2012年10月17日 星期三

Data Structure Alignment

今天同事分享了 Data Structure Alignment
寫 C/C++ 寫了六年多,竟然完全都不知道這回事 =口=
於是私下趕快研究了一下


Data Structure Alignment 究竟是何物?
它是為了加快執行速度而有的一種方式
由於 CPU 架構的關係,在讀 memory 的時候會以一個 word 為單位(在 32-bit 系統是4 bytes 為1個 word),因此 data 在儲存時,memory offset 便會是 word size 倍數,藉此增加效能

Data Structrue Alignment 分成兩個部分:Data Alignment 與 Data Structure Padding
Data Alignment 即是上述所述,data 的 memory offset 會是 word size 的倍數
Data Structure Padding 則是在 data structure 尾巴塞入一些無意義的 bytes,使下一個 data structure 的 memory offset 能夠對齊

這東西在實作上會有怎樣的影響,讓我們來看看
在一個 32-bit 系統,常見的 C/C++ compiler 的 default alignments為:

  • char (1 byte): 1-byte aligned
  • short (2 bytes): 2-byte aligned
  • int (4 bytes): 4-byte aligned
  • float (4 bytes): 4-byte aligned
  • double (8 bytes): 8-byte aligned (in windows) / 4-byte aligned (in Linux)
  • Any pointer (4 bytes): 4-byte aligned
C/C++ compiler 在 alignment 時最大原則:以目前最大的 alignment size向前 padding,向後 allocate

這是什麼意思?用以下的範例來讓大家了解

1.

struct MixedData 

 char data1; 
 short data2;
 int data3; 
 char data4;
};

Structure's Size: 12 bytes
Memory Offset:






  • data1:type 是 char,char 是 1-byte aligned,意思是其 memory 位置開頭必須是1 的倍數,所以就放在 0x00 的位置(假設是從 0x00 開始)
  • data2:type 是 short,short 是 2-byte aligned,所以其 memory 位置開頭必須是 2的倍數,因此 0x01 就會被放置一個 1 byte 的 padding,然後在 0x02 放 data2。因為 short size 比 char size 大,因此會 allocate 2-byte memory
  • data3:同理,4-byte aligned,allocate 4-byte memory
  • data4:雖然 size 是 1 byte,但由於目前最大的 alignment size 為 4 bytes,因此會 allocate 4-byte memory,後面的 3 bytes 就會是 padding

2.

struct ReorderedMixedData   // after reordering
{
    char data1;
    char data4; // reordered
    short data2;
    int data3;
};

Structure's Size: 8 bytes
Memory Offset:


這範例我就不解釋了,各位可以試著自己解釋看看

到這邊我們可以發現,在宣告 structure 時
成員的順序其實是會有所影響的
因此要宣告一個好的 structure,應該要減少 padding來降低 structure 的 size

3.

#pragma pack(push)  // push current alignment to stack 
#pragma pack(1)     // set alignment to 1 byte boundary

struct MyPackedData
{
    char data1;
    short data2;
    int data3;
    char data4;
};

#pragma pack(pop)   // restore original alignment from stack

programmer 難道沒辦法控制 alignment 嗎?
答案是可以的
#pragma pack(n) for n = 1, 2, 4, 8, 16, ...
這個語法便可以更改預設的 alignment

在範例中,我們設定 alignment pack size 為 1 byte
因此原本 data2 和 data4 會出現 padding 的情況就消失了
實際結果如下:
Structure's Size: 8 bytes
Memory Offset:




大家可以試試看把 n 調成其他 2 的倍數
觀察 Memory Offset 與 structure size 會有什麼變化
要注意的是 #pragma pack(n) 雖然可以變的更 compact 但會降低效能
另外,如果寫了一個 pack 過的 structure 給別人使用
別人不知道這件事的話,他去參照這個 structure 便會導致 crash
因此建議盡量不要使用這個語法,還是用 default 就好,以免造成問題

記得:宣告 structure 時,成員的順序看起來沒有影響,但其實是有的
一個好的 structure 應該要減少 padding 產生,這樣便能降低 structure 的大小

範例程式

Reference:

[1] "Data Structure Alignment", Wikipedia