C言語で書かれたプログラムで,fcgiのAPIを使うためにはfcgi_stdio.hをincludeしなければなりません.fcgi_stdio.hをインクルードするとprintfやら,stdoutなどなど,stdio.hの名前空間がFCGI用のものにdefineされます.

そこで,注意が必要で,fcgi_stdio.hを最後にインクルードしなければほかのincludeファイルに上記のdefineが上書きされてしまってFCGIの機能が使えなくなることがあります.fcgi_stdio.hを使っていて,FCGIの名前空間の問題が解決できない場合はfcgi_stdiot.h最後にインクルードしてコンパイルしてみましょう.


ここ何回かgperfのメモを取ってきて,かつここには書かなかったけど個人的にサンプルプログラムを作って改めて思ったんだけど,gperfってルックアップがめちゃくちゃ高速なわけですね.完全ハッシュなので当然っちゃー当然なのですが.早くてお手軽っての
がgperfの良いところなわけですが.さてさて,早いのわかったけど,どれぐらい早いの?ってのは何かの指標がなければわかりませんね.そこで,今のところ最強に早いといわれているTokyo Cabinetのhash DBMとのスピードの比較をしてみようという,結構無意
味なベンチテストをやってみた.

データの準備

やったことは単純で,ランダムにkey, valueのセットを作成し,それぞれ10セット,100セット,1000セット,10000セット,100000セット,のDBの作成時間と,ルックアップの時間を比較してみた.ちなみにkeyは[A-Za-z1-9]の文字列からランダムに選択した32
文字で構成され,valueは[1-9]の数字からランダムに選択した5桁の数値となります.

データの具体例

ls8NRbatYxDtR7xFYI33gR6Xd7UISN5E,64424
9sNbbs8fSvLC4XKGOyIVkE2pG3qDdoXN,81452
kC7gEuCC9YjEXclUjNHSqZYMSoRxCcIv,92562
85cH1CKlczbmXukZAk7EDbVyHee12mRl,27441
mBCqaxbg4xnT6qi67BxoosYnvefcPmAC,84235
IQ88EVLy5lOswuClaZsN6N8En6AK6BOi,38926
FinG7fDmDoEuLCeotyHcsAr5vF9Puz28,33697
bfMhSn3ee8tdB7PD348aCgDCceTv4p5N,84162
8DkGQWkpVUh7MvyVrULQfj49aLbOAYr9,29667
EoaxVsQIZbD9CXlumXeCGH4S5HVNQ7Ex,61271

上記のようなデータ(10set, 100set, 1000set, 10000set, 100000set)をそれぞgperfを使って完全ハッシュ関数のコードと,Tokyo Cabinetのhash DBMを作成した.

作成の時間比較

#of keys gperf TC hash DBM
10 0.002sec 0.035sec
100 0.009sec 0.036sec
1000 0.435sec 0.04sec
10000 1m26.67sec 0.082sec
100000 NaN 0.0496sec
  • gperfでのkeyの数100000万個の場合は75分以上たっても終わらなかったためあきらめました.今度終わったらまた書きます.

keyの数が増えると圧倒的にTCの方が早いですね.まあ,完全ハッシュ関数だから時間がかかるのは当然か...しかし,TCのDBMの作成は超はええなああ...keyの数が莫大になるとちょっとgperfは使い物にならないかもしれないなあ.

ルックアップスピードの比較

ルックアップスピードの比較は,DBに入ってるkeyをすべてイテレーションをして個々のkeyのvalueを引くという処理をそれぞれ1万回やりました.具体的にはkeyの数が10個の場合のテストは「イテレーションで10個のkeyを引く * 10000回」なので100000回のルッ
クアップをすることになります.

# of keys gperf TC hash DBM
10 0.012sec 0.035sec
100 0.097sec 0.330sec
1000 1.057sec 3.317sec
10000 11.526sec 33.531sec

綺麗にgperfのほうが約3倍早いですね.

まとめ

  • gperfはkeyの数が膨大になるとコード生成がものすごく時間がかかる,TCはコンスタントに早い
  • gperfはルックアップがtc hash DBMより約3倍早い

しかし,gperfはデータの更新をするたびにまたコードを生成しなおさなければなりません.TCはデータの追加も削除も高速にできます.
つまりユースケースによってどちらがいいかを選択すれば良いわけですね.前にも書いたのだけどgperfはデータの更新が無くて,ルックアップの数が莫大な数のユースケース,keyの数は1万以下ぐらいで適切かもしれません.TCのようなDBMはその逆で,データの
更新が頻繁にある場合で,かつkeyの数が莫大な場合に適切だと思います.

ちょっと長くなったけど,すごい自己満足なエントリーとなってしまった.しかも走り書きなので超まとまり悪くなったなあ.

一応将来の自分のために今回使ったプログラムの一部をメモっておく.

  • createData.pl (ランダムなデータの作成)
use strict;
use warnings;
use String::Random;

for(my $i = 0; $i < 100000; $i++){     my $rand_key = String::Random->new->randregex('[A-Za-z1-9]{32}');
    my $rand_val = String::Random->new->randregex('[1-9]{5}');
    print "$rand_key,$rand_val\n";
}
  • inputTc.pl (ランダムデータをTCにぶち込む)
use strict;
use warnings;
use TokyoCabinet;

my $save_path = shift @ARGV;

my $hdb = TokyoCabinet::HDB->new();
$hdb->tune(200000);
$hdb->open($save_path, $hdb->OWRITER|$hdb->OCREAT|$hdb->OTRUNC);

while(my $line = <>){
    chomp $line;
    my ($key, $val) = split ",", $line;
    $hdb->put($key, $val);
}
$hdb->close();
  • gperf (完全ハッシュ関数を生成するときのコマンド)
gperf -CtGD -Z TrainHash -L C++ dataFile
  • lookup.cpp (TCとgperfのルックアップをしたプログラム)
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include "perfect_hash.hpp"

int main(int argc, char** argv)
{
  std::string fileName = argv[0];
  std::string listFile = argv[1];
  std::string tcPath = argv[2];
  std::string mode = argv[3];
  std::vector keys;

  /* create key list*/
  std::ifstream ifs(listFile.c_str());
  std::string line;
  while(std::getline(ifs, line)){
    keys.push_back(line);
  }

  /* create gperf instance */
  TrainHash train;

  /* create tokyocabinet instance */
  TCHDB* hdb = tchdbnew();
  tchdbopen(hdb, tcPath.c_str(), HDBOREADER);

  for(unsigned int j = 0; j < 10000; j++){
    for(unsigned int i = 0; i < keys.size(); i++){
      if(mode == "gperf"){
        const struct Train* rv = train.in_word_set(keys[i].c_str(), std::strlen(keys[i].c_str()));
        //std::cout << keys[i].c_str() << "\t" << rv->val << std::endl;                                                                                                             
        if(!rv){
          std::cerr << "error: gperf not found key" << std::endl;
          exit(1);
        }
      } else if(mode == "tc"){
        char* val = tchdbget2(hdb, keys[i].c_str());
        //std::cout << keys[i].c_str() << "\t" << val << std::endl;                                                                                                                 
        if(!val){
          std::cerr << "error: tc not found key" << std::endl;
          exit(1);
        }
        std::free(val);
      }
    }
  }
  tchdbclose(hdb);
  tchdbdel(hdb);
  return 0;
}


超個人的なエントリで恐縮です。
先日完全ハッシュ関数に関して調査していたのですが、

perfect hash function(完全ハッシュ関数)の概要|http://blog.broomie.net/index.cgi?id=7

そこで、GNU gperfというアプリケーションが完全ハッシュ関数の生成器として存在するって話を少ししだけれども、かくいう僕もgperfを使わせていただいておるのですが、実際にどんなアプリケーションやユースケースで使われているのかなあ、と興味を持った
ので軽い気持ちで調べてみた。

gperfの本家のマニュアルを調べてみると確かに、それらしいことが書いてある。

gperf currently generates the reserved keyword recognizer for lexical analyzers in several production and research compilers and language processing tools, including GNU C, GNU C++, GNU Java, GNU Pascal, GNU Modula 3, and GNU indent. Complete C++ source code for gperf is available from http://ftp.gnu.org/pub/gnu/gperf/. A paper describing gperf’s design and implementation in greater detail is available in the Second USENIX C++ Conference proceedings or from http://www.cs.wustl.edu/~schmidt/resume.html.

http://www.gnu.org/software/gperf/manual/gperf.html|http://www.gnu.org/software/gperf/manual/gperf.html

gperfは(GNU C, GNU C++, GNU Java, GNU Pascal, GNU Modula 3, GNU indent.)などの様々なプログラミング言語のコンパイラで予約語の認識部分の処理を担っている.

って書いてありますね。予約語のチェックはルックアップ数が多いから、gperfで高速化しているんですね。上のリストには書いてないけれども、Rubyのソースを眺めてみたら、実際にRubyも予約語のチェックはgperfでやっているんですね。Rubyをソースで落とす
とパッケージの中にlex.cというのがあって、それはgperfで出力されたソースになっていました。参考になるので今後じっくり読んでみよう。

lex.cに先頭に以下のようにコメントしてあります。

/* C code produced by gperf version 3.0.3 */
/* Command-line: gperf -C -p -j1 -i 1 -g -o -t -N rb_reserved_word -k'1,3,$' keywords  */

google code searchでgperfというキーワードで検索してみたら、4000件もヒットしたし結構色んなところで使われているんですね。ばばーっと使われている部分を見てたんだけどやっぱり、予約語のチェックみたいに、シンタックスのチェックとかで使われているみたいです。高速で簡単に使えるんだからgperfってもっと色んなところで使われてもいいような気がするんだけどなあ。。。まあ更新ができないっていうのがネックなんだけどね。


「twitterを見るのに毎回ブラウザでアクセスするのがいい加減,狂おしいほどにだるくなってきた」 + 「emacsから手を離したくない.目を話したくない.いっつもemacsのことしか考えてないよね」なので,twitterのelispを探してたら発見.

http://github.com/hayamiz/twittering-mode/tree/master

超便利すぎなので,メモメモ.適当に.emacsに書けばすぐ使えます.投稿はC-c C-s.何が便利って勝手にリロードしてくれ最新の状態にしてくれます.


perfect hash function(完全ハッシュ関数)に関する調査。

perfect hash functionとは

wikipediaにはperfect hash functionは以下のようにまとまっている。

ハッシュ関数が単射の場合、すなわち正しい入力に対して必ず異なるハッシュ値が対応する場合、これを完全 (perfect) だという。このような関数を使えば、1つのハッシュテーブルで目的のエントリを直接探すことができ、それ以外の探索の手間が生じない。
完全ハッシュ関数は、入力される範囲が予め分かっていて変化しない場合のみ成立する。例えば英語の月の名前を0から11の整数にマッピングするとか、ある辞書に掲載されている単語にハッシュ値を割り当てるといった場合である。入力の集合を与えられると、それに対応した完全ハッシュ関数を実行する最適化されたサブルーチンを出力する生成器がいくつか存在する(例えば、GNU gperf)。

wikipedi:ハッシュ関数より引用

つまりハッシュ関数で、keyが絶対に衝突せずに必ず個々のkeyのハッシュ値が必ず一意に定まるのがperfect hashingです。特徴としては、衝突がないため検索が極めて高速であること。昨今のオープンソースのソフトウェアではGNU gperfというperfect hashingのハッシュ関数を生成してくれるソフトが多く用いられている。さくっと使ってみたい場合はgperfを試してみるのが良いでしょう。gperfは複数のkey, valueのデータセットを探索できるハッシュ関数を生成してくれて、CやC++で用いることができる便利なユーティリティです。

perfect hashingはどのようなケースで有効か

Using a perfect hash function is best in situations where there is a large set, S, which is not updated frequently, and many lookups into it. Efficient solutions to performing updates are known as dynamic perfect hashing, but these methods are relatively complicated to implement. A simple alternative to perfect hashing, which also allows dynamic updates, is cuckoo hashing.

wikipedia:perfect hash function より引用

上記の引用した内容のようにperfect hashingは以下のようなケースで有効です。

  • 更新が無い莫大なkey、valueのデータセット
  • かつkeyの探索(lookup)が高頻度の場合

ダイナミックに更新が必要な場合は、dynamic perfect hashingというアルゴリズムがあるが複雑らしいです。また、シンプルであるがダイナミックに更新できるもにcuckoo hashingというのがあるらしい。ちょっとこれは興味があるから別の機会に調査してみよう。

関連事項

perfect hasingと似たアルゴリズムでminimal perfect hash function(最小完全ハッシュ関数)がある。

n 個のキーに対する完全ハッシュ関数が最小 (minimal) であるとは、その値域が n 個の連続な整数(通常 0 から n-1)の場合である。単に参照が単純化されるだけでなく、ハッシュテーブルもコンパクトになり、空きスロットができない。最小完全ハッシュ関数は単なる完全ハッシュ関数よりも求めるのが難しい。

wikipedi:ハッシュ関数より引用

最小完全ハッシュ関数は、perfect hashingでかつ、ハッシュテーブルとてもコンパクトになる。詳しい調査は別のエントリーでしようと思う。最小完全ハッシュ関数は多くの実装あり、具体的にはなどがある。