如果使用 32 位整型会溢出 那么是否可以使用一个 40 位结构体代替 64 位长整型？

Question

问题

假如说，使用 32 位的整型会溢出，在不考虑使用长整型的情况下，如果我们只需要表示 2 的 40 次方范围内的数，是否可以利用某些 40 位长的数据类型来表示呢？这样的话，每个整型数就可以节省 24 位的空间。

如果可以，该怎么做？

需求是：我现在必须处理数以亿计的数字，所以在存储空间上受到了很大的限制。

回答

可以是可以，但是……

这种方法的确可行，但这么做通常没什么意义（因为几乎没有程序需要处理多达十亿的数字）：

#include <stdint.h> // 不要考虑使用 long long 类型
struct bad_idea
{
    uint64_t var : 40;
};

在这里，变量 var 占据 40 位大小，但是这是以生成代码时拥有非常低的运行效率来换取的（事实证明“非常”二字言过其实了——测试中程序开销仅仅增加了 1%到 2%，正如下面的测试时间所示），而且这么做通常没什么用。除非你还需要保存一个 24 位的值（或者是 8 位、16 位的值），这样你皆可以它们放到同一个结构中。不然的话，因为对齐内存地址产生的开销会抵消这么做带来的好处。

在任何情况下，除非你是真的需要保存数以亿计的数字，否则这样做给内存消耗带来的好处是可以忽略不计的（但是为了处理这些位字段的额外代码量是不可忽略的！）。

说明：

在此期间，这个问题已经被更新了，是为了说明实际上确实有需要处理数以亿计数字的情况。假设，采取某些措施来防止因为结构体对齐和填充抵消好处（比如在后 24 位中存储其它的内容，或者使用多个 8 位来存储 40 位），那么这么做就变得有意义了。

如果有十亿个数，每个数都节省三个字节的空间，那么这么做就非常有用了。因为使用更小的空间存储要求更少的内存页，也就会产生更少的 cache 和 TLB 不命中和内存缺页（单个缺页会产生数以千万计的指令 [译者注：直译是这样，但语义说不通！]）。

尽管上面提到的情况不足以充分利用到剩余的 24 位（它仅仅使用了 40 位部分），如果确实在剩余位中放入了有用的数据，那么使用类似下面的方法会使得这种思路就管理内存而言显得非常有用。

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

结构体大小和对齐长度等于 64 位整型的大小，所以只要使用得当就不会浪费空间，比如对一个保存 10 亿个数的数组使用这个结构（不考虑使用指定编译器的扩展）。如果你不会用到一个 8 位的值，那么你可以使用一个 48 位和 16 位的值（giving a bigger overflow margin）。

或者以牺牲可用性为代价，把 8 个 64 位的值放入这样的结构体中（或者使用 40 和 64 的组合使得其和满足 320）。当然，在这种情况下，通过代码去访问数组结构体中的元素会变得非常麻烦（尽管一种方法是实现一个 operator[]在功能上还原线性数组，隐藏结构体的复杂性）。

更新：

我写了一个快速测试工具，只是为了获得位字段的开销（以及伴随位字段引用的重载操作）。由于长度限制将代码发布在 gcc.godbolt.org 上，在本人 64 位 Win7 上的测试结果如下：

运行测试的数组大小为 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

运行测试的数组大小为 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

运行测试的数组大小为 134177228
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 大小，结果可能就不一样了（未亲自考证）。