動的メモリ確保
静的メモリアロケーションとは、プログラムのコンパイル時にデータ領域の確保を決定すること。複数のサブルーチンや関数からアクセスされるグローバルなデータ領域、特にプログラム走行中常に使用されるものをこの方法で確保するのが一般的である。具体的な確保の方法はプログラミング言語に依存する。
未使用領域をサイズ順に並べ替えておけば、要求されたサイズに最も近い未使用領域を比較的高速に(領域数に対し O(log n) の計算量で)確保することができる。平衡2分木を用いれば、このような実装が可能である。ほかのアルゴリズムと比較すると遅いので、領域をできるだけ有効に使いたい場合にだけ使われることがある。
Erlang 実行環境のアロケータ などで使用されている。
2の累乗ごとのフリーリストでは、最大で50%の無駄が生じる。たとえば、65バイトのデータを格納するために、128バイトの領域を割り当てる必要があるためである。Two-Level Segregated Fit アロケータ (TLSFアロケータ、「2レベル分離適合割り当て器」) は、2のべき乗の分類の下に、さらに細かい分類を行なうことでメモリ利用効率を改善する。空き領域を細かく分類して管理するので、要求されたサイズに最適なブロックがないこともあるが、細分類ごとの空き領域の有無をビットマップとして保持しているので、最適なサイズのブロックを即座に見つけだせるように工夫されている。
速度については、平均的なケースではdmallocと比べて少し遅いが、固定サイズブロック割り当ての応用であるためどのような状況でも同じ時間で動作し、最悪時間が存在しないのでリアルタイムシステムに向いている。
2003年に、リアルタイムオペレーティングシステムのアロケータとして発表された。
TLSFアロケータを採用したシステムには、Morph OS などがある。