とある愚直のリニアサーチ - 神様なんて信じない僕らのために

前のエントリで線形探索のメモリアロケータは駄目だ駄目だ、と言いました。 で、まず線形探索の何が駄目って、メモリは以下のようになっています。 最初は「未使用領域（青）」しかありません。ここからどう領域をとっても良いです。 ただ、使っていくうちに「使用領域（赤）」と「未使用領域（青）」の数珠つなぎになりがちです。 new/deleteの順番を意識すればこういったメモリの配置問題が解決できることもありますが、 実際には「クラスがメモリの状態に束縛される」とすると非常に面倒です。 なので、効率的なアロケータは必須なのです。 あなたが下のような断片化した領域をつなぐ双方向リストを持っていると仮定してください。 ここから効率よくメモリを探すことは絶対にできません。 ソートしておくといったことも考えられますが、ソートすると解放された領域のマージが困難です。 （freeされた隣接した領域はより大きなメモリ

[TAKESAKO]

とある愚直のリニアサーチ dlmalloc