c++ - tipos - Si un número entero de 32 bits se desborda, ¿podemos usar una estructura de 40 bits en lugar de una de 64 bits?

tipos de variables en java netbeans

Question

Si, por ejemplo, un número entero de 32 bits se desborda, en lugar de actualizar int a long , podemos usar algún tipo de 40 bits si necesitamos un rango solo dentro de 2 ⁴⁰ , de modo que ahorremos 24 (64-40) bits por cada entero?

¿Si es así, cómo?

Tengo que lidiar con miles de millones y el espacio es una limitación mayor.

Answer 1

Es posible que desee considerar la codificación de longitud variable (VLE)

Presumiblemente, tiene almacenados muchos de esos números en algún lugar (en la RAM, en el disco, enviándolos a través de la red, etc.), y luego los toma uno por uno y realiza un procesamiento.

Un enfoque sería codificarlos usando VLE. De la documentation protobuf de Google (licencia CreativeCommons)

Los varints son un método de serialización de enteros utilizando uno o más bytes. Los números más pequeños toman una cantidad menor de bytes.

Cada byte en un varint, excepto el último byte, tiene el bit más significativo (msb) establecido; esto indica que hay más bytes por venir. Los 7 bits inferiores de cada byte se utilizan para almacenar la representación del complemento a dos del número en grupos de 7 bits, primero el grupo menos significativo.

Entonces, por ejemplo, aquí está el número 1: es un solo byte, por lo que el msb no está configurado:

0000 0001

Y aquí hay 300, esto es un poco más complicado:

1010 1100 0000 0010

¿Cómo te das cuenta de que esto es 300? Primero, suelta el msb de cada byte, ya que está allí para decirnos si hemos llegado al final del número (como puede ver, está configurado en el primer byte ya que hay más de un byte en el varint)

Pros

• Si tiene muchos números pequeños, probablemente usará menos de 40 bytes por entero, en promedio. Posiblemente mucho menos.
• Puede almacenar números más grandes (con más de 40 bits) en el futuro, sin tener que pagar una multa por los más pequeños.

Contras

• Usted paga un bit extra por cada 7 bits significativos de sus números. Eso significa que un número con 40 bits significativos necesitará 6 bytes. Si la mayoría de sus números tienen 40 bits significativos, es mejor con un enfoque de campo de bits.
• Perderá la capacidad de saltar fácilmente a un número dado su índice (debe analizar al menos parcialmente todos los elementos anteriores en una matriz para acceder al actual.
• Necesitará alguna forma de decodificación antes de hacer algo útil con los números (aunque eso también es cierto para otros enfoques, como los campos de bits)

Answer 2

Sí, pero...

Ciertamente es posible , pero generalmente no tiene sentido (para cualquier programa que no use miles de millones de estos números):

#include <stdint.h> // don''t want to rely on something like long long
struct bad_idea
{
uint64_t var : 40;
};

Aquí, var tendrá un ancho de 40 bits a expensas de un código mucho menos eficiente generado (resulta que "mucho" está muy mal: la sobrecarga medida es de solo 1-2%, vea los tiempos a continuación), y generalmente en vano. A menos que necesite otro valor de 24 bits (o un valor de 8 y 16 bits) que desee empaquetar en la misma estructura, la alineación perderá todo lo que pueda obtener.

En cualquier caso, a menos que tenga miles de millones de estos, la diferencia efectiva en el consumo de memoria no se notará (¡pero se notará el código adicional necesario para administrar el campo de bits!).

Nota:
Mientras tanto, la pregunta se ha actualizado para reflejar que de hecho se necesitan miles de millones de números, por lo que esto puede ser algo viable, suponiendo que tome medidas para no perder las ganancias debido a la alineación de la estructura y el relleno, es decir, al almacenar algo más en los 24 bits restantes o almacenando sus valores de 40 bits en estructuras de 8 cada uno o múltiplos de los mismos).
Vale la pena ahorrar tres bytes mil millones de veces, ya que requerirá notablemente menos páginas de memoria y, por lo tanto, provocará menos errores de caché y TLB, y sobre todo fallas de página (una sola falla de página que pesa decenas de millones de instrucciones).

Si bien el fragmento anterior no hace uso de los 24 bits restantes (simplemente demuestra la parte "usar 40 bits"), será necesario algo similar a lo siguiente para que el enfoque sea realmente útil en un sentido de preservar la memoria, presumiendo que de hecho tiene otros datos "útiles" para poner en los agujeros:

struct using_gaps
{
uint64_t var : 40;
uint64_t useful_uint16 : 16;
uint64_t char_or_bool : 8;
};

El tamaño y la alineación de la estructura serán iguales a un número entero de 64 bits, por lo que no se desperdicia nada si crea, por ejemplo, una matriz de mil millones de tales estructuras (incluso sin usar extensiones específicas del compilador). Si no tiene uso para un valor de 8 bits, también podría usar un valor de 48 bits y un valor de 16 bits (lo que da un mayor margen de desbordamiento).
Alternativamente, podría, a expensas de la usabilidad, poner 8 valores de 40 bits en una estructura (el mínimo común múltiplo de 40 y 64 es 320 = 8 * 40). Por supuesto, entonces su código que accede a elementos en la matriz de estructuras se volverá mucho más complicado (aunque probablemente se podría implementar un operator[] que restaure la funcionalidad de la matriz lineal y oculte la complejidad de la estructura).

Actualizar:
Escribió un conjunto de pruebas rápidas, solo para ver qué sobrecarga tendrían los campos de bits (y la sobrecarga del operador con referencias de campo de bits). Código publicado (debido a la longitud) en gcc.godbolt.org , la salida de prueba de mi máquina Win7-64 es:

Running test for array size = 1048576
what alloc seq(w) seq(r) rand(w) rand(r) free
-----------------------------------------------------------
uint32_t 0 2 1 35 35 1
uint64_t 0 3 3 35 35 1
bad40_t 0 5 3 35 35 1
packed40_t 0 7 4 48 49 1
Running test for array size = 16777216
what alloc seq(w) seq(r) rand(w) rand(r) free
-----------------------------------------------------------
uint32_t 0 38 14 560 555 8
uint64_t 0 81 22 565 554 17
bad40_t 0 85 25 565 561 16
packed40_t 0 151 75 765 774 16
Running test for array size = 134217728
what alloc seq(w) seq(r) rand(w) rand(r) free
-----------------------------------------------------------
uint32_t 0 312 100 4480 4441 65
uint64_t 0 648 172 4482 4490 130
bad40_t 0 682 193 4573 4492 130
packed40_t 0 1164 552 6181 6176 130

Lo que se puede ver es que la sobrecarga adicional de los campos de bits es despreciable, pero la sobrecarga del operador con referencia de campo de bits como una cosa conveniente es bastante drástica (un aumento de aproximadamente 3 veces) al acceder a los datos linealmente de una manera amigable para la caché. Por otro lado, en el acceso aleatorio apenas importa.

Estos tiempos sugieren que simplemente usar números enteros de 64 bits sería mejor, ya que aún son más rápidos en general que los campos de bits (a pesar de tocar más memoria), pero, por supuesto, no tienen en cuenta el costo de las fallas de página con conjuntos de datos mucho más grandes. Puede verse muy diferente una vez que se quede sin RAM física (no lo probé).

Answer 3

Esto suplica la transmisión de compresión sin pérdida en la memoria. Si esto es para una aplicación de Big Data, los trucos de empaque densos son soluciones tácticas en el mejor de los casos para lo que parece requerir un middleware bastante decente o soporte a nivel de sistema. Necesitarían pruebas exhaustivas para asegurarse de que uno pueda recuperar todos los bits ilesos. Y las implicaciones de rendimiento son altamente no triviales y dependen mucho del hardware debido a la interferencia con la arquitectura de almacenamiento en caché de la CPU (por ejemplo, líneas de caché frente a estructura de empaque). Alguien mencionó estructuras de mallado complejas: estas a menudo se ajustan para cooperar con arquitecturas de almacenamiento en caché particulares.

Los requisitos no aclaran si el OP necesita acceso aleatorio. Dado el tamaño de los datos, es más probable que uno solo necesite acceso aleatorio local en fragmentos relativamente pequeños, organizados jerárquicamente para su recuperación. Incluso el hardware hace esto en grandes tamaños de memoria (NUMA). Como muestran los formatos de película sin pérdida, debería ser posible obtener acceso aleatorio en fragmentos (''cuadros'') sin tener que cargar todo el conjunto de datos en la memoria activa (desde el almacén de respaldo comprimido en memoria).

Sé de un sistema de base de datos rápido (kdb de KX Systems para nombrar uno, pero sé que hay otros) que puede manejar conjuntos de datos extremadamente grandes al mapear memoria de forma irreversible grandes conjuntos de datos del almacén de respaldo. Tiene la opción de comprimir y expandir de forma transparente los datos sobre la marcha.

Answer 4

Si lo que realmente quiere es una matriz de enteros de 40 bits (que obviamente no puede tener), simplemente combinaría una matriz de enteros de 32 bits y una matriz de enteros de 8 bits.

Para leer un valor x en el índice i:

uint64_t x = (((uint64_t) array8 [i]) << 32) + array32 [i];

Para escribir un valor x para indexar i:

array8 [i] = x >> 32; array32 [i] = x;

Obviamente bien encapsulado en una clase usando funciones en línea para una velocidad máxima.

Hay una situación en la que esto es subóptimo, y es cuando se hace un acceso verdaderamente aleatorio a muchos elementos, de modo que cada acceso a una matriz int sería una falta de caché; aquí obtendría dos fallas de caché cada vez. Para evitar esto, defina una estructura de 32 bytes que contenga una matriz de seis uint32_t, una matriz de seis uint8_t y dos bytes no utilizados (41 2/3 bits por número); El código para acceder a un elemento es un poco más complicado, pero ambos componentes del elemento están en la misma línea de caché.

Answer 5

(Editar: en primer lugar, lo que quieres es posible y tiene sentido en algunos casos; he tenido que hacer cosas similares cuando intenté hacer algo para el desafío de Netflix y solo tenía 1 GB de memoria; en segundo lugar, probablemente sea mejor usar una matriz de caracteres para el almacenamiento de 40 bits para evitar problemas de alineación y la necesidad de meterse con pragmas de embalaje de estructura; Tercero: este diseño asume que está bien con la aritmética de 64 bits para resultados intermedios, es solo para grandes almacenamiento de matriz que usaría Int40; Cuarto: no recibo todas las sugerencias de que esta sea una mala idea, solo lea sobre lo que pasa la gente para empacar estructuras de datos de malla y esto parece un juego de niños en comparación).

Lo que desea es una estructura que solo se usa para almacenar datos como entradas de 40 bits, pero se convierte implícitamente en int64_t para aritmética. El único truco es hacer la extensión de signo de 40 a 64 bits a la derecha. Si está bien con las entradas sin firmar, el código puede ser aún más simple. Esto debería poder ayudarte a comenzar.

#include <cstdint>
#include <iostream>
// Only intended for storage, automatically promotes to 64-bit for evaluation
struct Int40
{
Int40(int64_t x) { set(static_cast<uint64_t>(x)); } // implicit constructor
operator int64_t() const { return get(); } // implicit conversion to 64-bit
private:
void set(uint64_t x)
{
setb<0>(x); setb<1>(x); setb<2>(x); setb<3>(x); setb<4>(x);
};
int64_t get() const
{
return static_cast<int64_t>(getb<0>() | getb<1>() | getb<2>() | getb<3>() | getb<4>() | signx());
};
uint64_t signx() const
{
return (data[4] >> 7) * (uint64_t(((1 << 25) - 1)) << 39);
};
template <int idx> uint64_t getb() const
{
return static_cast<uint64_t>(data[idx]) << (8 * idx);
}
template <int idx> void setb(uint64_t x)
{
data[idx] = (x >> (8 * idx)) & 0xFF;
}
unsigned char data[5];
};
int main()
{
Int40 a = -1;
Int40 b = -2;
Int40 c = 1 << 16;
std::cout << "sizeof(Int40) = " << sizeof(Int40) << std::endl;
std::cout << a << "+" << b << "=" << (a+b) << std::endl;
std::cout << c << "*" << c << "=" << (c*c) << std::endl;
}

Aquí está el enlace para probarlo en vivo: http://rextester.com/QWKQU25252

Answer 6

Aquí hay bastantes respuestas que cubren la implementación, por lo que me gustaría hablar sobre arquitectura.

Por lo general, ampliamos los valores de 32 bits a valores de 64 bits para evitar el desbordamiento porque nuestras arquitecturas están diseñadas para manejar valores de 64 bits.

La mayoría de las arquitecturas están diseñadas para trabajar con números enteros cuyo tamaño es una potencia de 2 porque esto hace que el hardware sea mucho más simple. Las tareas como el almacenamiento en caché son mucho más simples de esta manera: hay una gran cantidad de divisiones y operaciones de módulo que se pueden reemplazar con enmascaramiento de bits y cambios si se adhieren a potencias de 2.

Como un ejemplo de cuánto importa esto, la especificación C ++ 11 define casos de carrera de subprocesos múltiples basados ​​en "ubicaciones de memoria". Una ubicación de memoria se define en 1.7.3:

Una ubicación de memoria es un objeto de tipo escalar o una secuencia máxima de campos de bits adyacentes que tienen un ancho distinto de cero.

En otras palabras, si usa los campos de bits de C ++, debe hacer todo su subprocesamiento múltiple cuidadosamente. Dos campos de bits adyacentes deben tratarse como la misma ubicación de memoria, incluso si desea que los cálculos a través de ellos puedan extenderse a través de múltiples subprocesos. Esto es muy inusual para C ++, por lo que es probable que cause frustración al desarrollador si tiene que preocuparse por ello.

La mayoría de los procesadores tienen una arquitectura de memoria que obtiene bloques de memoria de 32 bits o 64 bits a la vez. Por lo tanto, el uso de valores de 40 bits tendrá un sorprendente número de accesos adicionales a la memoria, lo que afectará drásticamente el tiempo de ejecución. Considere los problemas de alineación:

40-bit word to access: 32-bit accesses 64bit-accesses
word 0: [0,40) 2 1
word 1: [40,80) 2 2
word 2: [80,120) 2 2
word 3: [120,160) 2 2
word 4: [160,200) 2 2
word 5: [200,240) 2 2
word 6: [240,280) 2 2
word 7: [280,320) 2 1

En una arquitectura de 64 bits, una de cada 4 palabras será "velocidad normal". El resto requerirá obtener el doble de datos. Si obtiene muchos errores de caché, esto podría destruir el rendimiento. Incluso si obtiene aciertos de caché, tendrá que desempaquetar los datos y volver a empaquetarlos en un registro de 64 bits para usarlos (lo que incluso podría implicar una rama difícil de predecir).

Es completamente posible que valga la pena el costo

Hay situaciones en las que estas sanciones son aceptables. Si tiene una gran cantidad de datos residentes en la memoria que están bien indexados, puede encontrar que el ahorro de memoria vale la pena de rendimiento. Si realiza una gran cantidad de cálculo en cada valor, puede encontrar que los costos son mínimos. Si es así, no dude en implementar una de las soluciones anteriores. Sin embargo, aquí hay algunas recomendaciones.

• No use bitfields a menos que esté listo para pagar su costo. Por ejemplo, si tiene una variedad de campos de bits y desea dividirla para procesarla en varios subprocesos, está atascado. Según las reglas de C ++ 11, todos los campos de bits forman una ubicación de memoria, por lo que solo se puede acceder por un hilo a la vez (esto se debe a que el método de empaquetar los campos de bits está definido en la implementación, por lo que C ++ 11 no puede ayudarlo a distribuirlos de una manera no implementada definida)
• No use una estructura que contenga un entero de 32 bits y un carácter para hacer 40 bytes. La mayoría de los procesadores impondrán la alineación y no guardará un solo byte.
• Utilice estructuras de datos homogéneas, como una matriz de caracteres o una matriz de enteros de 64 bits. Es mucho más fácil obtener la alineación correcta. (Y también conserva el control del empaque, lo que significa que puede dividir una matriz entre varios hilos para el cálculo si tiene cuidado)
• Diseñe soluciones separadas para procesadores de 32 bits y 64 bits, si tiene que soportar ambas plataformas. Debido a que está haciendo algo de muy bajo nivel y muy mal soportado, necesitará personalizar cada algoritmo a su arquitectura de memoria.
• Recuerde que la multiplicación de números de 40 bits es diferente de la multiplicación de expansiones de 64 bits de números de 40 bits reducidos a 40 bits. Al igual que cuando se trata con la FPU x87, debe recordar que ordenar sus datos entre tamaños de bits cambia su resultado.

Answer 7

Asumiré que

1. esto es C y
2. necesita un único conjunto grande de números de 40 bits, y
3. estás en una máquina que es little endian, y
4. su máquina es lo suficientemente inteligente como para manejar la alineación
5. ha definido el tamaño como el número de números de 40 bits que necesita

unsigned char hugearray[5*size+3]; // +3 avoids overfetch of last element
__int64 get_huge(unsigned index)
{
__int64 t;
t = *(__int64 *)(&hugearray[index*5]);
if (t & 0x0000008000000000LL)
t |= 0xffffff0000000000LL;
else
t &= 0x000000ffffffffffLL;
return t;
}
void set_huge(unsigned index, __int64 value)
{
unsigned char *p = &hugearray[index*5];
*(long *)p = value;
p[4] = (value >> 32);
}

Puede ser más rápido manejar el get con dos turnos.

__int64 get_huge(unsigned index)
{
return (((*(__int64 *)(&hugearray[index*5])) << 24) >> 24);
}

Answer 8

Como sugieren los comentarios, esta es una gran tarea.

Probablemente sea una molestia innecesaria a menos que quiera ahorrar mucha RAM, entonces tiene mucho más sentido. (El ahorro de RAM sería la suma total de bits guardados en millones de valores long almacenados en RAM)

Consideraría usar una matriz de 5 bytes / char (5 * 8 bits = 40 bits). Luego, deberá cambiar los bits de su valor (desbordado int, por lo tanto, un valor long ) a la matriz de bytes para almacenarlos.

Para usar los valores, luego cambie los bits de nuevo a un long y puede usar el valor.

Luego, el almacenamiento de RAM y archivos del valor será de 40 bits (5 bytes), PERO debe considerar la alineación de datos si planea usar una struct para contener los 5 bytes. Avíseme si necesita más detalles sobre este cambio de bit y las implicaciones de alineación de datos.

Del mismo modo, podría usar los 64 bits de long y ocultar otros valores (quizás 3 caracteres) en los 24 bits residuales que no desea usar. Nuevamente, utilizando el desplazamiento de bits para agregar y eliminar los valores de 24 bits.

Answer 9

Otra variación que puede ser útil sería usar una estructura:

typedef struct TRIPLE_40 {
uint32_t low[3];
uint8_t hi[3];
uint8_t padding;
};

Tal estructura tomaría 16 bytes y, si se alinea a 16 bytes, cabría completamente dentro de una sola línea de caché. Si bien identificar cuál de las partes de la estructura usar puede ser más costoso de lo que sería si la estructura tuviera cuatro elementos en lugar de tres, acceder a una línea de caché puede ser mucho más barato que acceder a dos. Si el rendimiento es importante, se deben usar algunos puntos de referencia, ya que algunas máquinas pueden realizar una operación divmod-3 a bajo costo y tener un alto costo por búsqueda de línea de caché, mientras que otras pueden tener acceso a memoria más barato y divmod-3 más costoso.

Answer 10

Para el caso de almacenar algunos miles de millones de enteros con signo de 40 bits, y suponiendo bytes de 8 bits, puede empacar 8 enteros con signo de 40 bits en una estructura (en el siguiente código utilizando una matriz de bytes para hacer eso), y, Dado que esta estructura está normalmente alineada, puede crear una matriz lógica de dichos grupos empaquetados y proporcionar una indexación secuencial ordinaria de eso:

#include <limits.h> // CHAR_BIT
#include <stdint.h> // int64_t
#include <stdlib.h> // div, div_t, ptrdiff_t
#include <vector> // std::vector
#define STATIC_ASSERT( e ) static_assert( e, #e )
namespace cppx {
using Byte = unsigned char;
using Index = ptrdiff_t;
using Size = Index;
// For non-negative values:
auto roundup_div( const int64_t a, const int64_t b )
-> int64_t
{ return (a + b - 1)/b; }
} // namespace cppx
namespace int40 {
using cppx::Byte;
using cppx::Index;
using cppx::Size;
using cppx::roundup_div;
using std::vector;
STATIC_ASSERT( CHAR_BIT == 8 );
STATIC_ASSERT( sizeof( int64_t ) == 8 );
const int bits_per_value = 40;
const int bytes_per_value = bits_per_value/8;
struct Packed_values
{
enum{ n = sizeof( int64_t ) };
Byte bytes[n*bytes_per_value];
auto value( const int i ) const
-> int64_t
{
int64_t result = 0;
for( int j = bytes_per_value - 1; j >= 0; --j )
{
result = (result << 8) | bytes[i*bytes_per_value + j];
}
const int64_t first_negative = int64_t( 1 ) << (bits_per_value - 1);
if( result >= first_negative )
{
result = (int64_t( -1 ) << bits_per_value) | result;
}
return result;
}
void set_value( const int i, int64_t value )
{
for( int j = 0; j < bytes_per_value; ++j )
{
bytes[i*bytes_per_value + j] = value & 0xFF;
value >>= 8;
}
}
};
STATIC_ASSERT( sizeof( Packed_values ) == bytes_per_value*Packed_values::n );
class Packed_vector
{
private:
Size size_;
vector<Packed_values> data_;
public:
auto size() const -> Size { return size_; }
auto value( const Index i ) const
-> int64_t
{
const auto where = div( i, Packed_values::n );
return data_[where.quot].value( where.rem );
}
void set_value( const Index i, const int64_t value )
{
const auto where = div( i, Packed_values::n );
data_[where.quot].set_value( where.rem, value );
}
Packed_vector( const Size size )
: size_( size )
, data_( roundup_div( size, Packed_values::n ) )
{}
};
} // namespace int40
#include <iostream>
auto main() -> int
{
using namespace std;
cout << "Size of struct is " << sizeof( int40::Packed_values ) << endl;
int40::Packed_vector values( 25 );
for( int i = 0; i < values.size(); ++i )
{
values.set_value( i, i - 10 );
}
for( int i = 0; i < values.size(); ++i )
{
cout << values.value( i ) << " ";
}
cout << endl;
}

Answer 11

Puede empaquetar enteros de 4 * 40 bits en una estructura de 160 bits como esta:

struct Val4 {
char hi[4];
unsigned int low[4];
}
long getLong( const Val4 &pack, int ix ) {
int hi= pack.hi[ix]; // preserve sign into 32 bit
return long( (((unsigned long)hi) << 32) + (unsigned long)pack.low[i]);
}
void setLong( Val4 &pack, int ix, long val ) {
pack.low[ix]= (unsigned)val;
pack.hi[ix]= (char)(val>>32);
}

Estos nuevamente pueden usarse así:

Val4[SIZE] vals;
long getLong( int ix ) {
return getLong( vals[ix>>2], ix&0x3 )
}
void setLong( int ix, long val ) {
setLong( vals[ix>>2], ix&0x3, val )
}

Answer 12

Puede usar una estructura de campo de bits, pero no le ahorrará memoria:

struct my_struct
{
unsigned long long a : 40;
unsigned long long b : 24;
};

Puede exprimir cualquier múltiplo de 8 de esas variables de 40 bits en una estructura:

struct bits_16_16_8
{
unsigned short x : 16;
unsigned short y : 16;
unsigned short z : 8;
};
struct bits_8_16_16
{
unsigned short x : 8;
unsigned short y : 16;
unsigned short z : 16;
};
struct my_struct
{
struct bits_16_16_8 a1;
struct bits_8_16_16 a2;
struct bits_16_16_8 a3;
struct bits_8_16_16 a4;
struct bits_16_16_8 a5;
struct bits_8_16_16 a6;
struct bits_16_16_8 a7;
struct bits_8_16_16 a8;
};

Esto le ahorrará algo de memoria (en comparación con el uso de 8 variables "estándar" de 64 bits), pero tendrá que dividir cada operación (y en particular las aritméticas) en cada una de estas variables en varias operaciones.

Por lo tanto, la optimización de la memoria se "cambiará" por rendimiento en tiempo de ejecución.

Answer 13

Sí, puede hacerlo, y ahorrará espacio para grandes cantidades de números.

Necesita una clase que contenga un std :: vector de un tipo entero sin signo.

Necesitará funciones miembro para almacenar y recuperar un número entero. Por ejemplo, si desea almacenar 64 enteros de 40 bits cada uno, use un vector de 40 enteros de 64 bits cada uno. Entonces necesita un método que almacene un número entero con índice en [0,64] y un método para recuperar dicho número entero.

Estos métodos ejecutarán algunas operaciones de cambio, y también algunos binarios | y &.

Todavía no agrego más detalles aquí porque su pregunta no es muy específica. ¿Sabes cuántos enteros quieres almacenar? ¿Lo sabes durante el tiempo de compilación? ¿Lo sabes cuando comienza el programa? ¿Cómo deben organizarse los enteros? ¿Como una matriz? ¿Como un mapa? Debe saber todo esto antes de intentar exprimir los enteros en menos espacio de almacenamiento.

Answer 14

Si tiene que lidiar con miles de millones de enteros, trataría de encapsular matrices de números de 40 bits en lugar de números únicos de 40 bits. De esa manera, puede probar diferentes implementaciones de matriz (por ejemplo, una implementación que comprime datos sobre la marcha, o tal vez una que almacene datos menos utilizados en el disco) sin cambiar el resto de su código.

Aquí hay una implementación de muestra ( http://rextester.com/SVITH57679 ):

class Int64Array
{
char* buffer;
public:
static const int BYTE_PER_ITEM = 5;
Int64Array(size_t s)
{
buffer=(char*)malloc(s*BYTE_PER_ITEM);
}
~Int64Array()
{
free(buffer);
}
class Item
{
char* dataPtr;
public:
Item(char* dataPtr) : dataPtr(dataPtr){}
inline operator int64_t()
{
int64_t value=0;
memcpy(&value, dataPtr, BYTE_PER_ITEM); // Assumes little endian byte order!
return value;
}
inline Item& operator = (int64_t value)
{
memcpy(dataPtr, &value, BYTE_PER_ITEM); // Assumes little endian byte order!
return *this;
}
};
inline Item operator[](size_t index)
{
return Item(buffer+index*BYTE_PER_ITEM);
}
};

Nota: La memcpy memcpy de 40 bits a 64 bits es básicamente un comportamiento indefinido, ya que asume memcpy capacidad. Sin embargo, debería funcionar en plataformas x86.

Nota 2: Obviamente, este es un código de prueba de concepto, no un código listo para producción. Para usarlo en proyectos reales, tendría que agregar (entre otras cosas):

• manejo de errores (¡malloc puede fallar!)
• Copiar constructor (por ejemplo, copiando datos, agregando recuento de referencias o haciendo privado el constructor de copias)
• mover constructor
• const sobrecargas
• Iteradores compatibles con STL
• comprobaciones de límites para índices (en la compilación de depuración)
• comprobaciones de rango para valores (en la construcción de depuración)
• afirma los supuestos implícitos (little-endianness)
• Tal como está, el Item tiene una semántica de referencia, no una semántica de valor, lo cual es inusual para el operator[] ; Probablemente podría evitar eso con algunos ingeniosos trucos de conversión de tipo C ++

Todos estos deberían ser sencillos para un programador de C ++, pero harían que el código de muestra fuera mucho más largo sin hacerlo más claro, por lo que he decidido omitirlos.