mimalloc：面向現代時代的新型高性能可擴展內存分配器

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、數百線程的大型服務等廣泛場景。