Malloc
C++でもmalloc関数は利用できるが、この利用は後述の問題を引き起こすため推奨されない。C++では言語の機能としてnew演算子、delete演算子が用意されている。mallocで確保したメモリ領域に対してdeleteしたり、逆にnewで確保した領域をfreeしたりすると結果は未定義となる。mallocによって生まれたポインタとnewによって生まれたポインタの混在はバグの温床であり、また、new/delete演算子と違い、malloc/free関数ではクラスのコンストラクタとデストラクタが呼ばれないという違いもあり、C++でのmallocは禁じ手の扱いである。
dlmalloc は Doug Lea が1987年に開発を始めた汎用アロケータ。パブリックドメインライセンス(CC0ライセンス)のオープンソースライブラリ。GNU Cライブラリ (glibc) の malloc は、dlmalloc を元に作られている。
ヒープ領域上のメモリは "chunk" という8バイト境界のデータ構造として確保され、その中にヘッダ部と利用可能なメモリがある。chunk および利用中フラグがあるため、8バイトまたは16バイトのオーバヘッドを含めたメモリ確保が必要である。アロケートされていないchunkも他のフリーなchunkへのポインタを持つため、chunkの最小サイズは24バイトとなっている。
アロケートされていないメモリは "bin" と呼ばれる同じサイズのchunkのグループに分けて管理される。binはchunkを双方向連結リストで連結したものである。
小さな領域 (<256B) を確保するときには2の累乗フリーリストが使われる。領域が不足したときは、より大きなサイズ用の領域からプールを確保する。
中程度の大きさの領域は、bitwiseトライ木により管理される。領域が不足したときは、(sbrkによる)ヒープの拡張が行われる。
大きな領域(デフォルト値は >= 256KB)は、mmap() が使える環境の場合、mmap() により直接確保される。この大きさならば、ページサイズ(通常4KB, CPUのアーキテクチャに依存する)単位でしか割り当てられないことによるオーバーヘッド、システムコールの遅さによるオーバーヘッドはほとんどない。一方で、先に述べたヒープ方式のアロケーションの問題が起こらないので、この方法が使われる。