歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

如果使用32位整型會溢出,那麼是否可以使用一個40位結構體代替64位長整型?

問題:

假如說,使用32位的整型會溢出,在不考慮使用長整型的情況下,如果我們只需要表示2的40次方范圍內的數,是否可以利用某些40位長的數據類型來表示呢?這樣的話,每個整型數就可以節省24位的空間。

如果可以,該怎麼做?

需求是:我現在必須處理數以億計的數字,所以在存儲空間上受到了很大的限制。

回答:

可以是可以,但是……

這種方法的確可行,但這麼做通常沒什麼意義(因為幾乎沒有程序需要處理多達十億的數字):

  1. #include<stdint.h>// 不要考慮使用long long類型
  2. struct bad_idea
  3. {
  4. uint64_tvar:40;
  5. };

在這裡,變量var占據40位大小,但是這是以生成代碼時擁有非常低的運行效率來換取的(事實證明“非常”二字言過其實了——測試中程序開銷僅僅增加了1%到2%,正如下面的測試時間所示),而且這麼做通常沒什麼用。除非你還需要保存一個24位的值(或者是8位、16位的值),這樣你皆可以它們放到同一個結構中。不然的話,因為對齊內存地址產生的開銷會抵消這麼做帶來的好處。

在任何情況下,除非你是真的需要保存數以億計的數字,否則這樣做給內存消耗帶來的好處是可以忽略不計的(但是為了處理這些位字段的額外代碼量是不可忽略的!)。

說明:

在此期間,這個問題已經被更新了,是為了說明實際上確實有需要處理數以億計數字的情況。假設,采取某些措施來防止因為結構體對齊和填充抵消好處(比如在後24位中存儲其它的內容,或者使用多個8位來存儲40位),那麼這麼做就變得有意義了。

如果有十億個數,每個數都節省三個字節的空間,那麼這麼做就非常有用了。因為使用更小的空間存儲要求更少的內存頁,也就會產生更少的cache和TLB不命中和內存缺頁(單個缺頁會產生數以千萬計的指令 [譯者注:直譯是這樣,但語義說不通!])。

盡管上面提到的情況不足以充分利用到剩余的24位(它僅僅使用了40位部分),如果確實在剩余位中放入了有用的數據,那麼使用類似下面的方法會使得這種思路就管理內存而言顯得非常有用。

  1. struct using_gaps
  2. {
  3. uint64_tvar:40;
  4. uint64_t useful_uint16 :16;
  5. uint64_t char_or_bool :8;
  6. };

結構體大小和對齊長度等於64位整型的大小,所以只要使用得當就不會浪費空間,比如對一個保存10億個數的數組使用這個結構(不考慮使用指定編譯器的擴展)。如果你不會用到一個8位的值,那麼你可以使用一個48位和16位的值(giving a bigger overflow margin)。

或者以犧牲可用性為代價,把8個64位的值放入這樣的結構體中(或者使用40和64的組合使得其和滿足320)。當然,在這種情況下,通過代碼去訪問數組結構體中的元素會變得非常麻煩(盡管一種方法是實現一個operator[]在功能上還原線性數組,隱藏結構體的復雜性)。

更新:

我寫了一個快速測試工具,只是為了獲得位字段的開銷(以及伴隨位字段引用的重載操作)。由於長度限制將代碼發布在gcc.godbolt.org上,在本人64位Win7上的測試結果如下:

  1. 運行測試的數組大小為1048576
  2. what alloc seq(w) seq(r) rand(w) rand(r) free
  3. -----------------------------------------------------------
  4. uint32_t02135351
  5. uint64_t03335351
  6. bad40_t05335351
  7. packed40_t07448491
  8.  
  9. 運行測試的數組大小為16777216
  10. what alloc seq(w) seq(r) rand(w) rand(r) free
  11. -----------------------------------------------------------
  12. uint32_t038145605558
  13. uint64_t0812256555417
  14. bad40_t0852556556116
  15. packed40_t01517576577416
  16.  
  17. 運行測試的數組大小為134177228
  18. what alloc seq(w) seq(r) rand(w) rand(r) free
  19. -----------------------------------------------------------
  20. uint32_t03121004480444165
  21. uint64_t064817244824490130
  22. bad40_t068219345734492130
  23. packed40_t0116455261816176130

我們看到,位字段的額外開銷是微不足道的,但是當以友好的方式線性訪問數據時伴隨位字段引用的操作符重載產生的開銷則相當顯著(大概有3倍)。在另一方面,隨機訪問產生的開銷則無足輕重。

這些時間表明簡單的使用64位整型會更好,因為它們在整體性能上要比位字段好(盡管占用更多的內存),但是顯然它們並沒有考慮隨著數據集增大帶來的缺頁開銷。一旦程序內存超過RAM大小,結果可能就不一樣了(未親自考證)。

Copyright © Linux教程網 All Rights Reserved