空のノート - note of void.


Menu

Navi
Auther
Webclap
Search
Categories
Archives
Recent
Comments
Trackbacks
Advertise
RSS1.0 XML


Entries


2010-07-18

Cuckoo Hashing

探索を高速に行うデータ構造であるハッシュテーブルの一種に、Cuckoo Hashingという物があります。 探索の高速化は一つのテーマでもあり、私も興味があるので実装してみました。 結論から言えば、探索は通常のチェイン法ハッシュテーブルに比べれば速くないようです。 ハッシュ関数の衝突が起こる(チェイン法ならバケツに2個以上の要素がぶら下がる)場合はCuckoo Hashingなら速度低下もありませんが、それが頻繁に起こる場合はまずハッシュ関数を取り替えるか、二分探索木を検討する方が筋が正しい気がします。 挿入・削除は意外にもCuckoo Hasingの方が速かったですが、差は微妙なものでした。

// 参考

container            | insert | find(lo)| find(mid)| erase
----------------------------------------------
std::set             |  1.172 |  0.031  |  1.110  |  1.312
std::unordered_set*1 |  0.547 |  0.125  |  0.156  |  0.359
std::unordered_set*2 |  0.562 |  0.391  |  0.359  |  0.453
CuckooHashSet        |  0.343 |  0.282  |  0.250  |  0.328

// *1 max_load_factor(1.0f);
// *2 max_load_factor(4.0f);

2009-12-24

Direct2D

最近のビデオカードでは2Dのハードウェアアクセラレーションが取り外されており、GDI等の2D描画は軒並み速度低下しているようです。 Windows 7でもAPI自体が完全にソフトウェアエミュレーションに移行し、時代は代わりにDirect2DとDirectWriteを使えという流れのようで。

Direct2Dは概ね2D描画のためのDirect3D 10.1のラッパのようです。 ベクトルグラフィックス(線や円等の図形)の機能をポリゴンを使って3Dハードウェアを使うようにしていたり高速化を図っているらしいです。 2Dの性質上、CPU側で行う処理は3Dに比べて多くなりそうですが、ある程度ハードウェアの能力活用を期待出来るという点では意義のある事でしょう。

まあ、GDIがlegacy扱いになった以上今後は何もかも3Dハードウェアの上かCPUでやらざるを得ないのでしょう。 しかしDirectX 10.1はSDKがWindows 7で提供される?ので、開発機がXPでは今すぐどうこう出来る話でもありませんけども。


2009-12-12

xpressive → regex

Tugumiでは正規表現ライブラリにboost::xpressiveを使っていましたが、個別ビルドが不要な代わりに大量のテンプレートを実体化するためオブジェクトサイズが大きくなる欠点があります。 最近そのあまりのオブジェクトデータ量にリンカがメモリ不足で停止するようになってしまったので、boost::regexに置き換える事にしました(メモリが1.7GBあっても足りないとは予想外…)。 置き換えた結果はと言うと、6MBのオブジェクトファイルが800KBに減ってサイズ縮減に成功。 リンカも落ちずに走るようになりました。

そもそもxpressiveと同じような仕組みのspirit v2も大量にメモリを喰っている事は予想に難くないのでそちらの方を先に対処するのが筋ではありますが、こちらは今更作り直すのも時間が掛かるので現状維持です。 スタティックライブラリにしてサイズが500MB超えてますが何とか。

staticオブジェクトのデストラクタで他のstaticオブジェクトを使ってはいけない

個人的には盲点な問題で、当たり前と言えば当たり前ですが気付くのに少し時間が掛かりました。 Effective本にも書いてありませんでしたし、ネットでもあまり見かけない話題です。

以下のようなstaticオブジェクトa、および関数ローカルのstaticオブジェクトbがあるとします。

A a;

B &get_b() {
    static B b;
    return b;
}

オブジェクトaはstatic初期化タイミングで初期化され、オブジェクトbはget_b関数が呼び出された時点で初期化されます。 ここまでは問題ありません。 関数ローカルstaticオブジェクトの遅延初期化は、staticオブジェクトが他のstaticオブジェクトに依存するために使われる事はよくあります。

しかし、オブジェクトaが構築完了した後の任意のタイミングでget_bを呼び出しオブジェクトbを構築し、かつクラスAのデストラクタが関数get_bを呼び出している場合、未定義の動作になります。 構築される順番はa→bなので破棄される順番はb→aであり、aの破棄時には既にbは解体済みだからです。

回避する方法としては、クラスAのコンストラクタでget_bを呼び出しておくのが簡単でしょうか。 そうすればbの寿命がaの破棄後まで延長されるので不正なアクセスをせずに済む事になります。 しかしながら、こういう対策をするように*気をつけなければ*いけないことが増えるのは事実なので、望ましくは対策不要であるように設計しておくのが最上でしょう。


2009-05-30

boost::spirit v2

前回で書いた構文解析が遅い件、どうもspiritのast_parseを使って構文木を構築する部分が遅いような感じです。 プログラム上、そこを変更するとなると解析部全体の見直しが必要になるため、結局パーザを最初から書き直すことに。 解析ライブラリを再度選ぶに当たってはlex/yaccやre2c/bison等という手も考えたのですが、APIが再入可能でなかったり出来れば依存ライブラリを増やしたくないという事情もあり、折角なのでboostに1.36から入ったspirit v2を使ってみる事にしました。 ドキュメントがまだ不完全なのである程度自分でソースを調べながら使わなければならないのですが、やはり新しいものということで実際に使ってみたいというわけです。

v2の今までと違う最大の点といえば、karma書式化出力ライブラリ、lex字句解析ライブラリ、qi構文解析ライブラリ(+phoenix)という構造に分割された事でしょうか。 と言っても今までの機能に相当するのはqiだけで、他の二つは実質新規追加のようなものです。 lexは元々別のlexertlというライブラリをspiritに取り込んで協調動作のためのラッパを被せたものらしいです。 ちなみにTugumiでは出力は不要なのでkarmaは使いません。

これらは内部的にはboost::proto(Expression Templateライブラリ)を使っているので、ソースが従来に輪をかけて激しく読みづらいです。 ステップ実行がほとんど無理な程入り組んでいるので使い始めてからちょっと後悔しましたが、何とか判ってきたのでこのまま頑張ってみようと思います。