Skip to main content

關於記憶體對齊(Alignment)

Opass
Opass
A life well lived

Selection_264.png

什麼是對齊？​

電腦中記憶體的資料放置在某個(2^N)倍數的記憶體位址，稱為對齊。例如4-byte aligned代表該物件的記憶體位址是4的倍數，也就是address % 4 == 0。8-byte aligned代表該物件的記憶體位址是8的倍數，代表8-byte aligned。以4-byte對齊的話，二進位表示的記憶體位址末兩位會是0，以8-byte對齊的話末三位會是0。

為什麼要對齊？​

電腦的記憶體通常會設計成以word-sized進行存取會最有效率。word是存取記憶體最自然的單位。word的大小是電腦架構所定義，一般現代的系統通常word不是4bytes(32bit)就是8bytes(64bit)。早期的電腦記憶體只能以word為單位進行存取，因此所有的記憶體存取都要落在以word為倍數的邊界上。但現代的電腦架構通常能夠存取小至單獨的byte，大至多個word。

為什麼不對齊會沒效率？​

想像一個簡單的情況，假設電腦的系統是以word(4bytes)來存取，假設我們要在記憶體內擺放一個char，一個short，一個int 沒對齊的情況：

unaligned.png

如果要存取int，那麼需要先存取第一個word，再存取第二個word，然後各自做bit shift再組合起來，才有辦法得到int。原本只要存取記憶體一次的，結果現在要兩次，還有額外計算bitshifting的開銷。這是很嚴重的問題，在某些架構上可以造成兩倍以上的效能差異。

對齊的情況：

Aligned.png

我們在第一個char之後加一個padding byte，int符合4-bytes對齊，此時存取就簡單多了，只要一次memory access即可。 上面只是一個簡單的說明，實際不對齊的後果在不同的架構上嚴重程度不同，對於有些RISC架構，例如ARM和MIPS，如果存取未對齊的記憶體處理器會產生alignment fault。特殊用途的處理器例如DSP通常不支援存取未對齊的記憶體位址。一般現代的處理器還是可以存取未對齊的記憶體，但是會產生嚴重的效能降低。非常先進的x86_64處理器可以存取未對齊的記憶體，而且不會產生效能損失。

在參考資料Alignment In C第七頁裡面有簡單的小程式實驗了存取對齊和未對齊的記憶體的效能差異，某些現代intel處理器沒有顯著的影響，但某些環境(Raspberry Pi 2)下存取時間可以差到兩倍以上。

如何對齊？​

自然對齊(natural alignment, aka self-alignment)​

一種常見的對齊方法叫做自然對齊(natural alignment)，也就是直接對齊該資料型態本身的大小。例如short是2個bytes，就對齊2 bytes-aligned，int是4個bytes，那就對齊4 bytes-aligned，long是8個bytes，就對齊8-byte aligned。 但，沒有人規定你一定要自然對齊。

ABI​

事實上，對齊是為了讓系統更有效率，architecture的實作不同，對於對齊的要求就不會一樣。不同架構的對齊需求所要參考的文件叫ABI。 ABI做什麼事情呢？ABI保證了相同的machine code可以移植到不同的機器上執行。這代表了相同的指令集和相同的編譯環境。ABI定義了C語言中留給各平台實作的部份，例如size_t這個type的大小要是幾bytes，int要是幾bytes，以及如何對齊、函式的參數怎麼傳、怎麼回傳，要傳到stack上還是傳到register內，要先放第一個參數還是最後一個參數（這些叫calling convention），如何進行系統呼叫、如何組織的object file等。 在AMD64架構上（其實就是x86_64的別稱而已，一樣的東西），物件是採用自然對齊，多大的物件就對齊多大的記憶體。但在i386架構上，int大小佔4byte，且為4-byte aligned，long也佔4 bytes，亦為4-byte aligned。但long long和double都佔了8bytes，卻也只對齊4byte。

一個有趣的問題​

32位元的系統上，記憶體每次只能存取word(4bytes)，那麼對於佔用8bytes的double，有必要對齊8 bytes嗎？還是對齊4個bytes就足夠了？ 實際上，對齊8bytes還是有一些額外的好處，像是假設cache line是32或64bytes，如果對齊4bytes，則有可能會讓物件剛好落在cache 邊界上， 一部分的物件在cache內，另一部份在外頭，那麼讀取在外頭的word需要花更長的時間。要是這件事情是發生在page的邊界上那會更嚴重。 但相對的，更多的對齊空間會耗費更大的記憶體，這是一個tradeoff。compiler有選項-malign-double 可以讓你把double對齊到8bytes上。 自然對齊有個好處是，他幫你避免掉這種跨越cache邊界的情況。你可以簡單思考，8個bytes的物件如果按照8-byte aligned對齊，那麼是不可能跨越在2^N大小的cache邊界外的（當然N>=3）。

結構的對齊 Alignment of Structure​

關於結構對齊的規則，如果我們站在設計者的角度來想，會有幾個重要的要求

  • 結構內的成員都要對齊
  • 結構本身也要對齊
  • 結構成員本身的相對偏移量必須是固定的，不能因為對齊而產生差別

因此產生了如下規則

  • 每個成員按照各自對齊的最低需求對齊，例如char就對齊到1bytes，short就對齊到2bytes
  • 結構本身的對齊要求等於該結構內最嚴格成員的對齊量，例如在基於x86_64下某個結構最嚴格的對齊是double的8bytes，那該結構本身就要對齊8bytes。
  • 結構本身大小等於該結構對齊的倍數

為什麼要這樣設計？ 如果一個結構本身沒有按照該成員最嚴格的對齊量對齊的時候，會相同的結構在不同的記憶體位址，成員之間的offset會不相同。 舉個最簡單的例子，假設一個結構裡面有兩個成員，一個是

struct S {
  char a;
  int b;
} s;

假設這個結構有照著4bytes對齊，那麼他的位址會長這樣

0x0        0x4
a [] [] [] b [b] [b] [b]
如果沒有對齊，該結構是從0x1的話
0x0  0x1        0x4
[]   a   [] []  b [b] [b] [b]

可以看到a和b之間的offset從3變成2了，會根據結構記憶體開頭的對齊不同而改變。

小附註​

C語言的結構成員的順序會影響struct的大小，這部份compiler並不會自動幫你優化或改變順序以減少struct空間。不優化的原因可以參考這篇。

Reference​