メモリアロケーションにおけるフラグメンテーションへの対策

[kawasin73]

動的なヒープメモリアロケーションではフラグメンテーションが発生する。 以下のそれぞれのモジュールでは、フラグメンテーションの対策をどのように行っているかを調査する。

• malloc
• tcmalloc
• jemalloc
• glic malloc ( https://www.slideshare.net/kosaki55tea/glibc-malloc )

[kawasin73]

まず、wikipedia で一般的な考え方を調査した

• 固定サイズのフリーリスト
  • サイズクラス（2 のベキ乗）ごとに連結リストでフリーリストをもつ
• 平衡2分木による実装
  • 未使用領域をサイズごとに並び替えて管理する
  • 一般的に遅くなるが、空間を効率的に使える
  • サイズクラスごとにアドレス順で並び替え、Low address なメモリを再利用することで局所性がでる
• TLSFアロケータ（Two-Level Segregated Fit）
  • サイズクラスを2階層設け、2 のベキ乗のサイズクラスの下にさらに細かいサイズクラスを設けることで内部フラグメンテーションを減らす
  • 細分類ごとの空き領域の有無をビットマップとして保持
  • 平均的なケースではdmallocと比べて少し遅いが、同じ時間で動作し、最悪時間が存在しないのでリアルタイムシステムに向いている
• 一般的に大きなメモリ（256KBを超えるなど）は、mmap が利用可能な場合 mmap を用いてメモリ確保し、小さなメモリ管理とは別で管理する
• バディブロック
  • 2 のベキ乗のメモリ領域を分割して、分割した2つの領域をバディとしてグルーピングする。この分割を再帰的に行い必要なサイズのメモリをアロケーションする
  • ブロックの解放ではバディが解放されているかを確認し結合する

参考

• malloc - Wikipedia
• 動的メモリ確保 - Wikipedia

[kawasin73]

TCMalloc

Thread-Caching Malloc

http://goog-perftools.sourceforge.net/doc/tcmalloc.html

特徴

• malloc が速い
• スレッド間でのロック競合が少ない
• 管理領域のオーバーヘッドが 1 % に抑えられている

仕組み

• Central Heap と Thread Cache を持つ
• 32K 以下は Small Object、それより大きいメモリは Large Object
• Small Object は、複数のサイズクラスをもち、1 つのページを分割して同じサイズのメモリオブジェクトを作り、サイズクラスの free list に追加する。同じページから作られたメモリオブジェクトの集合は Span で管理される。
• Large Object は Central Heap からアロケートされ、ページにアライメントされる。ページサイズのサイズクラスごとに free list を持つ。複数ページにまたがる Large Object も Span で管理する。
• スレッドごとの Thread Cache が small object の free list をサイズクラスごとに連結リストで持つ。足りない時は Central Heap から Thread Cache に移動させる
• Central Heap の free list のサイズクラスにない場合はメモリをページでアロケートして分割する
• Span という構造体で大元のメモリページの集合を管理、メモリサイズの単位を保持する。ページ番号から Span をひくインデックス（32 bit だと 4MB になる）を持っている
• Deallocate では、メモリアドレスからページ番号を計算し、Span のインデックスによって Span を引いてくる
  • small Object の場合は、Span からサイズクラスを取得して Thread Cache の free list に戻す。free list のサイズが大きくなった場合は GC を実行して、Thread Cache の free list から Central Heap へ移動させる。
  • large Object の場合は、前後のページの Span を確認して使われていない場合は結合して、free list に戻す
  • Central Heap で free list が一定数以上になった場合、GC を行い、Span 内のすべてのメモリが使われていない時は結合してページにし、Large Object として free list に戻す

[kawasin73]

jemalloc

http://d.hatena.ne.jp/repeatedly/20110110/1294634486

https://www.facebook.com/note.php?note_id=480222803919

• メモリの確保と解放を高速に行う、フラグメンテーションを抑える、プロファイリングを可能にする、の3つの性質を同時に満たすことを目標にしたアロケーター
• 特徴
  • 小さいアドレスを使うようにする（参考：phkmalloc）
  • フラグメンテーションが少なくなるようなサイズクラス設計
  • メタデータのオーバーヘッドを 2% 以内に抑える
  • 同じアプリケーションに使われているページを少なくすることで、まとめて file に　swap されるようにする。（参考：phkmalloc）
  • ロック競合を抑える。（参考：lkmalloc、tcmalloc）
• small(〜4KB)、large(4K〜4MB)、huge(4MB〜) の3つの大きさによって処理の方法が異なる
  • small：[8], [16, 32, 48, ..., 128], [192, 256, 320, ..., 512], [768, 1024, 1280, ..., 3840]
  • large：[4 KiB, 8 KiB, 12 KiB, ..., 4072 KiB]
  • huge：[4 MiB, 8 MiB, 12 MiB, ...]
• サイズクラスごとに未使用領域を管理し、サイズクラスごとにアドレスの順番で並び替えて管理する
• スレッドごとに独立した「アリーナ」を作成し、その中に small と large のメモリプールを持たせる。
• どのスレッドで解放されても、解放されたメモリは確保されたアリーナに戻る

アリーナのメモリは、chunk （デフォルトで 4MiB）で管理されている。定数時間で chunk のメタデータにアクセスできる。 チャンクの先頭にメタヘッダーがあり、ページマップを持つ。 Small Object は、それぞれ small object page run の先頭にメタヘッダーを持つ Lage Object は、チャンクのメタヘッダーに管理される 空きのある small object page run は、dirty と clear の2種類の赤黒木で管理され、dirty なものから使っていく

スレッドごとにキャッシュを持ち、アリーナにアクセスする前にキャッシュを確認して利用可能であればキャッシュから使う。 アリーナの操作にはロックが必要になる

スレッドキャッシュにあるメモリはアロケーションリクエストを単位とする インクリメンタルGC によって指数的に徐々に低下するアプローチでアリーナに戻される