C++ bool 所占的記憶體空間與資料對齊 (data alignment)

前言

這篇文章的內容，緣起於「程式人雜誌」討論區的這個討論串。這個討論串到最後已經失焦了，不過有幾個重點是值得提出來討論的，於是順手整理出幾個重點。

bool 所占的記憶體空間

C++ 內建的標準的型別中，有一個叫 bool 的型別，用來儲存邏輯運算的 true（真）與 false（假）。由於這種型別的變數就只會有 true 或 false 這兩種可能的值，因此，若是我們要儲存這樣的變數的話，理論上來說其實只要 1 個 bit 就夠用了。

然而在實作上，由於不是所有的 CPU 都能夠很有效率地處理單一 bit 的運算，因此通常編譯器會用其他更有效率方式的處理。

C++ 語言標準並沒有硬性規定 bool 要用多大的記憶體空間實作，把這件事留給編譯器自行決定。以 Visual C++ 來說，Visual C++ 4.2 是利用 typedef 將 bool 定義成 int，因此 1 個 bool 變數會占用 4 個 byte 的空間；但在 Visual C++ 5.0 以後的版本，bool 則實作為占用 1 個 byte 的內建型別。在目前 x86 版的 GCC 中，bool 占用的空間也是 1 個 byte；但依據 CPU 架構的不同，可能會有不同的做法。

想要測試系統/編譯器如何實作，可以試著編譯並執行下面這個小程式：

#include <iostream>
using namespace std;
int main(void)
{
    cout << Size of bool =  << sizeof(bool) << endl;
    return 0;
}

資料對齊 (Data Alignment)

首先我們先來看一個小程式：（以下程式均在 x86-64 版的 Ubuntu Linux 上，使用 GCC 編譯執行）

// File: data_align_1.C
#include <iostream>
using namespace std;

struct STRUCT_A {
    bool b;
    int  i;
};

int main(void)
{
    STRUCT_A myVar;
    cout << Size of myVar.b =  << sizeof(myVar.b) << endl;
    cout << Size of myVar.i =  << sizeof(myVar.i) << endl;
    cout << Size of myVar   =  << sizeof(myVar) << endl;
    return 0;
}

編譯與執行結果如下：

$ g++ data_align_1.C
$ ./a.out
Size of myVar.b = 1
Size of myVar.i = 4
Size of myVar   = 8

「等一下！明明 STRUCT_A 中的兩個資料成員 b 和 i 的體積分別是 1 和 4 個 bytes，為什麼合起來變成 STRUCT_A 之後，就變成 8 個 bytes 了呢？」 是啊！為什麼呢？我們來把 myVar.b 和 myVar.i 的記憶體位址印出來看看好了：

// File: data_align_2.C
#include <iostream>
using namespace std;

struct STRUCT_A {
   bool b;
   int  i;
};

int main(void)
{
   STRUCT_A myVar;

   cout << Size of myVar.b =  << sizeof(myVar.b) << endl;
   cout << Size of myVar.i =  << sizeof(myVar.i) << endl;
   cout << Size of myVar   =  << sizeof(myVar) << endl;

   // 印出 myVar 中所有成員的記憶體位址
   cout << endl;
   cout << Addr of myVar.b =  << &myVar.b << endl;
   cout << Addr of myVar.i =  << &myVar.i << endl;
   return 0;
}

執行結果如下：

$ ./a.out
Size of myVar.b = 1
Size of myVar.i = 4
Size of myVar   = 8
Addr of myVar.b = 0x7fff41fe3e00
Addr of myVar.i = 0x7fff41fe3e04

你可以試著多跑幾次，雖然每次跑出來的記憶體位址可能不一樣，但都會符合兩件事實：

1. myVar.i 的位址一定是 4 的倍數，而且 myVar 的位址（也就是 myVar.b 的位址）也是 4 的倍數。
2. 雖然 myVar.b 的體積只有 1 byte，但 myVar.i 的位址卻是在「myVar.b 的位址 + 4」，而非「myVar.b 的位址 + 1」。

這其實是作業系統和編譯器幫你做的安排。那為什麼它們要這樣做呢？這和 CPU 的結構設計有關係。

現代大部份的 CPU 在讀取記憶體內容的時候，並不是 1 個 byte 1 個 byte 讀取的，而是依照其資料線的寬度，一次讀取數個 byte（目前一般來說是 4 個 byte，也就是 32 個 bit）的資料。而且通常讀取位址的起始位置也有限制，例如一次要讀 4 個 byte，那麼開始的位址就必須是 4 的倍數。這個單位我們一般稱為 chunk。

假設我們有個這樣的組語指令：（下面的組語是參考 GNU Assembler 的語法編出來的，實際 CPU 可能沒有 MOVL 這樣的指令，僅供參考）

# 從絕對位址 0x98760003 開始，搬 4 個 byte 的資料到 R9 暫存器
MOVL         $0x98760003, %r8
MOVL         (%r8), %r9

在大部份 RISC 系列的 CPU（如 ARM、PowerPC 等）上並不支援「跨 chunk」存取記憶體。若是你要求 CPU 執行上面的指令的話，CPU 可能會因為無法執行而產生例外狀況 (exception)。至於 x86 系列的 CPU，雖然可以執行，但一般來說執行效率會比較差。

在不支援「跨 chunk 存取記憶體」的 CPU 上，若是硬要做的話，必須要讀取前後的 2 個 chunk 的內容，然後再湊成我們想要的結果：

# 先將 0x98760000 這個 chunk 搬進來，取出 0x98760003 開始的 1 個 byte。
# 假設這顆 CPU 為 little-endian，則此 byte 為最低的那個 byte。
MOVL         $0x98760000, %r8
MOVL         (%r8), %r10
ANDL         $0x000000FF, %r10  # 留下最後的 1 個 byte

# 然後再讀進 0x98760004 那個 chunk，取出 0x98760004~0x98760006 這 3 個
# byte，往高位元 shift 8 個 bit。
MOVL         $0x98760004, %r8
MOVL         (%r8), %r9
SALL         $0x08, %r9         # R9 往左 shift 8 bits

# 最後再把兩次取得的結果組合成我們想要的內容
ORL          %r9, %r10

原本只需要存取記憶體 1 次，現在必須要存取 2 次，還需要加上額外的運算，可想而知的是速度一定會變慢。

因此，為了克服這個問題，作業系統在配置記憶體的時候會以 chunk 為單位；而編譯器在安排資料結構時，也會避免產生必須跨 chunk 存取的狀況。我們上面的例子，myVar.i 被安排在 0x7fff41fe3e04 而不是 0x7fff41fe3e01，就是這個原因。這樣的行為，我們就稱之為資料對齊 (Data Alignment)。

「編譯器一定要這麼雞婆嗎？我就是不想要浪費記憶體空間，就算執行的速度再慢也沒有關係！」 如果你真的有需要的話，沒問題。一般有做資料對齊的編譯器都會提供關掉這個功能的做法。以 Visual C++ 和 GCC 來說，你可以在「不想做資料對齊」的資料結構前後加上兩行 #pragma 指令：

// File: data_align_3.C
#include <iostream>

using namespace std;

#pragma pack(push,1)   /* 加入這一行 */
struct STRUCT_A {
    bool b;
    int  i;
};
#pragma pack(pop)  /* 還有這一行 */

int main(void)
{
    STRUCT_A myVar;
    cout << Size of myVar.b =  << sizeof(myVar.b) << endl;
    cout << Size of myVar.i =  << sizeof(myVar.i) << endl;
    cout << Size of myVar   =  << sizeof(myVar) << endl;

    // 印出 myVar 中所有成員的記憶體位置
    cout << endl;
    cout << Addr of myVar.b =  << &myVar.b << endl;
    cout << Addr of myVar.i =  << &myVar.i << endl;
    return 0;
}

（每一套編譯器的做法可能不太一樣，不過 Visual C++ 和 GCC 在這件事情上剛好有共識。）

輸出的結果如下：

$ ./a.out
Size of myVar.b = 1
Size of myVar.i = 4
Size of myVar   = 5
Addr of myVar.b = 0x7fff41fe3e00
Addr of myVar.i = 0x7fff41fe3e01

嗯，看樣子 myVar.i 的確乖乖地貼在 myVar.b 後面了。很好。

延伸思考

1. 「強制關閉資料對齊功能」所產生出來的資料結構，和一般情況（開啟資料對齊）所產生出來的資料結構，編譯器會產生出不同的機械語言來處理嗎？我們可以要求編譯器產生組語程式，然後再觀察組語程式的內容；或者可以直接從除錯器的反組譯視窗觀察。
2. 8 位元的 CPU（例如 8051）、編譯器（例如 Keil C51）會做資料對齊嗎？

參考資料

• 布林 (Wikipedia)
• Is sizeof(bool) defined? (StackOverflow)
• bool (C++) (MSDN)
• Windows Data Alignment on IPF, x86, and x64 (MSDN)
• Data alignment for speed: myth or reality? by Daniel Lemire