FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

malloc/free

dlmallocのヘッダ削減のアイデアに感動してアロケータ作ってみた。基本first-fit。でも大抵はほぼO(1)。
固定サイズの領域からメモリを管理する。ヒープ領域の拡張とかマルチスレッドでのパフォーマンスとかは考えてない。

実装したアイデアは次の二つだけ
・フリーブロックを2の累乗ごとに区切ったテーブルで管理
・使用中のブロックのヘッダサイズが4byte

C++のプログラムは注意しないと大抵数十byteの小さいオブジェクトが増えるのでヘッダサイズは重要。

別のアイデア
・小さいサイズ(64か128byteあたり?)のアロケートをFixedAllocatorなどの別の方法に変える
小さいサイズだと4byteとはいえヘッダが占める割合が大きくなるので効果はあったりする。またFixedAllocatorなら通常のアロケートより速く動作してくれる。

・ヘッダサイズを更に削る
ブロックのサイズが入っているヘッダだが、サイズが1byteないしは2byteで表せる範囲なら4byteも必要ない。サイズを表すビットを追加すれば判別もできる。速度は遅くなるから微妙といえば微妙。
そこまでして削るぐらいならもっとマクロな視点から削ろうよとか突っ込まれそう。

・フリーテーブルの細分化
2の累乗ごとにテーブルを区切ってるけど、これをもっと細かくする。テーブルサイズは増えてしまうけどbest-fitに近づくので断片化対策になる。

参考:
ここにあるパワポがすごい判りやすかった。
革命の日々!カーネル読書会で講演してきました
本家 
A Memory Allocator

ヘッダ


定義


スポンサーサイト
検索フォーム
ユーザータグ

ICPC 2009 国内予選 ゲームプログラミング 

カテゴリ
最新記事
月別アーカイブ
最新コメント
最新トラックバック
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。