malloc()アルゴリズムの比較

メモリ割り当ての問題はメモリ割り当てを制限します（必要でない場合）。マルチスレッドプログラムは、ヒープがボトルネックとなるため、スケーリングしないことがよくあります。複数のスレッドが同時にアロケータからメモリを割り当てたり解放したりすると、アロケータはそれらをシリアライズします。アロケータを集中的に使用するプログラムは、プロセッサ数が増加するにつれて実際に遅くなります。malloc (libc) は使用するのに最も悪いメモリ割り当てAPIです。プログラムは、可能であれば、メモリの割り当て/解放を頻繁に行わないようにし、特にパケットを受信するたびに避けるべきです。Linuxカーネルには、skbuff（送受信パケットを格納するために使用されるカーネルメモリ）をリサイクルするためのカーネル/ドライバパッチがあります。NICから円形バッファへのパケットのコピーにメモリ割り当てを一切行わないPF_RING（ドライバ内）を使用すると、キャプチャパフォーマンスが約10%向上し、輻輳問題が軽減されます。 設計の進化 malloc()の基本的な設計は、OSからメモリのプールを動的に事前割り当てし、アプリケーションがそこからより小さな断片を取得できるようにすることです。malloc()は、異なる割り当てアルゴリズムの選択肢を持つ標準APIであり、割り当て時に高コストなOSシステムコール（通常はプログラム初期化時に行われる）を軽減するためにシステムメモリを割り当てます。最初のメモリ割り当てスキームは、スタックベースのメモリ割り当てから始まりました。次に、リンクリストとバケットヒープメカニズムを使用して、サイズクラスアプローチでプライベートヒープを分割する動的ベースのメモリ割り当てスキームが登場しました。すぐに、ガベージコレクションアルゴリズムがメモリ割り当てスキームの初期バックエンドとして導入されました。フロントエンドは、通常のmalloc() APIなどをカバーします。2006年には、3番目のプール（オペレーティングシステムメモリプールとライブラリベースのメモリプールに加えて）が「アリーナ」として導入されました。アリーナはjemallocの用語であり、異なる速度のメモリバンクやNUMAアーキテクチャ、さらには複数のCPUコアまたはCPUインフィニティにそれぞれ関連付けられたメモリなど、異なるメモリタイプを扱うことを意図しています。 フロントエンドの進化 フロントエンドは、アプリケーションに与えられるメモリを管理します。メモリ割り当てシステムのフロントエンド内では、進化は次の順序で行われました：リンクリストの空きスペースヒープバケットサイズクラス（オブジェクトヘッダの排除）（プロセス）オーナーエンコーディングシングルコアローカル割り当てバッファ（CLABs）エポックエンコーディング大きなサイズのクラスメモリブロック（mmap()経由）ハザードポインタ（ロックフリーオブジェクトの安全なメモリ回収）（M.M. Michael, 2004）アリーナメモリプール（CPU/コアおよびスレッドごと）スレッド固有のローカル割り当てバッファ（TLABs）定数時間モジュロ同期（OSプールへの早期リターン、またはFreeBSD madvise呼び出し）。 バックエンドの進化 メモリ割り当てシステムのバックエンドは、空き、散在した、断片化した、またはもはや使用されていないメモリブロックをOSに戻す（これによりRSSを削減する）ことを管理します。プールセマンティクス：リモートf-listエンコーディング（Treiberスタックを使用）（R.K. Treiber, 1986）バディアルゴリズムバイナリバディアルゴリズムBIPOPテーブル（spanベースのアロケータ）（S. Schneider, 2006）別名ローカルフリーリストとリモートフリーリストセグメントキュー（Quasi-linearizability, Y. Afek, 2010）マルチコア分散キュー（A. Haas, 2013）k-FIFOキュー（T.A. Henzinger, 2013）。 競合 より多くのスレッド/プロセスがメモリ割り当てシステムコールを実行しても悪化しない、より優れたものが存在します。それらは、パフォーマンスの良い順にリストされています [ソースからのシード]: malloc設計の比較 アロケータ | Origin / Maintainer | スレッドセーフ | パーソナルスレッドキャッシュ | マルチアリーナ/ヒープ | ロックフリー高速パス | NUMA対応 | 断片化制御 | メモ dlmalloc | Doug Lea | いいえ | いいえ | いいえ | いいえ | 低 | 単一グローバルヒープ; 多くの後続アロケータの基盤 ptmalloc2 / ptmalloc3 | glibc | はい | 限定的 | はい | いいえ | 中 | glibcデフォルト; アリーナロックが競合を引き起こす glibc malloc (current) | GNU | はい | 限定的 | はい | いいえ | 中 | ptmallocのラッパー、チューナブル付き jemalloc | FreeBSD / Meta | はい | はい | はい | 部分的 | 高 | スレッドアリーナ親和性がCAS競合を軽減 tcmalloc | Google | はい | はい | はい | 部分的 | 中-高 | CPUごとのキャッシュ; 中央フリーリストは依然として存在する mimalloc | Microsoft | はい | はい | はい | はい | 高 | アトミック操作と偽共有を最小限に抑えるように設計 Hoard | Emery Berger | はい | はい | はい | 部分的 | 中 | スケーラビリティと偽共有回避に焦点を当てる nedmalloc | NEDMALLOC | はい | はい | はい | いいえ | 中 | dlmalloc派生、スレッドキャッシング付き phkmalloc | FreeBSD | はい | はい | はい | いいえ | 中 | 初期FreeBSDアロケータファミリー libumem | Solaris | はい | はい | はい | はい | 中-高 | デバッグとローカリティサポート付きSolarisアロケータ mtmalloc | Solaris | はい | はい | はい | はい | 中 | Solarisマルチスレッドアロケータ snmalloc | Microsoft Research | はい | はい | はい | はい | 高 | NUMA対応、セキュリティおよびスケーラビリティ重視のロックレスmalloc（研究） Academic / Experimental | Varies | はい | Varies | はい | 低 | 多くの場合CASヘビー; 本番環境には不向き CAS / アトミック競合特性 アロケータ | alloc/freeあたりの推定アトミック数 | 共有キャッシュラインリスク | CAS競合感度 | メモ dlmalloc | 高 | 高 | 非常に高 | グローバル構造とロックが支配的 ptmalloc2 / ptmalloc3 | 中-高 | 高 | 高 | アリーナロックがキャッシュラインバウンスを引き起こす glibc malloc (current) | 中-高 | 高 | 高 | ptmallocのラッパー jemalloc | 低 | 低 | 低 | アリーナローカルメタデータ; 最小限の共有CAS tcmalloc | 低-中 | 中 | 中 | CPUごとのキャッシュ; 中央フリーリストCAS mimalloc | 非常に低 | 非常に低 | 非常に低 | アトミック操作を最小限に抑えるように設計 Hoard | 中 | 中 | 中 | 偽共有を軽減するが同期は依然として行われる nedmalloc | 中 | 中 | 中 | スレッドキャッシュはCASを削減するが排除はしない phkmalloc | 中 | 中 | 中 | 古いFreeBSD設計 libumem | 低 | 低 | 低 | Solarisでのロックフリー高速パス mtmalloc | 低 | 低 | 低 | スレッドごとの構造がアトミック共有を削減 snmalloc | 非常に低 | 非常に低 | 非常に低 | メッセージパッシングモデルが共有CASを回避 lockless malloc (research) | 高 | 高 | 高 | ロックがないにもかかわらずCASヘビーであることが多い NUMA、メモリローカリティ特性 アロケータ | 明示的なNUMAサポート | ファーストタッチフレンドリー | クロスNUMAトラフィックリスク | ローカリティ維持 | メモ dlmalloc | いいえ | はい | 非常に高 | 低 | 単一ヒープがノード全体に広がる ptmalloc2 / ptmalloc3 | いいえ | 部分的 | 高 | 公平 | アリーナはNUMAに束縛されない glibc malloc (current) | いいえ | 部分的 | 高 | 公平 | OS配置に依存 jemalloc | 部分的 | はい | 中 | 良好 | オプションのNUMAアリーナチューニング tcmalloc | 限定的 | はい | 中 | 公平 | CPUキャッシュはNUMAを意識しない mimalloc | いいえ | はい | 低 | 非常に良好 | 強力なスレッドローカリティ Hoard | いいえ | はい | 中 | 良好 | CPUごとのヒープが役立つ nedmalloc | いいえ | はい | 中 | 公平 | スレッドキャッシュだがグローバルフォールバック phkmalloc | 部分的 | はい | 中 | 公平 | 初期ローカリティ最適化 libumem | はい | はい | 低 | 非常に良好 | Solaris NUMAポリシー mtmalloc | はい | はい | 低 | 非常に良好 | NUMA向けに設計されたSolarisシステム snmalloc | はい | はい | 非常に低 | 優秀 | NUMAファーストアーキテクチャ lockless malloc (research) | いいえ | Varies | 高 | 低 | ローカリティはめったに対処されない ベンチマーク指向の実践的パフォーマンス アロケータ | 小オブジェクト割り当てスループット | 大オブジェクト割り当てスループット | 競合下でのレイテンシ | メモリオーバーヘッド | 断片化リスク | メモ dlmalloc | 低 | 中 | 低 | 低 | 高 | マルチスレッド負荷には不向き ptmalloc2 / ptmalloc3 | 中 | 中 | 低 | 中 | 中 | glibcデフォルト glibc malloc (current) | 中 | 中 | 低 | 中 | 中 | チューナブルだが限定的 jemalloc | 高 | 高 | 非常に良好 | 中-低 | 低 | 優れたオールラウンドアロケータ tcmalloc | 非常に高 | 中 | 良好 | 中 | 中 | 小オブジェクトに最適化 mimalloc | 高 | 高 | 優秀 | 低 | 低 | 優れたレイテンシ予測可能性 Hoard | 中 | 中 | 良好 | 中 | 低 | スケーラビリティ向けに設計 nedmalloc | 中 | 中 | 公平 | 中 | 中 | 古いが使用可能 phkmalloc | 中 | 中 | 公平 | 中 | 中 | 歴史的なFreeBSDアロケータ libumem | 高 | 中 | 非常に良好 | 中 | 低 | 強力なデバッグサポート mtmalloc | 高 | 中 | 非常に良好 | 中 | 低 | エンタープライズSolarisワークロード snmalloc | 高 | 高 | 優秀 | 非常に低 | 非常に低 | セキュリティ+スケーラビリティ重視 lockless malloc (research) | Varies | Varies | 低 | 低 | 高 | 実践では不安定なことが多い アロケータ推奨 ワークロードタイプ | プライマリボトルネック | 主要リスク | 推奨アロケータ