如果使用32位整型会溢出,那么是否可以使用一个

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

如果可以,该怎么做?

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

如果使用32位整型会溢出,那么是否可以使用一个

回答:

可以是可以,但是……

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

#include<stdint.h>// 不要考虑使用long long类型

struct bad_idea

{

uint64_tvar:40;

};

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

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

说明:

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

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

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

struct using_gaps

{

uint64_tvar: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_t02135351

uint64_t03335351

bad40_t05335351

packed40_t07448491

 

运行测试的数组大小为16777216

what alloc seq(w) seq(r) rand(w) rand(r) free

-----------------------------------------------------------

uint32_t038145605558

uint64_t0812256555417

bad40_t0852556556116

packed40_t01517576577416

 

运行测试的数组大小为134177228

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/5ea90c1e3758bcb46746529433d807ee.html