標籤:

如何理解 struct 的內存對齊?


ludx/The-Lost-Art-of-C-Structure-Packing · GitHub


padding = (align - (offset mod align)) mod align
new offset = offset + padding = offset + (align - (offset mod align)) mod align

the total size of the structure should be a multiple of the largest alignment of any structure member
------ wikipedia

3 個因素導致現在的地址對齊約定:

  1. 生活很艱難
  2. 世界多姿多彩,世上有各種不同的人存在
  3. 但我們還是要在一起呀在一起

以下以最簡,理想的模型進行討論。

一個最小存儲單位為 8 位元組的內存來說。訪問地址1, 大小為 4 位元組的數據。只需讀取地址 0 的 8 位元組的數據。然後在出口處移位下就行。因為只需在出口處做一次處理,所以可以不計成本進行移位優化,但這種優化只能在部件內部或者部件組內部進行。不同組件的交互部分對「對齊」還是有不同的看法的。又因為 RISC CPU 的設計,大多精簡指令集的指令長就是字長。而指令還需區分取立即數和各種 action, 一字長的指令無法全部用來表示地址空間。綜上,大多 RISC CPU 強制地址對齊,地址的低位腦補成 0。順便也減少了地址線的寬度。

訪問內存的速度是非常非常非常……慢的。再加上 CPU 及其指令設計的限制。在這種艱苦條件下,我們必須無所不用其極地減少隨機內存訪問次數:

  • 在一個訪問周期里讀寫最多,但不更多的數據。也就是一字長大小的數據。
  • 對於 CPU, 內存的最小存儲單元的大小為最大,但不更大的 CPU 字長。

基於此,一般的 RISC CPU 的地址線寬度為 wordSize - log_2frac{wordSize}{byteSize}. 比如一個 32 位 CPU 的字長是 32bit, 位元組大小為 8bit, 那麼地址線寬度為 32 - log_2frac{32}{8} = 30 可選擇 2^{30} 個地址單位, 每個單位的大小是 4 位元組 於是總共可管理 2^{30}*4=2^{30+2} 位元組的內存。這也是邏輯地址最低 log_2frac{wordSize}{byteSize} 位總是為 0 的來歷了。對於 32bit 字長的 CPU, 就是最低 2 位為 0 了。注意,此段所述只是基於 de-facto 習慣(1 byte = 8 bit, mem 空間大小為 2^{wordSize}

byte), 為了便於討論而做的假設。並無特別的意義和強行規定。

以一個字長為 4 位元組的 RISC CPU 來進行討論。單位為位元組。
此時,如果我們需要訪問地址為 2 的大小為 1 字長也就是 4 位元組的數據,也就是 2-5 的數據. 地址 2 mod 大小 4 = 2 不為 0. 這是未對齊的訪問。(地址線以二進位表示。最後兩位空置,所以始終為邏輯 0)我們需要將地址線設為 0(00) 讀出 0-3, 取 2-3, 然後將地址線設為 1(00) 讀出 4-7 取 4-5, 然後再合成所需數據。共兩次訪問。如果要訪問地址為 0(00) 或者 1(00) 的大小為 1 字長的數據。則一次訪問即可。
這就是地址不對齊導致訪問變慢的來歷了。

此時若要訪問 地址 2 的半個字長大小的數據。也就是 2-3 的數據。我們可以將地址設為 0(00) 讀出 0-3 的數據,然後將其在寄存器中右移 2 位元組即可。

那麼,問題來了。既然如此,我也可以訪問地址 1, 大小為 2 位元組的數據啊。也就是 1-2 的數據。將地址線設成 0(00) 讀出數據,然後在寄存器內左移 1 位元組,再右移 2 位元組就行了啊。
這時候 1 mod 2= 1, 不為 0, 但需要訪問內存的次數還是一次。
但世界上有許多地方,那兒的 CPU 字長只有 2 位元組。當數據到那些地方去旅行時。那兒的 CPU 訪問地址為 1, 大小為 2 位元組的數據的時候還是需要兩次的。

那麼,問題又來了。字長為 4 位元組的 CPU, 訪問 8 位元組長度的數據,這個數據反正始終都要讀兩次,那麼它不對齊也是可以的呀。只要他的地址 mod 4 為 0 就可以了。
但世界上還有些地方,那兒的 CPU 字長是 8 位元組的,當數據到那些地方去旅行時。那兒的 CPU 訪問大小為 8 位元組的數據,若其地址 mod 8 為 0 時,只要讀一次就夠了。此時讀兩次就是一種浪費了。

我們的世界是個艱難但又多姿多彩的世界。為了大家的數據都有一個兼容且一致的模型,方便交換,分析。我們鄭重做出約定:

大小為 size 的欄位,他的結構內偏移 offset 需符合 offset mod size 為 0.
引用的 wikipedia 的第一段就是對這句話的精確表述。

最後,問題又來了。

struct hi { let: 4 // padding 4 us: 8 // padding 0 play: 1 // padding 1 together: 2 // padding ? }

together 欄位的 padding 是要多少?是的 padding 0 就行了。所以大小是 8 + 8 + 2 + 2= 20
那為什麼 gcc 告訴我們應該是 24 呢。

因為我們的世界不是孤單的世界。

數據們可以歡樂地組成團隊。

hi group[2];

如果我們不能相互體諒,自私地將最後的 padding 設為 0 的話。

假設第一個 hi 位於地址 0, 那麼第二個 hi 就得從地址 20 開始了。此時 us 的地址是 20+sizeOf(let)+padding(let)= 20+4+4= 28

, 而 28 mod 8= 4 不為 0.
如果 hi 的大小為其中最大單元的整數倍也就是 8 * 3= 24 的話。那麼 第二個 hi 的 us 欄位的地址是 24+8= 32. 而 32 mod 8= 0, 對齊了。所以,最後我們還需要 padding 4 位元組。
在這個不孤單的世界裡,為了同一類數據能和諧相處。所以我們鄭重做出約定:

整個結構的大小必須是其中最大欄位大小的整數倍。

於是,不管是在一個數組裡沒羞沒臊地在一起。還是在這個如此多姿多彩各不相同的世界裡到處旅行。數據們的美好的生活都可以快速,和諧,一致地進行啦。

最後,若題主有閑,推薦看一下哈佛的 CS101, From NAND to Tetris 課程。從最簡單的邏輯門開始,自己動手打造一遍 latch, flip-flop, register,RAM, ALU, CPU, assembler, compiler. 相信到時候你會有更深的體會。


5分鐘教你秒殺:

前言:(10秒)

前面的各位的方法很好,很傳神,不適合速成,想要速成還得看我這種小屁孩寫的

公式:(20秒)

公式1:前面的地址必須是後面的地址正數倍,不是就補齊

公式2:整個Struct的地址必須是最大位元組的整數倍

30秒....敵人還有三十秒到達戰場...來看看下面的Ex(不是前任...!)

Struct E1

{ int a;char b; char c}e1;

第一地址肯定存放a是4Byte地址,第二地址,b要1Byte的地址,來歡迎公式一登場: 4 == 1*N (N等於正整數) 答""!地址現在為5Byte,下一個c要1Byte的地址同上,所以,就是6Byte。來歡迎公式二登場,在這個E1中最大的位元組是4,而我們的地址位元組是6,4的整數倍不是6,所以,要加2Byte(總地址),So,整個位元組為8!

CAUTION:

每個特定平台上的編譯器都有自己的默認「對齊係數」。可以通過預編譯命令#pragma pack(n)

喝下茶,緩緩


看我背書大法:

許多計算機系統對基本數據類型合法地址做出了一些限制,要求某種類型對象的地址必須是某個值K(通常是2、4或8)的倍數。這種對齊限制簡化了形成處理器和存儲器系統之間介面的硬體設計。

所以說對齊就是為了優化硬體效率。

另外Linux和Windows的對齊策略似乎是不一樣的。


空間換時間不是很常見嘛


背書式:各成員變數存放的起始地址相對於結構的起始地址的偏移量必須為該變數的類型所佔用的位元組數的倍數 各成員變數在存放的時候根據在結構中出現的順序依次申請空間 同時按照上面的對齊方式調整位置 空缺的位元組自動填充 同時為了確保結構的大小為結構的位元組邊界數(即該結構中佔用最大的空間的類型的位元組數)的倍數,所以在為最後一個成員變數申請空間後 還會根據需要自動填充空缺的位元組

多!

簡!

單!


位元組對齊主要是為了提高內存的訪問效率,比如intel 32為cpu,每個匯流排周期都是從偶地址開始讀取32位的內存數據,如果數據存放地址不是從偶數開始,則可能出現需要兩個匯流排周期才能讀取到想要的數據,因此需要在內存中存放數據時進行對齊。

通常我們說位元組對齊很多時候都是說struct結構體的內存對齊,比如下面的結構體:

struct A{
char a;
int b;
short c;
}

在32位機器上char 佔1個位元組,int 佔4個位元組,short佔2個位元組,一共佔用7個位元組.但是實際真的是這樣嗎?

我們先看下面程序的輸出:

#include &

struct A{
char a;
int b;
short c;
};
int main(){
struct A a;
printf("A: %ld
", sizeof(a));
return 0;
}

測試輸出的結果是A: 12, 比計算的7多了5個位元組。這個就是因為編譯器在編譯的時候進行了內存對齊導致的。

內存對齊主要遵循下面三個原則:

  1. 結構體變數的起始地址能夠被其最寬的成員大小整除
  2. 結構體每個成員相對於起始地址的偏移能夠被其自身大小整除,如果不能則在前一個成員後面補充位元組
  3. 結構體總體大小能夠被最寬的成員的大小整除,如不能則在後面補充位元組

其實這裡有點不嚴謹,編譯器在編譯的時候是可以指定對齊大小的,實際使用的有效對齊其實是取指定大小和自身大小的最小值,一般默認的對齊大小是4。

再回到上面的例子,如果默認的對齊大小是4,結構體a的其實地址為0x0000,能夠被最寬的數據成員大小(這裡是int, 大小為4,有效對齊大小也是4)整除,姑char a的從0x0000開始存放佔用一個位元組即0x0000~0x0001,然後是int b,其大小為4,故要滿足2,需要從0x0004開始,所以在char a後填充三個位元組,因此a對齊後佔用的空間是0x0000~0x0003,b佔用的空間是0x0004~0x0007, 然後是short c其大小是2,故從0x0008開始佔用兩個位元組,即0x0008~0x000A。 此時整個結構體佔用的空間是0x0000~0x000A, 佔用11個位元組,11%4 != 0, 不滿足第三個原則,所以需要在後面補充一個位元組,即最後內存對齊後佔用的空間是0x0000~0x000B,一共12個位元組。


http://www.blogfshare.com/memory-alignment.html


一個簡單的演算法就是:

如果n位對齊,那麼n位以下的所有基本類型,地址必須為本類型長度的整數倍;

n位以上的基本類型,保持n位對齊。


這篇博客給的例子挺詳細內存對齊規則之我見


CPU是按字讀取內存。所以內存對齊的話,不會出現某個類型的數據讀一半的情況,需要再二次讀取內存。可以提升訪問效率。

Reference: Purpose of memory alignment


我認為歸根結底是編譯器想通過空間換時間,通過適當增加padding,使每個成員的訪問都在一個指令里完成,而不需要兩次訪問再拼接。

理解有誤的話請無視…


就題主貼出的圖

如果 都是 自帶的數據類型,則結構體內部按照佔用內存最大的數據類型對齊。

E1~E6 都是。 拿E3舉例,E3中long long佔用8位元組(因為題主context int佔用了四位元組,所以都是按int 4位元組計算)。所以E3中 longlong 前面的 a(1位元組), b(2位元組), c( 1位元組 ) 總共是4位元組,因為結構體內部按照最大的8位元組對齊 所以E3 是16位元組。

如果 有自定義數據類型,並且自定義數據類型 比 自帶數據類型佔用內存大時,將自定義數據類型佔用內存擴充至最大自帶數據類型的整數倍進行對齊。


用空間換時間

也可能是編譯器優化不到位


推薦閱讀:

C++內存劃分類型?
在c++中指針是否能夠被完全替代?甚至是不使用指針?
C++ 是 2012 年不宜進入的技術點嗎?
c++虛函數表在運行時候是如何存在的?
cocos2dx開發遊戲,如果可以使用C++做出來,是不是不用lua,全用C++做更好呢?

TAG:C | CC |