如果32位整数溢出,我们可以使用40位结构而不是64位长结构吗？

Question

例如,如果一个32位整数溢出,而不是升级int到long,如果我们需要一个仅在2 ⁴⁰之内的范围,我们可以使用一些40位类型,这样我们就可以节省24(64-40)位整数？

如果是这样,怎么样？

我必须处理数十亿和空间是一个更大的约束.

Answer 1

对,但是...

这当然是可能的,但它通常是荒谬的(对于任何不使用数十亿这些数字的程序):

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

在这里,var确实会有40位的宽度,代价是生成的代码效率低得多(事实证明"很多"是非常错误的 - 测得的开销仅为1-2%,见下面的时间),以及通常无济于事.除非您需要另外的24位值(或8位和16位值),您希望将其打包到相同的结构中,否则对齐将失去您可能获得的任何内容.

在任何情况下,除非你有数十亿这些,否则内存消耗的有效差异将不明显(但管理位字段所需的额外代码将是显而易见的!).

注意:
问题的平均时间已经更新,以反映确实需要数十亿的数字,所以这可能是可行的事情,假设您采取措施不会因结构对齐和填充而失去收益,即通过在剩余的24位中存储其他东西,或者将40位值存储在每个8或其倍数的结构中.
节省三个字节十亿次是值得的,因为它将需要明显更少的内存页面,从而导致更少的缓存和TLB未命中,以及最重要的页面错误(单页错误加权数千万条指令).

虽然上面的代码片段没有使用剩余的24位(它只是演示了"使用40位"部分),但是为了真正使该方法在保留内存的意义上有用,必须使用类似于以下内容的东西 - 假设你确实还有其他"有用"的数据可以放入漏洞中:

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

结构大小和对齐将等于64位整数,因此如果您制作例如十亿个这样的结构的数组(甚至不使用特定于编译器的扩展),则不会浪费任何东西.如果您没有使用8位值,您还可以使用48位和16位值(给出更大的溢出余量).
或者,您可以以可用性为代价,将8个40位值放入结构中(40和64的最小公倍数为320 = 8*40).当然然后代码,其访问元素的结构的阵列中的将成为多更加复杂(尽管或许可以实现一个operator[]能恢复线性阵列功能和隐藏结构的复杂性).

更新:
编写了一个快速测试套件,只是为了查看位域(以及运算符使用位域引用重载)会产生什么开销.在gcc.godbolt.org上发布代码(由于长度),我的Win7-64机器的测试输出是:

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

可以看到的是,位域的额外开销是可以忽略的,但是当以缓存友好的方式线性访问数据时,运算符重载位域引用作为一种方便的东西是相当激烈的(大约增加3倍).另一方面,随机访问它几乎不重要.

这些时序表明简单地使用64位整数会更好,因为它们总是比位域更快(尽管触及更多内存),但当然它们没有考虑更大数据集的页面错误的成本.一旦物理RAM耗尽,它可能看起来非常不同(我没有测试过).

Answer 2

您可以非常有效地将4*40位整数打包成160位结构,如下所示:

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);
}

这些可以像这样使用:

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 3

您可能需要考虑变长编码(VLE)

据推测,你已经在某个地方存储了很多这些数字(在RAM中,在磁盘上,通过网络发送它们等),然后一个接一个地进行处理.

一种方法是使用VLE 对它们进行编码.来自Google的protobuf 文档(CreativeCommons许可)

Varints是一种使用一个或多个字节序列化整数的方法.较小的数字占用较少的字节数.

varint中的每个字节(最后一个字节除外)都设置了最高有效位(msb) - 这表示还有其他字节.每个字节的低7位用于存储7位组中的二进制补码表示,最低有效组优先.

因此,例如,这里是数字1 - 它是单个字节,因此msb未设置:

0000 0001

这是300 - 这有点复杂:

1010 1100 0000 0010

你怎么知道这是300？首先从每个字节中删除msb,因为这只是告诉我们是否已到达数字的末尾(如您所见,它在第一个字节中设置,因为varint中有多个字节)

优点

• 如果你有很多小数字,平均每个整数可能会少于40个字节.可能要少得多.
• 您将来可以存储更大的数字(超过40位),而不必为小的数字支付罚金

缺点

• 您为数字的每7个有效位额外支付一笔费用.这意味着具有40个有效位的数字将需要6个字节.如果您的大多数数字都有40个有效位,那么使用位域方法会更好.
• 您将失去在给定索引的情况下轻松跳转到数字的能力(您必须至少部分地解析数组中的所有先前元素才能访问当前元素.
• 在对数字做任何有用的事情之前,你需要某种形式的解码(尽管其他方法也是如此,比如位字段)

Answer 4

(编辑:首先 - 你想要的是什么,在某些情况下是有意义的;当我尝试为Netflix挑战做一些事情并且只有1GB的内存时,我不得不做类似的事情;第二 - 它可能是最好的使用char数组进行40位存储,以避免任何对齐问题,并且需要混淆struct packing pragma;第三 - 这个设计假设您可以使用64位算术来获得中间结果,它只适用于大型您将使用Int40的数组存储;第四:我没有得到所有建议,这是一个坏主意,只是阅读人们通过打包网格数据结构,这看起来像比较的孩子的游戏).

你想要的是一个结构,它只用于将数据存储为40位整数,但隐式转换为int64_t进行运算.唯一的技巧是将符号扩展从40位改为64位.如果您对未签名的整数没问题,那么代码可以更简单.这应该可以帮助你入门.

#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;
}

以下是试用它的链接:http://rextester.com/QWKQU25252

Answer 5

您可以使用位域结构,但它不会为您节省任何内存:

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

您可以将8个这样的40位变量的任意倍数压缩到一个结构中:

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;
};

这将节省一些内存(与使用8"标准"64位变量相比),但您必须将每个操作(特别是算术运算)拆分为多个操作.

因此,内存优化将被"交易"以用于运行时性能.

Answer 6

正如评论所暗示的,这是一项非常重要的任务.

除非你想节省大量的RAM,否则可能是一种不必要的麻烦- 然后它会更有意义.(RAM节省将是long存储在RAM中的数百万个值中保存的总和)

我会考虑使用5字节/字符的数组(5*8位= 40位).然后,您需要将位(溢出的int - 因此a long)值中的位移动到字节数组中以存储它们.

要使用这些值,然后将这些位移回到a中long,您可以使用该值.

然后你的RAM和文件存储的值将是40位(5字节),但如果你打算使用a struct来保存5个字节,你必须考虑数据对齐.如果您需要详细说明这种位移和数据对齐的影响,请告诉我.

类似地,您可以使用64位long,并在您不想使用的剩余24位中隐藏其他值(可能是3个字符).再次 - 使用位移来添加和删除24位值.

Answer 7

我会假设的

1. 这是C,和
2. 你需要一个40位数的大型数组,和
3. 你在一台小端的机器上
4. 你的机器足够聪明,可以处理对齐
5. 您已将大小定义为您需要的40位数字的数量

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);
}

处理两班制获得可能会更快.

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

Answer 8

另一种可能有用的变化是使用结构:

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

这种结构需要16个字节,如果是16字节对齐,则完全适合单个高速缓存行.虽然识别要使用的结构的哪个部分可能比结构保持四个元素而不是三个元素更昂贵,但访问一个高速缓存行可能比访问两个更便宜.如果性能很重要,那么应该使用一些基准测试,因为一些机器可以廉价地执行divmod-3操作并且每个高速缓存行获取具有高成本,而其他机器可能具有更便宜的存储器访问和更昂贵的divmod-3.

Answer 9

如果你必须处理数十亿个整数,我会尝试封装40位数字的数组,而不是单个 40位数字.这样,您可以测试不同的阵列实现(例如,即时压缩数据的实现,或者可能将较少使用的数据存储到磁盘的实现),而无需更改代码的其余部分.

这是一个示例实现(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);
    }
};

注意:memcpy从40位到64位的转换基本上是未定义的行为,因为它假定为litte-endianness.但它应该可以在x86平台上运行.

注2:显然,这是概念验证代码,而不是生产就绪代码.要在实际项目中使用它,您必须添加(除其他外):

• 错误处理(malloc可能会失败!)
• 复制构造函数(例如,通过复制数据,添加引用计数或使复制构造函数为私有)
• 移动构造函数
• const重载
• STL兼容的迭代器
• 边界检查索引(在调试版本中)
• 范围检查值(在调试版本中)
• 声明隐含的假设(little-endianness)
• 实际上,它Item具有引用语义,而不是值语义,这是不寻常的operator[]; 您可以使用一些聪明的C++类型转换技巧来解决这个问题

对于C++程序员来说,所有这些都应该是直截了当的,但是他们会使代码代码更长,而不会让它更清晰,所以我决定省略它们.

Answer 10

对于存储数十亿个40位有符号整数并假设为8位字节的情况,可以在一个结构中打包8个40位有符号整数(在下面的代码中使用一个字节数组来完成),以及由于此结构通常是对齐的,因此您可以创建此类压缩组的逻辑数组,并提供以下常规顺序索引:

#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;
}