Tweet

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

データの準備

やったことは単純で，ランダムにkey, valueのセットを作成し，それぞれ１０セット，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を作成した．

作成の時間比較

• gperfでのkeyの数100000万個の場合は75分以上たっても終わらなかったためあきらめました．今度終わったらまた書きます．

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

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

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

綺麗に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;
}