FC2ブログ

スポンサーサイト

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

SmallObj.cppの覚書その2

http://loki-lib.sourceforge.net/html/a00671.html

00168 class FixedAllocator
    固定サイズアロケータ。チャンクの検索さえ入らなければ高速。確保/開放がLIFOになってれば検索がほぼ最小になるので速い。
    ランダムな確保/開放の性能は微妙。ブロックの最小サイズは1byte。それはすげえ。けどインデックスになってるから除算とか入る。

00176 void DoDeallocate( void * p );
    ブロックpの解放。deallocChunk_がpのチャンクである必要が在る。
    解放後にdeallocChunk_が完全に空(使用中のブロックを持っていない)であり、かつemptyChunk_が非NULLであれば
    そのチャンクを解放する。また解放時に、allocChunk_が満杯か、もしくは解放するチャンクであればallocChunkを
    空なチャンクに差し替える。

00183 bool MakeNewChunk( void );
    新しいチャンクの追加。成功すればtrue,失敗すればfalse。
    Chunk::Initが出すかもしれない例外をキャッチする。
    allocChunk_は新しく作ったチャンクに。deallocChunk_はchunks_の先頭のチャンクになる。
    chunks_の拡張→チャンクの初期化→chunks_への追加、と処理を行う。
    push_backしたあとチャンクの初期化をやると、初期化に失敗したときにそのチャンクを消す手間があるので、それをなくすためにこの順番でやってると思われる。

00197 Chunk * VicinityFind( void * p ) const;
    pが属しているチャンクを返す。見つからなければNULL。
    deallocChunk_から前後に配置されているチャンクを順番に検索する。LIFOに基づいてれば速いそうな。

00200 FixedAllocator(const FixedAllocator&);
00202 FixedAllocator& operator=(const FixedAllocator&);
    コピー防止。

00205 typedef std::vector< Chunk > Chunks;
    Chunkのリスト。vector使ってるのは検索を高速化するためだと思われる。

00207 typedef Chunks::iterator ChunkIter;
00209 typedef Chunks::const_iterator ChunkCIter;
    イテレーター。

00212 static unsigned char MinObjectsPerChunk_;
    チャンク当たりの最小ブロック数。8。

00215 static unsigned char MaxObjectsPerChunk_;
    チャンク当たりの最大ブロック数。インデックスの最大値である255。

00218 std::size_t blockSize_;
    ブロックひとつ当たりのサイズ。

00220 unsigned char numBlocks_;
    確保(ユーザーに渡した)ブロック数。

00223 Chunks chunks_;
    Chunkのリスト。    

00225 Chunk * allocChunk_;
    最後にブロックを確保したチャンク。高速に動作させるためのキャッシュ。フリーブロックを持っているとは限らない。

00227 Chunk * deallocChunk_;
    最後にブロックを解放したチャンク。高速化の為にFixedAllocator::VicinityFindで利用されてる。

00229 Chunk * emptyChunk_;
    空なチャンクがあればこの変数に格納される。この変数が非NULLの状態でさらに空チャンクが発生した場合はそのチャンクが解放される。

00233 FixedAllocator();
    コンストラクタ。変数の初期化のみ。

00236 ~FixedAllocator();
    DO_EXTRA_LOKI_TESTが定義されているときに TrimEmptyChunk() の呼び出し。
    保持しているチャンクに対してChunk::Releaseの呼び出し。

00239 void Initialize( std::size_t blockSize, std::size_t pageSize );
    初期化。
    ブロックサイズはそのまま。ページサイズに入りうるブロックの数を求めて
    MinObjectPerChunk_とMaxObjectsPerChunk_でクランプしてnumBlocksに入れる。

00244 void * Allocate( void );
    メモリの確保。フリーブロックを持つチャンク、allocChunk_のChunk::Allocを呼び出す。
    allocChunk_がNULLか満杯ならば、フリーブロックをもつチャンクを線形検索する
    それでもフリーブロックを持つチャンクが見つからなければMakeNewChunkを呼び出す。MakeNewChunkに失敗すればNULLが返る。

00251 bool Deallocate( void * p, Chunk * hint );
    hintが非NULLならそのチャンクを、そうでなければFixedAllocator::VicinityFindから取得したチャンクを
    deallocChunk_に設定しDoDeallocateを呼び出す。
    戻り値は解放が成功すればtrue、失敗すればfalse。ポインタpが指定されたチャンクから取得したものでなければ失敗。

00254 inline std::size_t BlockSize() const { return blockSize_; }
    ブロックサイズの取得。

00260 bool TrimEmptyChunk( void );
    空な(余分な)チャンクを消す。

00267 bool TrimChunkList( void );
    チャンクリストから余分な領域を削る。

00272 std::size_t CountEmptyChunks( void ) const;
    空(使用中のブロックを持っていない)なチャンクの個数を返す。
    emptyChunk_が非NULLであれば1,そうでなければ0。
    DO_EXTRA_LOKI_TESTSが定義されていれば、チャンクリストから空なチャンクの個数を検索する。
    0か1しか返らない。

00280 bool IsCorrupt( void ) const;
    整合性チェック。整合性が取れていなければtrue、取れてればfalse。
    チャンクを持っていないときは、chunks_のbegin()==end()はtrueか?CountEmptyChunksは0か?deallocChunk_,allockChunk_,emptyChunk_はNULLか?がチェックされる。
    チャンクを持っているときは、chunks_のbegin()<end()はtrueか?deallocChunk_,allocChunk_は、chunks_の中に含まれるか?emptyChunk_は空なチャンクか?全チャンクに対するChunk::IsCorruptの呼び出し、が行われる。

00286 const Chunk * HasBlock( void * p ) const;
    そのブロックが確保されたチャンクを返す。判定方法は全チャンクを線形検索し、各々のチャンクにChunk::HasBlockを呼び出すだけ。

00287 inline Chunk * HasBlock( void * p )
    const版を呼ぶだけ。
スポンサーサイト

SmallObj.cppの覚書その1

http://loki-lib.sourceforge.net/html/a00671.html

00068 class Chunk
    FixedAllocatorの下位で動くクラス。FixedAllocatorはChunkを複数もつ。
    実際の確保/開放処理はFixedAllocatorからこいつに投げられる。

00078 bool Init( std::size_t blockSize, unsigned char blocks );
    引数のオーバーフローのアサートチェック、メモリの確保、Chunk::Resetの呼び出し。
    USE_NEW_TO_ALLOCATEが定義されて居た場合はnew,そうでなければstd::mallocがメモリ確保に使用される。
    戻り値は成功/不成功。メモリ確保に失敗したときのみ失敗が返る。
    newで失敗した場合は例外投げられる。キャッチするのは上位レイヤーらしい。例外オフにされてたらどうする。

00086 void * Allocate( std::size_t blockSize );
    ブロックの確保。出来ない場合はNULLが返る。フリーリストから先頭ブロックの取り出し。

00096 void Deallocate( void * p, std::size_t blockSize );
    ブロックの解放。
    渡されたブロックをフリーリストに追加するだけ。インデックスを求めるために除算が入る。

00103 void Reset( std::size_t blockSize, unsigned char blocks );
    メンバ変数の初期化、フリーリストの構築。
    各々のブロックの先頭に次のフリーブロックのインデックスを書き込む。

00106 void Release();
    Initで確保されたバッファを開放するだけ。

00117 bool IsCorrupt( unsigned char numBlocks, std::size_t blockSize, bool checkIndexes ) const;
    整合性チェック。
    想定以上のフリーブロックがないか?フリーリストの先頭インデックスが正当か?
    chunkIndexesがtrueであれば、フリーリストの連結に不整合をチェック。
    チャンク外のインデックスはあるか?2重に連結されていないか?、フリーブロックの個数はblockAvaliable_と同一か?

00126 bool IsBlockAvailable( void * p, unsigned char numBlocks, std::size_t blockSize ) const;
    渡されたブロック(p)が利用可能かどうかをチェックする。trueならば利用可。falseなら利用不可。
    フリーリスト内のものであれば利用可能と判断される。

00130 inline bool HasBlock( void * p, std::size_t chunkLength ) const
    渡されたポインタ(p)がそのチャンクから確保されたものかどうかを返す

00136 inline bool HasAvailable( unsigned char numBlocks ) const
    numBlocksのフリーブロックがあればtrue,そうでなけばfalse

00139 inline bool IsFilled( void ) const
    チャンクが満杯かどうか?フリーなブロックを持っているかどうか?
    チャンクが満杯ならばtrue、そうでなければfalse。

00143 unsigned char * pData_;
    チャンクが保持しているバッファ

00145 unsigned char firstAvailableBlock_;
    フリーリストの先頭を示すインデックス

00147 unsigned char blocksAvailable_;
    チャンク全体でのフリーブロックの数

ICPC 2010 Japan Domestic Problem D ぐらぐら

問題

下のコード解説
1.ピースにユニークなラベルをつける。
2-1.ピースAの上にピースBがあるとき onPiece[A][B] がtrueになるような配列を作る
2-2.ついでに下のピース(地面)と接している左端と右端のピースを求めておく
3.onPiece をウォーシャルフロイドで推移閉方に拡張
4.すべてのピースに対して、そのピースに乗っているブロックの重心求めて安定かどうか調べる

ピースごとのモーメントとブロック数をラベル付けするときに求めておけば、4のなかのモーメント計算を省略できる。
もっと単純にならんかなー。

ICPC 2010 Japan Domestic Problem C ポロック予想

問題

すわ数論か!とか思ったら、力技で余裕だった。オンラインジャッジだと通らないかも。

ICPC 2010 Japan Domestic Problem B 迷図と命ず

問題

3年ぐらい前なら壁じゃなくて通れないブロックだったろうなあ、と問題読んで思った。


ICPC 2010 Japan Domestic Problem A 角角画伯,かく悩みき

問題

2010年度の国内予選A問題。
今年は問題が全部で7問になってたり、今までになくいやらしい入力のB問題とか、ダイクストラが無いとか、動的計画法がでたりなど去年までと比べ難しくなったと思う。
去年はマッチングが出たりしたけど今年はそういうのは無し。毎年毛色を変えるのだろうか?それはそれで面白い。対策練れるぐらいにパターン化されてるのも面白いけど。

難易度は
A < B <= C < D <= E < F << G
あたり?

SmallObj覚書

SmallObjというかFixedAllocator?

・確保/開放がLIFOになってる分には速いが、ランダムな確保/開放は遅い
 FixedAllocator::VicinityFind や FixedAllocator::Allocate にはチャンクの線形検索が入っている。最後に使用されたチャンクがキャッシュとして保持されているため、そのキャッシュに引っかかった場合(オブジェクトの確保/解放がLIFOになっている場合)は検索が入らないけど、そうでない場合(ランダムな場合)には検索が入りまくる。この検索が(特にパラメータ指定をミスってチャンクの数がすごく多いような場合には)遅い。

・チャンクの検索が遅いことに対する改善案
 フリーブロックを持ったチャンクとそうでないチャンクを別々のリストで管理する
 O(1)でブロックからチャンクを求められる仕組みを導入する

改善案を施すとパラメータ指定(チャンクサイズとか)をミスったようなケースでも大抵高速に動くようになった。無論代償はある。というか無いわけが無い。

・他
 インデックスで管理しているやつをポインタに差し替えることで、インデックスにまつわる幾つかの演算を省くことができ、わずかだけど高速化できる。変わりに最小確保サイズが1byteから4byteになるが、そもそも1~3byteの要求がそんなにあるのか?という話になる。


検索フォーム
ユーザータグ

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

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