mimalloc は、Microsoft Research の RiSE グループが開発したオープンソースのモダンでスケーラブルなメモリアロケータであり、従来の malloc や free のドロップイン代替として機能します。コードベースは約12,000行のC言語と比較的コンパクトで、内部データ構造は明確に設計されており、他のプロジェクトへのビルドや統合が容易です。mimalloc は、OSプリミティブに依存する境界のある最悪ケース割り当て時間、境界のある空間オーバーヘッド、低い内部断片化、そしてほぼ専ら原子操作に依存することで最小限の競合を実現します。
mimalloc は2020年に、RiSE グループが開発した最先端のプログラミング言語 Lean および Koka のための高速アロケータとして設計されました。これらの言語は、革新的なコンパイラ誘導型参照カウント（Perceus を参照）を使用します。mimalloc のスケーラブルな設計は、マイクロソフトの大規模サービスでも非常に良好に機能することが証明されました。製品チームとの緊密な協力を通じて、mimalloc は Bing などのサービスの応答時間を大幅に改善しました。現在、mimalloc はマイクロソフト内外の大規模サービスやアプリケーションで広く使用されており、NoGIL CPython 3.13+ のアロケータとして機能し、Unreal Engine に統合され、Death Stranding などのゲームでも使用されています。このプロジェクトは GitHub でオープンソース公開されており、12,000 以上のスターを獲得しています。Rust ラッパーだけでも1日あたり10万以上のダウンロードがあります。
mimalloc の核心的な設計原則は、各スレッドが独自のスレッドローカルヒープ（theap）を維持することです。各 theap は一連の mimalloc「ページ」（通常64 KiB）を所有します。各ページは固定サイズのブロックを含み、内部断片化を低減するためにサイズクラスに編成されています。各スレッドに独自の theap とページセットを割り当てることで、メモリの割り当てと解放は通常、同期なしで進行します。原子操作は、スレッドが別のスレッドによって割り当てられたブロックを解放する場合にのみ必要です。
小さな割り当て（通常1 KiB未満）の場合、mimalloc は高速パスを提供します。たとえば、mi_malloc 関数は最初にサイズがしきい値を超えているかチェックし、超えていなければスレッドローカルページのフリーリストからブロックをポップします。このパスは原子操作を必要としません。x64 アーキテクチャでは、このコードは2つのまれな分岐を持つ少数の命令に変換されます。同様に、mimalloc は解放のための高速パスも提供します。ブロックが現在のスレッドに属するページに解放される場合、ページの local_free リストにプッシュするだけで原子操作は不要です。そうでない場合は、mi_free_cross_thread 関数に入り、原子比較交換（CAS）を使用してブロックをページの thread_free リストにプッシュします。ページ数が多いため、クロススレッド解放の競合は稀です。
各ページは3つのフリーリストを維持します：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 を採用し、またその上にサイクルガベージコレクションを実装することも比較的容易です。mimalloc は、Koka や Lean のような小規模アプリケーションから、500 GiB を超えるメモリと数百のスレッドを持つ大規模サービスまで、幅広いシナリオで効果的です。