使用 C 語言從零開始構建記憶體配置器

記憶體配置是系統程式設計中最基本的面向之一。雖然大多數開發者依賴標準函式庫的 malloc 和 free，但對於任何想要優化效能、減少記憶體碎片化並理解堆積（heap）如何管理的人來說，了解這些函式在底層是如何運作的至關重要。使用 C 語言從零開始構建一個記憶體配置器，為軟體如何與硬體及作業系統互動提供了一個關鍵的視窗。

記憶體配置的核心邏輯

記憶體配置器的核心是管理作業系統提供的大塊記憶體。配置器的主要目標是追蹤該記憶體中哪些部分已被使用，哪些是空閒的。當使用者請求大小為 $N$ 的區塊時，配置器必須找到一個至少具有該大小的合適空閒區塊，並將其標記為已使用。當使用者呼叫 free 時，配置器必須將該區塊標記為已歸還至可用池中。

實作這項功能需要一個管理結構——通常是空閒區塊的鏈結串列（linked list）——來追蹤可用空間。這個過程涉及導覽這些串列、尋找足夠大的區塊（使用如 first-fit 或 best-fit 等策略），並且如果區塊明顯大於請求的大小，則可能需要將其分割，以避免浪費空間。

學術與實務應用

實作自定義配置器是頂尖大學系統程式設計課程的必修內容。例如，卡內基美隆大學（CMU）15-213 課程與哈佛大學 CS 61（系統程式設計與機器組織）的學生都會將其作為核心練習。這些作業通常會促使學生意識到速度、利用率與碎片化之間複雜的權衡。

社群中一個有趣的見解揭示了操縱基準測試（benchmarks）的危險性。在 CMU 的一項作業中，一名學生指出，透過識別測試套件中分配比例異常的特定區塊大小，他們能夠透過為該大小硬編碼（hardcoding）一個特定的空閒串列，從而登上排行榜的首位。這提醒了我們，合成基準測試往往無法捕捉到真實世界的用法模式。

針對效能的專用配置器

雖然像 malloc 這樣的通用配置器功能強大，但在特定環境下，專用配置器可以提供顯著的效能增益。

池化配置器 (Pool Allocators)

池化配置器（或固定大小區塊配置器）是通用配置器的替代方案。它們不搜尋鏈結串列，而是使用帶有索引陣列的預配置池。這種方法具有幾個優點：

  • 常數時間複雜度：透過索引的原子遞增或遞減，配置與釋放都是 $O(1)$ 操作，消除了遍歷鏈結串列的需求。

  • SMP 與無鎖設計：透過使用原子操作，這些配置器可以在對稱多處理（SMP）環境中運作，而不需要昂貴的鎖，從而減少競爭。

  • 跨平台相容性：因為它們簡單且依賴基本的原子操作，因此可以在不同的作業系統（如 Linux、QNX 和 VxWorks）以及核心與使用者空間中實作。

WebAssembly 中的佔用空間優化

與此同時，配置器本身的尺寸也是一個關鍵指標。對於開發 C-to-WebAssembly (Wasm) 模組的開發者來說，配置器的二進位檔案大小會顯著影響最終模組的大小。使用像 walloc 這樣的極簡配置器而非像 emmalloc 這樣較大的替代方案，可以將模組大小從 27kb 減少到 17kb——對於網頁部署來說，這是一個實質性的縮減。

結論

無論是作為大學教室中的教學工具，還是作為系統工程領域中的高效能工具，構建一個記憶體配置器都是系統程式設計師的成年禮。它迫使開發者面對記憶體碎片化的現實、中繼資料（metadata）的開銷，以及針對目標環境的特定限制選擇正確配置策略的重要性。

Sources