[プログラミング] Google Sparsehashを使うときの注意点

持橋さんの書かれたgoogle-sparsehashと自作のsplay-treeとの速度比較をした結果の記事を読んで、さすがに速度に200倍近くの差がでるのはおかしいだろうということで原因を探ってみた。

結論としてはGoogle Sparsehashを使うときに__gnu_cxx::hashを使わない方がよいということが分かった。

時間の測定に用いられているコードは概ね以下のコードと同じである。

#include <iostream>
#include <google/sparse_hash_map>
#include <cstdio>
#include <cstring>
#include <ext/hash_map>

using namespace std;
using google::sparse_hash_map;

typedef __gnu_cxx::hash<const char *> HashFunc;

struct eqstr
{
  bool operator() (const char *a, const char *b) const
  {
    return (a == b) || (a && b && strcmp(a,b) == 0);
  }
};

int read_word (FILE *fp, const char *buf)
{
  return fscanf(fp, "%s", buf);
}

int main (int argc, char *argv[])
{
  FILE *fp;
  char s[BUFSIZ];
  sparse_hash_map <const char *,int, HashFunc ,eqstr> lexicon;
  sparse_hash_map <const char *,int, HashFunc ,eqstr>::iterator it;

  if ((fp = fopen(argv[1], "r")) == NULL){
    perror("fopen");
    exit(1);
  }

  while (read_word(fp, s) != EOF){
    if ((it = lexicon.find(s)) == lexicon.end()){
      lexicon[strdup(s)] = 1;
    } else {
      it->second++;   // count++;
    }
  }
  fclose(fp);
  return 0;
}

これを例えば以下のperlスクリプトで生成した1から10万までの数字がランダムに1回ずつ現れるテキストで実行時間を測ると2.4秒かかり、50万件の場合は36秒かかる

use List::Util 'shuffle';
print "$_\n" for(shuffle((1 .. 100000)));

データを5倍にしたときに実行時間がリニアに増えないため、大量のハッシュの衝突が起きてそうだということが予想できる。
実際にハッシュ関数をtypedefしている部分を

typedef tr1::hash<const char *> HashFunc;

にして時間を測ったところ10万件の場合0.149秒、50万件の場合0.844秒かかった。

なぜこれだけかかるのかについてですが、 __gnu_cxx::hashのハッシュ関数はext/hash_fun.hの中をみると

  inline size_t
  __stl_hash_string(const char* __s)
  {
    unsigned long __h = 0;
    for ( ; *__s; ++__s)
      __h = 5 * __h + *__s;
    return size_t(__h);
  }

となっており、別の方の実験でも非常に衝突が起こりやすいことが報告されており、あまりよくないハッシュ関数となっている。

一方でtr1::hashはfnv hashといわれる、高速で比較的ばらつきやすいハッシュ関数を利用しておりこれが実行時間の短縮につながっていると思われる。

gcc 4系列を使っている場合は./configure時にtr1::hashがデフォルトのハッシュとして設定されるが、そうではない場合 __gnu_cxx::hashが選ばれ、ハッシュ関数が適切でないためsparse_hash_mapの性能が低下することがありえます。これを回避する方法としては自分でハッシュ関数を定義するというもので例えば各種マップ実装の性能比較のテストで用いられている

struct stringhash {                      // hash function for string
  size_t operator()(const string& str) const {
    const char *ptr = str.data();
    int size = str.size();
    size_t idx = 19780211;
    while(size--){
      idx = idx * 37 + *(uint8_t *)ptr++;
    }
    return idx;
  }
};

を用いるという方法があります。

いくつかの検索結果を見たところ、ハッシュ関数が適切でないことからsparse_hash_mapが思ったような性能が出ないという記事がいくつか見受けられたので、もし性能がでないと思われたらハッシュ関数を変えることを検討してみたらどうでしょうか。