C++ STL 記憶體配置器 深度解析：SGI alloc 設計哲學、雙層架構與原始碼走讀

STL 容器的高效能很大程度仰賴其記憶體配置器。SGI STL 實作的 std::alloc（非標準 allocator，不接受模板參數）採用經典的雙層級配置器設計，巧妙解決小區塊碎片與多執行緒爭用問題。本文結合關鍵原始碼深度剖析其設計思想。

1. 配置器介面概覽

• <stl_alloc.h>：負責原始記憶體 allocate/deallocate/reallocate。
• <stl_construct.h>：負責物件建構/解構 construct/destroy。
• 容器預設使用 std::alloc，無需顯式指定：vector 即合法。

2. 物件建構與解構工具（stl_construct.h）

construct()：Placement New

template 
inline void construct(T1* p, const T2& value) {
    new (p) T1(value);   // placement new：在指定記憶體建構物件
}

destroy()：三層優化

1. 單一物件：顯式呼叫解構子 p->~T()。
2. 範圍解構：destroy(first, last) → __destroy → __destroy_aux。利用 __type_traits 判斷 trivial_destructor，若為真則直接返回（零開銷），否則逐一呼叫單一物件版本。
3. char*/wchar_t* 特化：空函式體，避免無謂呼叫。

3. 第一級配置器：malloc/free 直通車

• allocate(n) → malloc(n)，失敗呼叫 oom_malloc（Out-Of-Memory 處理器）。
• deallocate(p, n) → free(p)。
• reallocate(p, old_sz, new_sz) → realloc(p, new_sz)，失敗呼叫 oom_realloc。

設計細節：因使用 C 的 malloc/realloc，無法直接用 C++ set_new_handler，SGI 自行實作一套 _malloc_alloc_oom_handler 機制模擬 new-handler 行為。

4. 第二級配置器：記憶體池核心

設計哲學

• 區塊 > 128 bytes → 轉交第一級配置器（視為「大塊」）。
• 區塊 ≤ 128 bytes → 記憶體池管理，避免碎片與管理開銷。

核心資料結構

• 16 條 free-list：分別管理 8, 16, 24, ..., 128 bytes（8 的倍數對齊）。
• union 節點：union obj { union obj* free_list_link; char client_data[1]; }; —— 利用「柔性陣列」技巧，同一記憶體區既能串聯 free-list，又能供用戶使用。
• 記憶體池：靜態 char* start_free, *end_free，向系統申請大塊（預設 20 × 區塊大小），切分後掛入對應 free-list。

配置流程 allocate(n)

1. 若 n > 128 → malloc_alloc::allocate(n)。
2. 對齊至 8 的倍數 n = ROUND_UP(n)，找對應 free-list 索引。
3. 若 free-list 非空 → 取頭節點回傳。
4. 若空 → refill(n) 向記憶體池申請 20 區塊（可調），切分掛入 free-list 後回傳一塊。
5. 記憶體池不足 → chunk_alloc 嘗試從系統 malloc 取得大塊，失敗則遍歷較大 free-list 拆分借用，仍失敗則拋 bad_alloc。

釋放流程 deallocate(p, n)

1. n > 128 → malloc_alloc::deallocate(p)。
2. 否則依 n 找 free-list 索引，將 p 插入表頭（LIFO），極快 O(1)。

5. 多執行緒考量

• SGI STL 使用 _STL_THREADS 巨集控制：定義時啟用 __malloc_lock/__malloc_unlock（通常映射到 pthread_mutex）。
• 第二級配置器的 free-list 操作同樣受鎖保護。

6. 關鍵優化總結

7. 現代 C++ 視角

• C++11 起標準 std::allocator 已支援狀態與型別感知，SGI alloc 為歷史實作。
• 現代高效能配置器（jemalloc, tcmalloc, mimalloc）同樣採用 Thread-local Cache + Size Class 思想，與 SGI 設計異曲同工。
• 理解 SGI alloc 有助於掌握配置器核心設計模式，對自訂配置器、效能調優極具參考價值。

1. 上一篇文章： PIC 單片機 C 語言喂狗完全指南：各系列編譯器對照表與嵌入組語寫法
2. 下一篇文章： C 語言開發環境從零開始：GCC 編譯四階段、常用參數與分步建構實戰

關於C語言

C# 獲取當前進程 Hash 值的方法 (三) 執行結果驗證

驗證說明 Visual Studio 偵錯模式下，實際執行進

C# 程式設計利器之二：結構與列舉——FontStyle 列舉實際應用

.NET Framework 列舉基底類別 System.E

C語言小專案：自動生成小學四則運算練習題目程式

C語言小專案：自動生成小學四則運算練習題目程式 本程式實作一

C# 例外處理（二）：finally 保證執行、goto/return/break 穿透、try-catch-finally 完整模式

finally 區塊 在 try 區塊結束時必定執行，不論離