プールアロケータ

弾、パーティクル、エンティティのように、同じサイズのオブジェクトを絶えず作っては壊すプログラムでは、汎用ヒープは遅く、断片化も起きやすい。プールアロケータはバッファをあらかじめ固定サイズのブロックに分割し、空きブロックを単純な連結リストにつなぐ。割り当ては先頭の空きブロックを取り出すこと、解放は先頭に戻すことで、どちらもO(1)だ。

すべてのブロックが同じ大きさなので、どんな順序で再利用しても、何も収まらない隙間は生じない。断片化は構造上なくなる。この仕組みをオブジェクトプーリングと混同しないこと。考え方は同じだが一段上の話で、そちらは使い終えたゲームオブジェクトを再利用し、こちらは生のメモリブロックを再利用する。