6月20日、mimallocというメモリアロケータが公開されました。 mimallocは関数型言語の処理系のような、小さな確保と解放を繰り返す状況で性能を発揮するアロケータです。
microsoft/mimalloc: mimalloc is a compact general purpose allocator with excellent performance.
“less than 3500 LOC” （他のmallocは数万行あったりする）ということで、頑張れば自分でも読めるのではないかと思いました。 そこでまずは論文を読んで大まかな仕組みを理解しようと思います。
なぜかはわかりませんが、とてもスラスラ読むことが出来る論文でした。 この論文ではmimallocの実装と評価をすることで、 参照局所性を考えて、Free List Shardingを用いて作ったメモリアロケータが高い性能を出せることを示しています。 以下Free List Shardingについて簡単な要約をします。
Free List Sharding
mimallocで特に重要な機能が “free list sharding” です。 フリーリストをいくつかにsharding（水平分割）することによって、参照局所性の向上、確保時の条件分岐の削減など、 様々な問題を解決しています。
Allocation Free List
解放された領域を連結リストにして、あとで再利用するときに高速にアクセスできるようにするのがフリーリストです。 この論文では確保するアドレスの参照局所性を問題にしています。
確保と解放を繰り返していると、フリーリストがあちこちに飛ぶことがあります。 同時期に呼ばれたmallocで確保したメモリは同時期に使われることが多いので、 このままだと参照局所性が低下してしまいます。 参照局所性が低下すると、データがCPUのキャッシュに載らないなどの理由から性能が悪化します。
そこでメモリ領域を64KiB程度の大きさのpageに分割し、各ページに別々のフリーリストを作りました。 これによって同じフリーリスト内のアドレスは場所が近くなり、参照局所性が向上します。
Local Free List
mimallocでは処理を “fast path” と “slow path” の2つに分け、 フリーリストが空になったときのみslow pathを呼び出すようにしています。 しかし定期的に行いたい処理があるので、 確保と解放を繰り返してフリーリストが空にならないような状況でも定期的にslow pathが呼ばれるようにしたいです。
そこでフリーリストを更に分割し、解放した領域を追加していくリストと、 再利用するために領域を取り出すリストにして、取り出すリストが空になったら役割を交代させるようにします。 増えていくだけのリストと、減っていくだけのリストにフリーリストを分割するのです。 こうすることで、「フリーリストが空になったか」と「ある一定回数程度mallocが呼ばれたか」 の判定がひとつの条件分岐で行えるようになり、fast pathを遅くすることなしに定期実行機能を実現できるようになります。
Thread Free List
mimallocではセグメント（に属するページ）はスレッドに属し、他のスレッドがページの領域を確保しに来ることはありません。 しかし解放は他のスレッドから出来るようにする必要があります。 これをロックフリーに実現するため、さらに新しいフリーリストを作ります。
このフリーリストも追加専用です。 thread free listへの要素の追加はアトミックに行うことができます。 その後、上記のlocal free listで実現したタイマーでslow pathが呼ばれた際、thread free listを回収します。 これも根本のポインタを操作するだけでいいのでアトミックに行えます。 そうして回収したリストをlocal free listにマージするのです。
Full List
ここまでのものを実際に実装して試してみると一部のベンチマークで性能が悪くなったので、 それを解決するためにさらに新しいフリーリストを作っています。 マルチスレッド環境で競合を発生させることなくロックフリーにfull listを実現するため、 thread free listのポインタ下位2ビットにフラグを埋め込んだりしています。
読書メモ
以下、読みながら書いた読書メモです。
Mimalloc: Free List Sharding in Action
Modern memory allocators はパフォーマンス、セキュリティ、コンカレンシー等の様々な要求、そしてコンテキストに応じて変化するアプリケーション特有の要求のバランスを取らなければならない。 アロケータのユースケースとしてSwiftやPythonのような自動メモリ管理を備えた言語処理系がある。 言語処理系の参照カウント式メモリ管理で使われるアロケータとして既存のアロケータより高い性能を発揮するMimallocを紹介する。
Mimallocは様々なイノベーションを含む。
- page-local sharded free list
- 空間局所性が良くなる、競合を回避できる。 処理が高速なfast pathとそうでないパスに分かれる。
- “temporary cadence”: fast pathから定期的に出て処理が出来る
プログラミング言語LeanとKokaの処理系とRedis においてmimallocは既存のアロケータより高速に動作した。
- tcmallocより7%高速
- jemallocより14%高速
1. INTRODUCTION
LeanとKokaのランタイムを開発するに当たって現在のアロケータには問題があった。 2つは関数型言語であり、寿命の短いアロケーションを大量に行う。 Leanでは、小さいアロケーションのために独自のアロケータを作っていた。
SwiftやPythonのランタイムシステムはメモリ管理に参照カウント方式を採用している。 大きなデータ構造の解放にかかる時間を抑えるために参照カウントの"deferred decrementing"が必要だった。 “deferred decrementing"をresumeするのにベストなタイミングはmemory pressureがある時である。 そのため、“deferred decrementing"実現のためにはアロケータの協力が必要である。
これらの問題に対処するため、新しいアロケータを作った。
- free list sharding: 小さな領域(mimalloc page, usually 64KiB)ごとにフリーリストをもつ。 これによりpageがいっぱいになるまではmallocの空間局所性が保たれる。
- thread-free list: mallocのfast pathにおいてロックや競合を回避する。 バッチ処理によってアトミックに解放を行う
- local-free list: フリーリストが空になるとlocal-free listが新しいフリーリストになる。 これにより重い処理が償却される。 fast pathの処理を減らすことが出来る。
- 確保と解放のコードパスは最適化され、それ以外のルーチンは延期する。
fast pathの条件分岐を簡単にするためデータ構造はregularになる。
この設計はまた特殊ケースを減らしコードの再利用を増やすことで、コードを一般化させシンプルにする。
これによりライブラリは3500 LOC以下になり、これは他のアロケータよりも遥かに小さい。
- tcmalloc: ~20k LOC
- jemalloc: ~25k LOC
- ロックは存在せず、スレッドのインタラクションはアトミックな操作で完結する。 これによりアロケーションの最悪計算時間が抑えられ、 メタデータのオーバーヘッドは約0.2%、 メモリの無駄はたかだか16.7%(1/8)になる。
様々なアロケータとmimallocを様々なベンチマークで比較した結果、安定して他のアロケータよりも好成績を治めた。 Leanの小さいオブジェクト用独自アロケータよりも高い性能を達成した。 redisでもいい感じだった。
歴史的にアロケータはアロケータの実行時間の削減、メモリ使用量の削減、複数スレッドでのスケーリングを問題として設計されてきた。 アプリケーションの参照局所性を重視した設計は少なかった。 例えばVAMやPHKmallocの初期バージョンもシーケンシャルなアロケーションが同じページに来るようにフリーリストシャーディングを使っていた。 mimallocもアプリケーションの参照局所性を改善しており、そこからさらにVAMになかった機能を追加している。 参照局所性の改善にフォーカスしたアロケータがパフォーマンスと並行スケーラビリティを実現することを示した。
mimallocはCで書かれておりいろんなプラットフォームで動く。 シンプルでレギュラーなコードベースにより、言語のランタイムに組み込みやすくなっている。
2. FREE LIST SHARDING
2.1 The Allocation Free List
関数型言語は小さなオブジェクトの確保と解放を大量に繰り返す傾向がある。 多くのアロケータはサイズクラスあたりひとつのフリーリスト使い、これは局所性の悪化を招き、 ひとつのデータ構造 (リンクリスト等) に属するオブジェクトがヒープ全体に散らばってしまうことになる。
関数型言語においてヒープはそのような状態になりがちである。 局所性の改善のために、mimallocはfree list shardingを使う。 これはヒープをpage (OSのそれとは別のもの) に分割し、pageごとにフリーリストを作る。 (小さいオブジェクト用のページは通常64KiBである)
これにより局所性が改善され、mimallocの性能が大きく改善するという仮説を立てた。
これをテストするために、Leanコンパイラで実験をした。 実装をシャーデッドフリーリストに置き換えただけで、1GiBのヒープ内のデータ構造のベンチマークで25%以上の性能改善が見られた！ 先行研究であるVAMアロケータでも局所性の改善によるL2キャッシュミスの減少が計測されている。
2.2 No Bump Pointer
ページ内からアロケーションをする際は単にページのフリーリストからpopする。
fast pathには1つの条件分岐 (フリーリストは空か？) とpopだけがある。 フリーリストが空のときはmalloc_generic (slow path) を呼ぶ。 used変数をインクリメントしているのはページ内のすべてのオブジェクトが開放されているかを効率的に判定するためである。 多くのアロケータはreap designを採用しており、これはbump pointer (bump pointer=ページの終わりのアドレスと比較演算をしてページが満杯か判定する手法。 先頭アドレスを確保サイズ分加算することでメモリの確保をする) を使い初期状態でページは空である。 mimallocでもbump pointerを試してみたがベンチマークが2%悪くなった。 おそらくfast path内の条件分岐が増えてしまうためだろう。 分岐予測もできないし、確保されたメモリのアドレスがが予測しやすいというセキュリティリスクもあるのでbump pointerはなくした。
2.3 The Local Free List
KokaやLeanのランタイムにおいては最悪確保時間、最悪解放時間に上限がほしい。 特に大きなデータ構造を開放する際の再帰的解放呼び出し (free call) の数は限られていてほしい。 KokaとLeanはランタイムで参照カウントを採用している (SwiftやPythonと同じように)。 しかしどの言語でも参照カウントは大きなデータ構造で問題が起こる。 参照カウントにおける解放呼び出し数の制限は単純なリミットカウンタと、 残りのポインタをdeferred decrement listに突っ込む事で実現できる。
いつこのdeferred decrement listからの解放を再開すればいいだろうか？
ベストなタイミングはアロケータがさらなるフリースペースを探しているときであり、
そのためアロケータの協力が必要になる。
mimallocアロケータはユーザが定義したコールバックdeferred_freeをそのようなときに呼び出す。
これはページのフリーリストがからのときに呼ばれるmimallocの
slow pathmalloc_genericルーチン内で呼ばれる。
しかしこの汎用ルーチンが定期的に呼ばれるという保証がないためまだだめだ。 ユーザはページ内で解放と確保を繰り返し、ページのフリーリストが空になることはないかもしれない。 一定回のアロケーションごとに汎用ルーチンが呼び出されるようにする方法が必要である。
したがって、フリーリストをさらに水平分割する。 local free listを各ページに追加して、 regular free listからアロケートする間に開放したオブジェクトを (regular free listではなく) local free listに配置する。 こうすることでフリーリストが一定回数のアロケーションの後空になることを保証できる。 汎用ルーチンではローカルフリーリストをフリーリストにする。
MEMO: つまり2つのフリーリストを用意して、1つからは取り除き、もう1つには追加する。 取り除いている方が空になったら役割を交代する。
fast pathには条件分岐は増えておらず、仕事はすべてslow pathが行っていることに注目。
deferred_freeは一定回数のアロケーションまでに必ず呼び出されることが保証され、
これは決定論的heartbeatとしても使うことが出来る。
Leanではスレッドの処理に時間がかかっているときのタイムアウト処理をするためのポータブルなタイマーとして使っている。
このケースで、マシン内で決定論的でないために実時間をタイマーにすることはできない。
2.4 The Thread Free List
mimallocにおいてページはスレッドローカルなヒープに属し、アロケーションは常にローカルヒープ内で行われる。 ここでスレッドローカルなアロケーションにロックは不要である。 しかし任意のスレッドがオブジェクトを開放できる。 スレッドローカルな解放をロック無しに実現するために、 フリーリストをさらに水平分割し、thread free listを各ページに追加する。 他のスレッドはこのページのオブジェクトをこのリストに追加して開放できる。
非ローカルな解放では、スレッドフリーリストに開放したオブジェクトをアトミックに追加する操作を行う。
sharded thread free listの長所は、異なるページを解放しているスレッドどうしが競合しないため、 スレッド間の競合が減ることである。 現在のアーキテクチャでは競合しないアトミック操作は効率的であり、 chche consistency protocolの一部として実装されている。
汎用ルーチンでスレッドフリーリストを回収して、ローカルフリーリストに追加する。
MEMO: スレッドフリーリストの回収: リストの先頭ポインタを取得、同時に先頭ポインタをNULLにする。 この一連の操作はアトミックに行える。
スレッドフリーリスト全体の移動は一度に行われるため、 非ローカル解放の呼び出しは効率的にバッチ処理される。 これは確保するスレッドと解放するスレッドに分かれているような asymmetric concurrent work loadにおいて特に重要である。 snmallocはこのような状況において動作するように作られ、 こちらもバッチによって高価な同期処理を削減している。
3. IMPLEMENTATION
sharded listsを除き、全体の設計は他のsize-segregated thread-caching allocatorと似ている。
3.1. Malloc
オブジェクトを確保するとき、mimallocはまずthread local heap (tlb) へのポインタを得る。 1Kb未満の小さなオブジェクトのために、 ヒープは利用可能なページへ直接アクセスするためのポインタの配列を持っている。
小さいオブジェクトのためのmalloc_smallは条件分岐を1つだけ含む効率的なアセンブリになる。
ページとそのメタデータはすべて大きなsegment (他のアロケータではslabやarenaとも呼ばれる) に置かれる。 セグメントの大きさは4MiB (512KiBを超える巨大オブジェクト用には更に大きくなる) であり、 最初のページはメタデータとガードページの大きさ分だけ小さくなっている。 ページには3つのサイズがある。
- 8KiB未満のオブジェクト用: ページサイズは64KiBでセグメント内に64個ある
- 512KiB未満の大きなオブジェクト用: ページはセグメント全体を占め、ページはセグメントに1つ
- 512KiB以上の大きなオブジェクト用: ページは必要なサイズまで大きくなる
大きなオブジェクトにもページとセグメントを使うのはデータ構造を単純化しコードサイズと複雑性を削減、 特殊ケースの少ない一貫性のあるインターフェースを作るためである。 これによってmimallocのコードサイズは他のアロケータよりも小さくなっている。
3.2. Free
ページとそのメタデータはセグメント内に確保される。
これはOSの高価なアロケーションコールを削減するというのが主な理由だが、それだけではない。
ポインタを開放したとき、そのポインタに関するページのメタデータにアクセスしないといけないのだ。
mimallocのセグメントは4MiB境界でアラインされている。
ポインタpを持っているセグメントは下位ビットをマスクすることでわかる。
free関数はまず開放するポインタpの下位ビットをマスクすることでセグメントポインタを得る。
ポインタがNULLの場合、セグメントもNULLになり、それをチェックする。
アセンブリでは比較演算が削除されビット積になる。
ページ番号は差を取りpage_shiftだけシフトすることで得られる。
小さいページではpage_shiftは16 (=64KiB) になる。
大きいページでは22 (=4MiB) になり、インデックスは常にゼロとなる。
これもfast pathで特殊ケースと分岐を避けるためのuniform representationである。
主な条件判定はこれがスレッドローカルな解放か、他のスレッドからの解放かを判定するものである。
mimallocはthread_id()を呼び出し現在のスレッドのIDを取得し、
セグメントのthread_idフィールドと比較する。
多くのオペレーティングシステムでスレッドのIDは、
スレッドローカルな固定のアドレスから非常に効率的に読み出される
(64-bit Intel/AMD上のLinuxではfsレジスタのオフセット0にある)。
スレッドローカルか否かに応じてthread_freeまたはlocal_freeにオブジェクトがプッシュされる。
スレッドローカルな解放の場合、ページ内のオブジェクトがすべて開放されているかを確認し、
その場合ページを開放する。
このページ解放処理はスキップしてslow pathで行うことも出来るが、
特定のワークロードによっては可能な限り速くページを利用可能にしたほうが効率的なこともある。
ページ内のすべてのオブジェクトが開放されている場合、
thread sharedなthread_freedカウンタはバリアなしに読むことが出来る。
3.3. Generic Allocation
汎用アロケーションルーチンmalloc_genericは定期的に呼ばれることが保証された"slow path"である。
このルーチンはアロケーションで償却される高価な操作を行うことがあり、ガベージコレクタ的なアレである。
汎用ルーチンはサイズクラス内のページすべてを線形に操作し、オブジェクトを含まないページを解放する。 これは開放されたオブジェクトを持つページが見つかるまで続く。 実際の実装ではページをすぐには解放せず、少しの間将来のためにとっておく。 最悪アロケーション時間を制限するために、開放されるページの最大数が決められている。 ページにフリースペースが見つかった場合、そのページは次回の探索で最初に訪れる。
3.4. The Full List
SpecMark gcc benchmarkでは他のアロケータに比べ30%の低速化を計測している。 これは「銀の弾丸」が存在しないこと、 産業向けメモリアロケータは特定のワークロードでのみ現れるさまざまなコーナーケースを取り扱う必要があるということを示している。
gcc benchmarkでは独自アロケータを使っており、 最初に大きなオブジェクトを大量に確保して長期間保持していた。 これは汎用アロケーションルーチンで毎回線形にトラバースされる大量 (18000を超える) の満杯のページを発生させた。
すべてのページが満杯のfull listを、 そのページが解放されるまで通常のページリストから分離することでこの問題を解決した。 gcc benchmarkは改善したが、 この一見小さな変更によってマルチスレッド環境における重大な複雑性が生まれてしまった。
特に満杯のページに対する非ローカルな解放において、 高価なロックを行わないようにするには、 すでに満杯ではないページを所有しているという何らかのシグナルが必要となった。 これはヒープ固有のthread delayed freeブロックのリストで実現する。 汎用ルーチンでアトミックにこのリストを取得し、delayed free listのすべてのブロックを解放する。 これによってfull listのページは通常のリストに戻ってくる。
しかし非ローカルな解放のときに、それをページローカルなthread free listにプッシュすべきか、 thread delay free listにプッシュすべきか、どう判断すればいいだろうか？ このためにスレッドフリーリストのポインタの最下位2ビットを使い、3つの状態をアトミックにエンコードする。
- NORMAL: スレッドフリーリストにプッシュ
- DELAYED: ページがfull listに追加された状態。非ローカルな解放はdelayed free listにプッシュ
- DELAYING: delayed free listにプッシュ中
これは重要な最適化だった。 asymmetric concurrentワークロードでは解放スレッドは多くのオブジェクトを開放し、 高価なinital delayed freeが1回で終わるようにしなければならなかった。 この最適化がないと、xmalloc-testベンチマークは30%遅くなる。
3.5. Security
mimallocはブラウザなどで必要とされる様々なsecurity mitigationsを実装しやすいように設計されている。 様々なsecurity mitigationsを実装したmimallocのセキュアバージョン (smimalloc) を実装した。
- 各ページの間にOSのガードページを置く。 これによりヒープオーバーフロー攻撃はmimallocのページ1つの範囲に制限され、 ヒープのメタデータはオーバーフローしなくなる。
- ページのinital free listを、アロケーションパターンが読まれないようにランダムに初期化する。 ローカルフリーリストを使うかわりに、時々満杯のリストを拡張してランダム性を上げる。
- フリーリストを書き換えるヒープブロックオーバーフローに対抗するために、 フリーリストを各ページにxorエンコードする。 フリーリストを特定の値に書き換えるのを防ぎ、検知を容易にする。
- mimallocはすでに複数ヒープをサポートしている。 内部オブジェクトとそれ以外を分けることでセキュリティを強化する。
mimallocのセキュアバージョンは普通のmimallocと比べて3%遅い。 もっと遅くなると思ってたのでびっくりした。
4. EVALUATION
5. RELATED WORK
6. CONCLUSION
だいたい今まで言ってきたことと同じことが書いてあるので省略