如果使用32位整型會溢出,那麼是否可以使用一個40位結構體代替64位長整型?
回答:
可以是可以,但是……
這種方法的確可行,但這麼做通常沒什麼意義(因為幾乎沒有程序需要處理多達十億的數字):
#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
本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive