Data structure alignment 的對齊方式

1. Data alignment
Data alignment是為了加快CPU存取記憶體的速度，在32 bit的CPU架構中，CPU存取記憶體會以32 bit為單位，所以在將資料放入記憶體的方式，
Compiler會將資料在記憶體中的排列方式做最佳化，會以32 bit為單位，一個word為單位來排列對齊，目的是為了增加CPU處理記憶體的效能。


2. Data structure alignment被分為兩個部份
Data alignment: 意指資料放入記憶體時，是以一個word為單位。
Data structure padding: 為了對齊在記憶體中的資料，有可能在一筆資料後加入無意義的padding，以此讓下一筆資料可對齊。

3. 在一般32 bit x86架構的PC，通常變數型態會以下列方式對齊
A char (one byte) will be 1-byte aligned.
A short (two bytes) will be 2-byte aligned.
An int (four bytes) will be 4-byte aligned.
A long (four bytes) will be 4-byte aligned.
A float (four bytes) will be 4-byte aligned.
A double (eight bytes) will be 8-byte aligned on Windows and 4-byte aligned on Linux
  (8-byte with -malign-double compile time option).
A long long (eight bytes) will be 4-byte aligned.
A long double (ten bytes with C++Builder and DMC, eight bytes with Visual C++,
  twelve bytes with GCC) will be 8-byte aligned with C++Builder, 2-byte aligned with DMC,
  8-byte aligned with Visual C++, and 4-byte aligned with GCC.
Any pointer (four bytes) will be 4-byte aligned. (e.g.: char*, int*)

在一般64 bit x86架構的PC，有些變數型態的大小會不一樣
A long (eight bytes) will be 8-byte aligned.
A double (eight bytes) will be 8-byte aligned.
A long long (eight bytes) will be 8-byte aligned.
A long double (eight bytes with Visual C++, sixteen bytes with GCC)
  will be 8-byte aligned with Visual C++ and 16-byte aligned with GCC.
Any pointer (eight bytes) will be 8-byte aligned.

4. 範例一
struct test { 
    char a;
    short b;
    int c;
    char d;
};

 ________________________________________________________________
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
| a   p | b     | c                 | d   p   p   p |           |
|___ ___|___ ___|___ ___ ___ ___ ___|___ ___ ___ ___|___ ___ ___|

a: 型態char的大小為1 byte，1-byte aligned，記憶體的起始位置需為 1 的倍數，a 被放在0x0。
b: 型態short的大小為2 bytes,2-bytes aligned，記憶體的起始位置需為 2 的倍數，因此在a 變數後加了1 byte的padding，b 被放在0x2。
c: 型態int的大小為4 bytes，4-bytes aligned，記憶體起始位置需為 4 的倍數，直接放在0x4。
d: 型態char的大小為1 byte，1-byte aligned，記憶體的起始位置需為 1 的倍數，因為現在最大alignment size為 4，
   因此在 d 變數後加了3 bytes的padding，d 被放在0x8。
p: padding

這個structure佔記憶體空間為 12 bytes，浪費了 4 bytes的記憶體空間。

5. 範例二
struct test { 
    char a;
    char b;
    short c;
    int d;
};

 ________________________________________________________________
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
| a | b | c     | d                 |                           |
|___|___|___ ___|___ ___ ___ ___ ___|___ ___ ___ ___ ___ ___ ___|

a: 型態char的大小為1 byte，1-byte aligned，記憶體的起始位置需為 1 的倍數，於是 a 被放在0x0。
b: 型態char的大小為1 byte，1-byte aligned，記憶體的起始位置需為 1 的倍數，於是 b 被放在0x1。
c: 型態short的大小為2 bytes，2-bytes aligned，記憶體起始位置需為 2 的倍數，於是直接放在0x2。
d: 型態int的大小為4 bytes，4-bytes aligned，記憶體起始位置需為 4 的倍數，於是直接放在0x4。
p: padding

這個structure佔記憶體空間為 8 bytes，浪費了 0 byte的記憶體空間。

如果在設計structure時，有考慮到data alignment的問題，可避免padding的產生，也節省了記憶體空間的浪費。

6. 範例三
#pragma pack(push) /* push current alignment to stack */
#pragma pack(1) /* set alignment to 1 byte boundary */

struct test { 
    char a;
    short b;
    int c;
    char d;
};

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


 ________________________________________________________________
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
| a | b     | c             | d |                               |
|___|___ ___|____ __ ___ ___|___|___ ___ ___ ___ ___ ___ ___ ___|

這個structure佔記憶體空間為 8 bytes，浪費了 0 byte的記憶體空間。

如果在程式碼的前後pragma pack，就不會加上padding，將可避免記憶體空間的浪費。

7.結論
7.1 宣告 structure 時，成員的順序會影響到structure的大小，設計structure時，有考慮到data alignment的問題，
    可避免padding的產生，也節省了記憶體空間的浪費。
7.2 #pragma pack(n)，如果 n 比 structure 中最大成員的size還大 那還是會用最大成員的size來對齊。

8. 參考來源
https://en.wikipedia.org/wiki/Data_structure_alignment
http://mark-shih.blogspot.tw/2012/10/compiler-data-alignment.html