google::dense_hash_mapのset_deleted_keyメソッド

google::dense_hash_mapを使うときは、データのinsertを行う前にset_empty_keyメソッドで空のとき用のキーを指定しておく必要がある。同様にキーの削除を行う前には、set_deleted_keyメソッドで削除されたとき用のキーを指定しておかなければならない。

で、このset_deleted_keyをあらかじめ指定しておくようにしてたんだけど、そうしたら何か遅くなった？と思って、ちょっと動作速度を調べてみた。

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <google/dense_hash_map>

int main() {
  clock_t start, end;
  const int max = 20000000;

  srand(time(NULL));

  // not set_deleted_key
  google::dense_hash_map<int, int> h1;
  h1.set_empty_key(-1);
  start = clock();
  for (int i = 0; i < max; i++) { // write
    h1[i] = i;
  }
  for (int i = 0; i < max; i++) { // read
    int r = rand() % max;
    int val = h1[r];
  }
  end = clock();
  std::cout << "not_set_deleted_key: "
            << (double)(end - start) / CLOCKS_PER_SEC << std::endl;

  // set_deleted_key
  google::dense_hash_map<int, int> h2;
  h2.set_empty_key(-1);
  h2.set_deleted_key(-2);
  start = clock();
  for (int i = 0; i < max; i++) { // write
    h2[i] = i;
  }
  for (int i = 0; i < max; i++) { // read
    int r = rand() % max;
    int val = h2[r];
  }
  end = clock();
  std::cout << "set_deleted_key: "
            << (double)(end - start) / CLOCKS_PER_SEC << std::endl;

  return 0;
}

set_deleted_keyをあらかじめ指定した場合と、指定しなかった場合それぞれで、データのinsertとgetを繰り返し実行したときの処理時間を調べてみた。

% g++ dense_hash_bench.cc 
% ./a.out
not_set_deleted_key: 17.2
set_deleted_key: 17.65

びみょーな差だけど、set_deleted_keyを指定しておくと遅くなった。

ドキュメントを見てみると、set_empty_keyは初めから指定しておかないとダメだけど、set_deleted_keyはeraseが呼ばれるまでは実行しておく必要はないらしい。
http://goog-sparsehash.sourceforge.net/doc/dense_hash_map.html#6

なのでdense_hash_mapを使うときは、eraseが呼ばれる直前まではset_deleted_keyは使用しない方がよさそう。それとclear_deleted_keyを呼べばdeleted_keyもクリアされて、遅くなっていたのもの元に戻ってたので、set_deleted_keyを使用した後はclear_deleted_keyも忘れずに。

そもそもempty_keyやdeleted_keyを指定しておかないといけないかが分かっていないんだけど…。やはりアルゴリズムの中身をちゃんと勉強してないとダメだな。