Linux.中国 - 开源社区

 找回密码
 骑士注册

QQ登录

微博登录


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

2015-2-19 23:10    评论: 9 收藏: 5 分享: 13    

问题:

假如说,使用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大小,结果可能就不一样了(未亲自考证)。


via:stackoverflow

作者:DamonMichael Kohne 译者:KayGuoWhu 校对:wxy

本文由 LCTT 原创翻译,Linux中国 荣誉推出

发表评论


最新评论

我也要发表评论

教师_乙 2015-2-20 11:33  新浪微博网友评论
事实证明,瞎折腾通常得不偿失…
回复
路易斯偶偶 2015-2-20 11:03  新浪微博网友评论
@保存到为知笔记
回复
一个包子八个摺 2015-2-20 10:03  新浪微博网友评论
位段通常情况下会用来对应位图运算,或者直接操作寄存器。哪来当正常数据操作并大量使用~~我觉得还是掂量掂量吧
回复
一个包子八个摺 2015-2-20 10:03  新浪微博网友评论
基本上,这种操作就是把数据取回来,然后把多余位屏蔽掉,然后该怎么算怎么算,最后再把该屏蔽的位屏蔽了再放回去~就是多出几个位屏蔽操作~效率低是一回事。考虑一下代码量和数据量的平恒。每算一次就会多出几条指令~
回复
阿夏_黑黑 2015-2-20 02:03  新浪微博网友评论
对不齐……囧
回复
造化不弄僵尸大阿叔 2015-2-20 00:03  新浪微博网友评论
叠上个内存条[笑cry],增加偏移内存条,加寄存器,cpu哭了,,,,[笑cry]
回复
翼灵贰駟 2015-2-20 00:03  新浪微博网友评论
Repost
回复
范特熙-7 2015-2-19 23:33  新浪微博网友评论
好像很厉害的样子
回复
李大尖 2015-2-19 23:33  新浪微博网友评论
我想到了一个问题:求100亿以内所有质数的和
回复
返回顶部

分享到微信朋友圈

打开微信,点击底部的“发现”,
使用“扫一扫”将网页分享至朋友圈。