プログラミング

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

Comparison of Malloc() Algorithms (egbert.net)

120 pointsby egberts12026年9月16日32 コメント

要約

この記事は、マルチスレッド環境におけるmalloc()のパフォーマンスボトルネックと、メモリ割り当てアルゴリズムの進化について論じています。スタックベースの割り当てから動的スキーム、ガベージコレクション、そして異なるメモリタイプやアーキテクチャを管理するための「アリーナ」の導入に至るまでの進化を詳述しています。さらに、スレッドセーフティ、パフォーマンス、NUMA対応などの観点から、jemalloc、tcmalloc、mimallocといった様々なアロケータの詳細な比較表を提供しています。

全文翻訳

2026年1月20日 malloc()におけるアリーナアーキテクチャの比較

メモリ割り当て

問題点

必要でない限り、メモリ割り当てを制限する

マルチスレッドプログラムは、ヒープがボトルネックとなるため、多くの場合スケールしません。

複数のスレッドが同時にアロケータからメモリを割り当てたり解放したりすると、アロケータはそれらをシリアル化します。アロケータを集中的に使用するプログラムは、プロセッサ数が増えるにつれて実際に遅くなります。

Malloc (libc) は使用するのに最も悪いメモリ割り当てAPIです。

プログラムは、可能であれば、メモリの割り当て/解放を頻繁に行わないようにすべきです。特に、パケットを受信するたびに割り当て/解放するのは避けるべきです。

Linuxカーネルには、skbuff（送受信パケットを格納するために使用されるカーネルメモリ）をリサイクルするためのカーネル/ドライバパッチが利用可能です。

ドライバ内でPF_RINGを使用すると、メモリ割り当てなしでNICからサーキュラーバッファにパケットをコピーできるため、キャプチャパフォーマンスが約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-リストエンコーディング（Treiberスタックを使用）（R.K. Treiber, 1986）
バディアルゴリズム
バイナリバディアルゴリズム
BIPOPテーブル（スパンベースアロケータ）（S. Schneider, 2006）別名ローカルフリーリストとリモートフリーリスト
セグメントキュー（準線形化可能性、Y. Afek, 2010）
マルチコア分散キュー（A. Haas, 2013）
k-FIFOキュー（T.A. Henzinger, 2013）

競合

より優れたものが存在し、より多くのスレッド/プロセスがメモリ割り当てシステムコールを実行しても悪化しないものがあります。これらはパフォーマンスの良い順にリストアップされています [ソース付き]

malloc設計の比較

アロケータ	起源 / メンテナ	スレッドセーフ	スレッドごとのキャッシュ	マルチアリーナ / ヒープ	ロックフリー高速パス	NUMA対応	断片化制御	メモ
dlmalloc	Doug Lea	No	No	No	No	Low	Single global heap; basis for many later allocators	後続のアロケータの多くがベース
ptmalloc2 / ptmalloc3	glibc	Yes	Limited	Yes	No	Medium	glibc default; arena locks cause contention	glibcデフォルト; アリーナロックが競合を引き起こす
glibc malloc (current)	GNU	Yes	Limited	Yes	No	Medium	Wrapper around ptmalloc with tunables	ptmallocのラッパー、チューニング可能
jemalloc	FreeBSD / Meta	Yes	Yes	Yes	Partial	High	Thread-arena affinity reduces CAS contention	スレッドとアリーナの親和性がCAS競合を軽減
tcmalloc	Google	Yes	Yes	Yes	Partial	Medium-High	Per-CPU caches; central freelists still exist	CPUごとのキャッシュ; 中央フリーリストが存在
mimalloc	Microsoft	Yes	Yes	Yes	Yes	High	Designed to minimize atomic ops and false sharing	アトミック操作と偽共有を最小化するように設計
Hoard	Emery Berger	Yes	Yes	Yes	Partial	Medium	Focus on scalability and false-sharing avoidance	スケーラビリティと偽共有回避に注力
nedmalloc	NEDMALLOC	Yes	Yes	Yes	No	Medium	dlmalloc-derived with thread caching	スレッドキャッシングを備えたdlmalloc派生
phkmalloc	FreeBSD	Yes	Yes	Yes	No	Medium	Early FreeBSD allocator family	初期のFreeBSDアロケータファミリー
libumem	Solaris	Yes	Yes	Yes	Yes	Medium-High	Solaris allocator with debugging and locality support	デバッグとローカリティサポートを備えたSolarisアロケータ
mtmalloc	Solaris	Yes	Yes	Yes	Yes	Medium	Solaris multithreaded allocator	Solarisマルチスレッドアロケータ
snmalloc	Microsoft Research	Yes	Yes	Yes	Yes	High	NUMA-aware	security- and scalability-focused
lockless malloc (research)	Academic / Experimental	Varies	Yes	Varies	Yes	Low	Often CAS-heavy; not production ready	CAS多用; 本番環境には適さない
ltalloc	Academic

CAS、アトミック競合特性

CAS / アトミック競合特性

アロケータ	割り当て/解放あたりの推定アトミック数	共有キャッシュラインリスク	CAS競合感度	メモ
dlmalloc	High	High	Very High	グローバル構造体とロックが支配的
ptmalloc2 / ptmalloc3	Medium-High	High	High	アリーナロックがキャッシュラインのバウンスを引き起こす
glibc malloc (current)	Medium-High	High	High	ptmallocのラッパー
jemalloc	Low	Low	Low	アリーナローカルメタデータ; 共有CASは最小限
tcmalloc	Low-Medium	Medium	Medium	CPUごとのキャッシュ; 中央フリーリストCAS
mimalloc	Very Low	Very Low	Very Low	アトミック操作を最小化するように設計
Hoard	Medium	Medium	Medium	偽共有を軽減するが同期は必要
nedmalloc	Medium	Medium	Medium	スレッドキャッシュはCASを削減するが排除はしない
phkmalloc	Medium	Medium	Medium	古いFreeBSD設計
libumem	Low	Low	Low	Solarisでのロックフリー高速パス
mtmalloc	Low	Low	Low	スレッドごとの構造体がアトミック共有を削減
snmalloc	Very Low	Very Low	Very Low	メッセージパッシングモデルが共有CASを回避
lockless malloc (research)	High	High	High	ロックなしでもCAS多用

NUMA、メモリローカリティ特性

NUMA / メモリローカリティ特性

アロケータ	明示的なNUMAサポート	ファーストタッチフレンドリー	クロスNUMAトラフィックリスク	ローカリティ維持	メモ
dlmalloc	No	Yes	Very High	Poor	単一ヒープがノードをまたぐ
ptmalloc2 / ptmalloc3	No	Partial	High	Fair	アリーナはNUMAに束縛されない
glibc malloc (current)	No	Partial	High	Fair	OS配置に依存
jemalloc	Partial	Yes	Medium	Good	オプションのNUMAアリーナチューニング
tcmalloc	Limited	Yes	Medium	Fair	CPUキャッシュはNUMA対応ではない
mimalloc	No	Yes	Low	Very Good	強いスレッドローカリティ
Hoard	No	Yes	Medium	Good	CPUごとのヒープが役立つ
nedmalloc	No	Yes	Medium	Fair	スレッドキャッシュだがグローバルフォールバック
phkmalloc	Partial	Yes	Medium	Fair	初期ローカリティ最適化
libumem	Yes	Yes	Low	Very Good	Solaris NUMAポリシー
mtmalloc	Yes	Yes	Low	Very Good	NUMA Solarisシステム向けに設計
snmalloc	Yes	Yes	Very Low	Excellent	NUMAファーストアーキテクチャ
lockless malloc (research)	No	Varies	High	Poor	ローカリティはほとんど考慮されない

ベンチマーク指向の実践的パフォーマンス

アロケータ	小オブジェクトスループット	大オブジェクトスループット	競合下でのレイテンシ	メモリオーバーヘッド	断片化リスク	メモ
dlmalloc	Low	Medium	Poor	Low	High	マルチスレッド負荷には不向き
ptmalloc2 / ptmalloc3	Medium	Medium	Poor	Medium	Medium	glibcデフォルト
glibc malloc (current)	Medium	Medium	Poor	Medium	Medium	チューニング可能だが限定的
jemalloc	High	High	Very Good	Medium-Low	Low	優れたオールラウンドアロケータ
tcmalloc	Very High	Medium	Good	Medium	Medium	小オブジェクトに最適化
mimalloc	High	High	Excellent	Low	Low	優れたレイテンシ予測可能性
Hoard	Medium	Medium	Good	Medium	Low	スケーラビリティのために設計
nedmalloc	Medium	Medium	Fair	Medium	Medium	古いが使用可能
phkmalloc	Medium	Medium	Fair	Medium	Medium	歴史的なFreeBSDアロケータ
libumem	High	Medium	Very Good	Medium	Low	強力なデバッグサポート
mtmalloc	High	Medium	Very Good	Medium	Low	エンタープライズSolarisワークロード
snmalloc	High	High	Excellent	Low	Very Low	セキュリティ + スケーラビリティに注力
lockless malloc (research)	Varies	Varies	Poor	Low	High	実践では不安定なことが多い

アロケータ推奨

ワークロードタイプ	主なボトルネック	主要リスク	推奨アロケータ	適した理由	代替案	回避
高度に競合するマルチスレッド	アトミック/CASレイテンシ	キャッシュラインバウンス	jemalloc	マルチアリーナ + スレッド親和性が共有CASを最小化	mimalloc	snmalloc,dlmalloc ptmalloc
低レイテンシ / テール感度	割り当てジッター	ロックコンボイ	mimalloc	非常に低いアトミック数と予測可能な高速パス	snmalloc	jemalloc,tcmalloc
NUMA / マルチソケットサーバー	ノード間メモリアクセス	リモートキャッシュ所有権	snmalloc	明示的なNUMA対応とローカリティ制御	jemalloc (NUMAチューニング済み)	libumem,glibc malloc
小オブジェクト中心 (RPC / Web)	アロケータスループット	中央フリーリスト競合	tcmalloc	CPUごとのキャッシュが小オブジェクト割り当てに最適化	jemalloc	mimalloc,ptmalloc
大オブジェクト / 混合サイズ	断片化	TLB圧力	jemalloc	優れた断片化制御とエクステント管理	mimalloc	glibc malloc
偽共有に敏感	キャッシュラインのピンポン	メタデータ共有	Hoard	偽共有を回避するように設計	jemalloc	mimalloc,dlmalloc
セキュリティ強化	使用後解放エクスプロイト	ヒープ破損	snmalloc	分離 + セキュリティ不変条件	mimalloc (セキュア)	ptmalloc
デバッグ / リーク検出	メモリ誤用可視性	サイレント破損	libumem	強力な実行時診断	jemalloc (プロファイリング)	tcmalloc
組み込み / 低メモリ	フットプリントサイズ	オーバーヘッド	dlmalloc	シングルスレッドであれば小さくシンプル	nedmalloc	jemalloc
リアルタイム / 決定論的	無制限レイテンシ	OS干渉	mimalloc	低分散の高速パス	snmalloc	jemalloc,tcmalloc
HPC / 科学的NUMA	メモリ帯域幅	リモートNUMAヒット	snmalloc	NUMAファースト設計と低CASトラフィック	jemalloc + mbind	glibc malloc
レガシー / 互換性	ABI安定性	ツールチェーン問題	glibc malloc	システムデフォルトで最も安全なフォールバック	ptmalloc

malloc選択のための意思決定チャート

［画像: malloc選択のための意思決定スーパートゥリー］

Graphviz DOTファイル

参考文献

R. J. Maher, Problems of storage allocation in a multiprocessor multiprogrammed system, Communications of the ACM, 4(10):421-422, October 1961
A fast storage allocator, Kenneth C. Knowlton, Communications of the ACM, 8(10):623-625, October 1965.
Statistical properties of the buddy system, P.W. Purdom and S. M. Stigler, Journal of the ACM, 17(4):683-697, October 1970
Statistical investigation of three storage allocation algorithms, P. W. Purdom, S. M. Stigler, and Tat-Ong Cheam, BIT, 11:187-195, 1971.
A note on an optimal-fit method for dynamic allocation of storage, J. A. Campbell, Computer Journal, 14(1):7-9, February 1971.
Worst-case analysis of memory allocation algorithms, M. R. Garey, R. L. Graham, and J. D. Ullman, In Fourth Annual ACM Symposium on the Theory of Computing, 1972
A class of dynamic memory allocation algorithms, D. S. Hirschberg, Communications of the ACM, 16(10):615-618, October 1973
Dynamic storage allocations of arbitrary sized segments, J. S. Fenton and D. W. Payne, In Proc. IFIPS, pages 344-348, 1974
Worst-case of Memory Allocation Algorithms, Garey 1972
A simplified recombination scheme for the Fibonacci buddy system, B. Cranston and R. Thomas, Communications of the ACM, 18(6):331-332, July 1975.
Buddy systems, J. L. Peterson and T. A. Norman, Communications of the ACM, 20(6):421-431, June 1977.
Worst case fragmentation of first fit and best fit storage allocation strategies, J. M. Robson, Computer Journal, 20(3):242-244, August 1977.
Fast-fit: A new hierarchical dynamic storage allocation technique, M. Tadman, Master’s thesis, UC Irvine, Computer Science Dept., 1978.
The double buddy-system, David S. Wise, Technical Report 79, Computer Science Department, Indiana University, Bloomington, Indiana, December 1978
Memory fragmentation in buddy methods for dynamic storage allocation, A. G. Bromley, Acta Informatica, 14(2):107-117, August 1980.
Optimal fit of arbitrary sized segments, Ivor P. Page, Computer Journal, 25(1), January 1982.
Parallelizing the usual buddy algorithm, A. Gottlieb and J. Wilson, Technical Report System Software Note 37, Courant Institute, New York University, 1982.
Fast fits: New methods for dynamic storage allocation, C. J. Stephenson, In Proceedings of the Ninth Symposium on Operating Systems Principles, pages 30-32, Bretton Woods, New Hampshire, October 1983. ACM Press. Published as Operating Systems Review 17(5), October 1983.
On the asymptotic optimality of first-fit storage allocation, E. G. Coffman, Jr., T. T. Kadota, and L. A. Shepp, IEEE Transactions on Software Engineering, SE-11(2):235-239, February 1985.
Efficient implementation of the first-fit strategy for dynamic storage alloca- tion, R. Brent, ACM Transactions on Programming Languages and Systems, July 1989.
Fast allocation and deallocation of memory based on object lifetimes, David R. Hanson, Software Practice and Experience, 20(1), January 1990.
Dynamic Storage Allocation: A Survey and Critical Review, very useful chronological order of malloc(), 1995
The Memory Fragmentation Problem: Solved? Johnstone 1997
A Memory Allocator, 2000
Solaris mtmalloc (archived), 2003
Anatomy of a Program in Memory, 2009
A History of malloc, 2010
Heap and allocators, 2015
Understanding glibc malloc
The Origins of Malloc, 2017
GrapheneOS hardened_malloc, 2019
Simulation of High-Performance Memory Allocators, Risco-Martin, 2024