Pregunta Si un entero de 32 bits se desborda, ¿podemos usar una estructura de 40 bits en lugar de uno de 64 bits de longitud?


Si, por ejemplo, un 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 240, de modo que ahorramos 24 (64-40) bits por cada número entero

¿Si es así, cómo?

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


75
2017-12-30 12:22


origen


Respuestas:


Sí, pero...

Es seguramente 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 mucho código menos eficiente generado (resulta que "mucho" está muy mal - la sobrecarga medida es un mero 1-2%, ver los tiempos a continuación), y por lo general es 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 será notable (¡pero el código adicional necesario para administrar el campo de bit será notable!).

Nota:
Mientras tanto, la pregunta se ha actualizado para reflejar que efectivamente miles de millones de números, por lo que esto puede ser una tarea viable, suponiendo que se toman medidas para no perder las ganancias debido a la alineación de la estructura y el relleno, es decir, almacenando algo más en los 24 bits restantes o almacenando sus 40 bits valores en estructuras de 8 cada uno o múltiplos de los mismos).
Guardando tres bytes mil millones de veces Vale la pena, ya que requerirá un número notablemente menor de páginas de memoria y, por lo tanto, causará menos errores de caché y TLB, y sobre todo fallas de página (una falla de página única ponderando 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 realmente hacer que el enfoque sea útil en el sentido de preservar la memoria: se presume que de hecho tienes 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 de la estructura y la alineación será igual a un entero de 64 bits, por lo que no se desperdicia nada si haces, p. 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 y 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, su código que accede a elementos en la matriz de estructuras se convertirá en mucho más complicado (aunque uno podría probablemente implementar un operator[] que restaura la funcionalidad de matriz lineal y oculta la complejidad de la estructura).

Actualizar:
Escribí un conjunto de pruebas rápidas, solo para ver qué sobrecarga tendrían los bitfields (y la sobrecarga del operador con refs bitfield). 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 extra de bitfields es poco legible, pero la sobrecarga del operador con referencia de campo de bits como algo conveniente es bastante drástica (aproximadamente un aumento de 3x) cuando se accede linealmente a los datos en una manera de caché. Por otro lado, en el acceso aleatorio, apenas importa.

Estos tiempos sugieren que simplemente usar enteros de 64 bits sería mejor ya que son más rápidos en general que los bitfields (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 parecer muy diferente una vez que se quede sin RAM física (no lo he probado).


82
2017-12-30 12:32



Puede empaquetar de manera bastante efectiva 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 se pueden usar 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 )
}

53
2017-12-30 15:52



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

Presumiblemente, tiene que almacenar muchos de esos números en algún lugar (en la RAM, en el disco, enviarlos a través de la red, etc.), y luego tomarlos uno por uno y procesarlos.

Un enfoque sería codificar ellos usando VLE. Del protobuf de Google documentación (Licencia de Creative Commons)

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 menor cantidad de bytes.

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

Así que, por ejemplo, aquí está el número 1: es un byte único, 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 se da cuenta de que esto es 300? Primero dejas caer el msb de   cada byte, ya que esto solo está ahí para decirnos si hemos alcanzado el   fin del número (como puede ver, está establecido en el primer byte como allí   hay más de un byte en el varinte)

Pros

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

Contras

  • Pagas un poco más por cada 7 bits significativos de tus números. Eso significa que un número con 40 bits significativos necesitará 6 bytes. Si la mayoría de sus números tiene 40 bits significativos, es mejor con un enfoque de campo poco.
  • 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 a la actual.
  • Necesitará algún tipo de decodificación antes de hacer algo útil con los números (aunque eso también es cierto para otros enfoques, como campos de bit)

25
2017-12-30 20:29



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

Lo que quiere es una estructura que solo se use para almacenar datos como ints de 40 bits, pero implícitamente se convierta en int64_t para la aritmética. El único truco es hacer la extensión de signo de 40 a 64 bits a la derecha. Si estás bien con entradas sin firmar, el código puede ser incluso más simple. Esto debería ser capaz de 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


19
2017-12-30 16:44



Puedes usar una estructura de campo de bits, pero no te va a 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 deberá dividir todas las operaciones (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 "intercambiará" por el rendimiento en tiempo de ejecución.


16
2017-12-30 12:32



Como sugieren los comentarios, esta es toda una tarea.

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

Consideraría usar una matriz de 5 bytes / char (5 * 8 bits = 40 bits). Entonces necesitarás cambiar los bits de tu (int desbordado - de ahí una long) valor en la matriz de bytes para almacenarlos.

Para usar los valores, luego cambie los bits de vuelta a una long y puedes usar el valor

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

Del mismo modo, puede usar los 64 bits longy esconder otros valores (3 caracteres quizás) en los 24 bits restantes que no desea utilizar. Nuevamente, usar el cambio de bit para agregar y eliminar los valores de 24 bits.


8
2017-12-30 12:36



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 estuviera alineada con 16 bytes, encajaría completamente dentro de una sola línea de caché. Aunque identificar cuál de las partes de la estructura a utilizar puede ser más costosa 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 utilizar 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 un acceso a memoria más barato y divmod-3 más costoso.


6
2017-12-31 05:28



Asumiré que

  1. esto es C, y
  2. necesita una única matriz 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. usted ha definido el tamaño para ser la cantidad 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);
}

6
2017-12-30 21:58



Para el caso de almacenar algunos miles de millones de enteros con signo de 40 bits y asumir bytes de 8 bits, puede empaquetar 8 enteros con signo de 40 bits en una estructura (en el siguiente código usando una matriz de bytes para hacerlo), y dado que esta estructura está ordinariamente 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;
}

5
2018-01-01 00:47