mimalloc：面向現代時代的新型高效能可擴充套件記憶體分配器
mimalloc 是微軟研究院開源的現代可擴充套件記憶體分配器，可作為 malloc/free 的即插即用替代品。它程式碼精簡（約1.2萬行），結構清晰，易於整合，透過原子操作實現有界最壞情況分配時間、低空間開銷和低內部碎片。支援高併發和大記憶體場景（如數百GB），已用於 Bing、NoGIL CPython、Unreal Engine 和 Death Stranding 等。
文章情報
要點
- mimalloc 是微軟研究院 RiSE 團隊開發的開源記憶體分配器，最初為 Lean 和 Koka 語言設計。
- 採用執行緒本地堆（theap）和每執行緒獨立頁面，大多數分配釋放無需同步，僅跨執行緒釋放需要原子操作。
- 每個 64KB 頁面維護三個空閒連結串列（free、local_free、thread_free），減少競爭並提高快取區域性性。
- 已廣泛應用於微軟內部服務（如 Bing）及外部專案，在 NoGIL CPython 3.13+ 中作為預設分配器。
為什麼重要
這條新聞值得關注，因為mimalloc 是微軟研究院 RiSE 團隊開發的開源記憶體分配器，最初為 Lean 和 Koka 語言設計。
技術影響
可能影響模型選型、推理成本、產品能力和評測基準。
mimalloc 是微軟研究院（Microsoft Research）RiSE 團隊開發的一款開源、現代、可擴充套件的記憶體分配器，旨在作為傳統 malloc 和 free 的即插即用替代品。其程式碼庫相對精簡，約 1.2 萬行 C 程式碼，內部資料結構清晰，易於構建和整合到其他專案中。mimalloc 提供了有界的最壞情況分配時間（上限取決於作業系統原語）、有界的空間開銷、低內部碎片，並且幾乎完全依賴原子操作來最小化競爭。
mimalloc 最初於 2020 年設計，用於支援 RiSE 團隊開發的前沿程式語言 Lean 和 Koka，這兩種語言均採用新穎的編譯器引導引用計數（參見 Perceus）。其可擴充套件設計在微軟內部的大規模服務中也表現出色。透過與產品團隊的緊密合作，mimalloc 顯著提升了 Bing 等服務的響應時間。如今，mimalloc 已被廣泛應用於微軟內外的大型服務和應用程式，例如作為 NoGIL CPython 3.13+ 的分配器，整合到 Unreal Engine 中，並用於《死亡擱淺》等遊戲。該專案在 GitHub 上開源，擁有超過 12,000 顆星。其 Rust 封裝版本每日下載量超過 10 萬次。
mimalloc 的核心理念是每個執行緒維護自己的執行緒本地堆（theap），每個 theap 擁有一組 mimalloc“頁面”，頁面通常為 64 KiB。每個頁面包含固定大小的塊，按大小類別組織以減少內部碎片。透過為每個執行緒分配獨立的 theap 和頁面，大多數記憶體分配和釋放無需同步，僅當執行緒釋放由另一個執行緒分配的塊時才需要原子操作。
對於小型分配（通常小於 1 KiB），mimalloc 提供了快速路徑。例如，mi_malloc 函式首先檢查大小是否超過閾值，若未超過則直接從執行緒本地頁面的空閒連結串列中彈出塊，無需原子操作。在 x64 架構上，該路徑僅包含少數幾條指令和兩個不常見分支。類似地，mimalloc 也為釋放操作提供了快速路徑：如果釋放的塊屬於當前執行緒，可直接將其推入頁面的 local_free 列表，無需原子操作；否則進入 mi_free_cross_thread，使用原子比較並交換（CAS）將塊推入頁面的 thread_free 列表。由於存在大量頁面，跨執行緒釋放操作通常不會發生競爭。
每個頁面維護三個空閒連結串列：free 列表用於分配、local_free 列表用於同執行緒釋放、thread_free 列表（原子操作）用於跨執行緒釋放。這種設計保證了在固定次數的分配後空閒連結串列會耗盡，從而偶爾觸發較慢的通用分配路徑，用於清理空閒連結串列。由於每個 64 KiB 頁面都擁有這三個連結串列，程式可能擁有數千個空閒連結串列，這對可擴充套件性和快取區域性性至關重要。
mimalloc 的設計靈感來自隨機化演算法。例如，平衡二叉樹可以透過隨機分割來達到足夠平衡，而無需複雜的旋轉操作。類似地，mimalloc 不依賴複雜併發資料結構，而是為每個頁面設定一個執行緒空閒連結串列，任何執行緒都可透過簡單原子 CAS 推入塊。由於連結串列數量眾多，多個執行緒同時向同一頁面釋放塊的機率很低，因此大多數推入操作都是無競爭的原子更新。透過將連結串列組織在 64 KiB 頁面內，分配傾向於在同一頁面內進行，直到頁面滿為止，從而改善快取區域性性。相比之下，如果每個執行緒或程序只有一個空閒連結串列，分配可能重用散佈在各處的最近釋放塊，導致區域性性下降。
在可擴充套件性和記憶體高效共享之間存在基本矛盾。為達到最佳可擴充套件性，應讓每個執行緒獨佔其頁面以減少同步；但這可能導致記憶體浪費，例如一個執行緒擁有大量空閒塊而另一個執行緒需要相同大小的塊時，無法共享或竊取頁面，必須分配新記憶體。反之，如果所有頁面在所有執行緒間透過單一鎖共享，記憶體利用率最優但可擴充套件性喪失。基準測試顯示，標準 Windows 分配器記憶體佔用接近理想（僅多 1.1 倍），但總分配量僅 56 GiB；而另一個高度併發的分配器在分配 262 GiB 資料的同時，提交的記憶體是活躍資料的 4 倍，這在大記憶體工作負載中不可接受。mimalloc 在兩者之間取得了平衡，透過大量頁面和原子操作實現了接近線性的可擴充套件性，同時保持較低的記憶體開銷。
mimalloc 已移植到多個平臺，包括 Windows、macOS、Linux、FreeBSD、NetBSD、DragonFly 以及多種遊戲主機。其清晰的資料結構使得 Sam Gross 等人能夠順利將其採用為 NoGIL CPython 的併發分配器，也使得在其上實現迴圈垃圾回收相對直接。mimalloc 有效適用於從 Koka 或 Lean 等小型應用到記憶體超過 500 GiB、數百執行緒的大型服務等廣泛場景。