頻度計数における unordered_map の調整（C++）

形態素の頻度をカウントするというシンプルなタスクで std::tr1::unordered_map の性能について実験してみました．std::string より const char * の方がメモリを節約できるというような軽い内容です．

実験概要

実験環境は以下のとおりです．

入力として使用したのは，ウェブコーパスから抽出した形態素を改行区切りで保存したファイルです．

  • 入力
    • サイズ：815,793,701 bytes
    • 形態素数：133,940,786
    • 異なり数：516,612

形態素の入力については，std::ios::sync_with_stdio(false) を呼び出した後で std::getline() を使うようにしています．各行が短いので，オーバーヘッドが大きくなっています．fgets() や getline() などに切り替えることで，かなり短縮できるかもしれません．

実験概要は以下のようになっています．

  • getline
    • 形態素の読み込みにかかる時間を計測します．
  • map
    • std::map<std::string, int>
    • std::tr1::unordered_map を使いましょう．
  • unordered-map
    • std::tr1::unordered_map<std::string, int>
    • ベースラインです．基本はこれで問題ありません．
  • custom-map0
  • custom-map1
    • 自作 String, StringPool + FNV Hash + std::strcmp()
      • String: const char *
    • std::string はメモリを使いすぎだということで，文字列を格納するための領域を自前で管理するようにしてみました．
  • custom-map2
    • 自作 String, StringPool + FNV Hash + 自作比較関数（ポインタのインクリメント）
    • std::strcmp() の関数呼び出しが地味に効いているかもしれないと思って試してみました．†
  • custom-map3
    • 自作 String, StringPool + FNV Hash + 自作比較関数（カウンタのインクリメント）
    • ポインタとカウンタとどちらが速いかなんて気にしても仕方がない…ということはなさそうです．†
  • custom-map4
  • custom-map5
    • 自作 String, StringPool + hashlittle() + 自作比較関数（カウンタのインクリメント）
      • String: const char *, std::size_t
    • std::string はメモリを使いすぎ（以下略．

†：ハッシュ関数の中身や最適化の効果は環境によって異なるので，実際のところは試してみないと分かりません．

実験結果

実験結果（処理時間とメモリ使用量）は以下のとおりです．

- 処理時間 メモリ使用量
getline 13,376 ms -
map 184,964 ms 64 MiB
unordered-map 36,312 ms 52 MiB
custom-map0 31,870 ms 52 MiB
custom-map1 31,281 ms 28 MiB
custom-map2 31,036 ms 28 MiB
custom-map3 29,831 ms 28 MiB
custom-map4 32,467 ms 52 MiB
custom-map5 29,269 ms 35 MiB

処理時間については，std::tr1::unordered_map の方が std::map より明らかに高速です．std::map を使っているコードが手元にあるのであれば，std::tr1::unordered_map に切り替えるだけでもかなりの高速化が期待できます．一方，custom-map への切り替えにおいては，処理時間はそれほど短縮されません．

メモリ使用量については，std::string から自作のクラスに移行することでメモリを節約できます．簡単な機能のみを実装するのであれば 100 行くらいなので，それほど手間はかかりません．

追記（2010-11-29）：寝惚けながら書いたおかげか投げやりな終わり方になっていたので，std::string について，少し書き足しておきます．

実際のところ，ほとんどの用途では std::string を使っておけば問題ないと思います．今回のタスクにしても，この規模であれば，std::string をそのまま使うのが最適な選択です．30 秒で終わるタスクに 100 行もコードを加えるなんて，どう考えても趣味の領域です．テストも必要になりますし，採算が合いません．

あえて自前のクラスを用意するような状況としては，現実にメモリが不足しそうなときや，文字列の実体を持たせたくないときなどでしょうか．後者については，substr() が分かりやすいと思います．std::string では新しく確保した領域に substr() で指定した部分をコピーするという大仕事になりますが，ポインタと長さのみを持つクラスであれば，ポインタと長さを設定するだけになります．

結局のところは適材適所が一番ということで，ありふれた結論に落ち着きます．

# とはいえ，あまり意味がないと分かっていても，何か新しいことを試してみたり，効率化を施したりしてしまうものです．

実際のコード

以下，custom-map0 から custom-map3 までで使ったコードです．

class String {
 public:
  String() : str_(NULL) {}
  explicit String(const char *str) : str_(str) {}
  String(const String &str) : str_(str.str_) {}
  ~String() {}

  String &operator=(const String &str) {
    str_ = str.str_;
    return *this;
  }

  bool operator==(const String &rhs) const {
    return std::strcmp(str_, rhs.str_) == 0;
  }

  const char &operator[](std::size_t index) const {
    return str_[index];
  }
  const char *str() const {
    return str_;
  }

 private:
  const char *str_;
};

class StringPool {
 public:
  StringPool() : chunks_(), ptr_(NULL), avail_(0) {}
  ~StringPool() {}

  String Clone(const char *ptr, std::size_t length) {
    if (length >= avail_) {
      NewChunk(length + 1);
    }
    for (std::size_t i = 0; i < length; ++i) {
      ptr_[i] = ptr[i];
    }
    String clone(ptr_);
    ptr_[length] = '\0';
    ptr_ += length + 1;
    avail_ -= length + 1;
    return clone;
  }

 private:
  enum { MIN_CHUNK_SIZE = 4096 };

  std::vector<std::tr1::shared_ptr<std::vector<char> > > chunks_;
  char *ptr_;
  std::size_t avail_;

  void NewChunk(std::size_t chunk_size) {
    if (chunk_size < MIN_CHUNK_SIZE) {
      chunk_size = MIN_CHUNK_SIZE;
    }
    std::tr1::shared_ptr<std::vector<char> > new_chunk(
        new std::vector<char>(chunk_size));
    chunks_.push_back(new_chunk);
    ptr_ = &new_chunk->front();
    avail_ = chunk_size;
  }

  // Disallows copy and assignment.
  StringPool(const StringPool &);
  StringPool &operator=(const StringPool &);
};

class StringHash {
 public:
  uint32_t operator()(const String &str) const {
    uint32_t a = 0x811C9DC5;
    for (const char *p = str.str(); *p != '\0'; ++p) {
      a *= 0x01000193;
      a ^= static_cast<unsigned char>(*p);
    }
    return a;
  }
};

以下，custom-map4 と custom-map5 で使ったコードです．

class String {
 public:
  String() : ptr_(NULL), length_(0) {}
  String(const char *ptr, std::size_t length) : ptr_(ptr), length_(length) {}
  String(const String &str) : ptr_(str.ptr_), length_(str.length_) {}
  ~String() {}

  String &operator=(const String &str) {
    ptr_ = str.ptr_;
    length_ = str.length_;
    return *this;
  }

  bool operator==(const String &rhs) const {
    if (length_ != rhs.length_) {
      return false;
    }
    if (ptr_ == rhs.ptr_) {
      return true;
    }
    for (std::size_t i = 0; i < length_; ++i) {
      if (ptr_[i] != rhs.ptr_[i]) {
        return false;
      }
    }
    return true;
  }

  const char &operator[](std::size_t index) const {
    return ptr_[index];
  }
  const char *ptr() const {
    return ptr_;
  }
  std::size_t length() const {
    return length_;
  }

 private:
  const char *ptr_;
  std::size_t length_;
};

class StringPool {
 public:
  StringPool() : chunks_(), ptr_(NULL), avail_(0) {}
  ~StringPool() {}

  String Clone(const String &str) {
    if (str.length() > avail_) {
      NewChunk(str.length());
    }
    for (std::size_t i = 0; i < str.length(); ++i) {
      ptr_[i] = str[i];
    }
    String clone(ptr_, str.length());
    ptr_ += str.length();
    avail_ -= str.length();
    return clone;
  }

 private:
  enum { MIN_CHUNK_SIZE = 4096 };

  std::vector<std::tr1::shared_ptr<std::vector<char> > > chunks_;
  char *ptr_;
  std::size_t avail_;

  void NewChunk(std::size_t chunk_size) {
    if (chunk_size < MIN_CHUNK_SIZE) {
      chunk_size = MIN_CHUNK_SIZE;
    }
    std::tr1::shared_ptr<std::vector<char> > new_chunk(
        new std::vector<char>(chunk_size));
    chunks_.push_back(new_chunk);
    ptr_ = &new_chunk->front();
    avail_ = chunk_size;
  }

  // Disallows copy and assignment.
  StringPool(const StringPool &);
  StringPool &operator=(const StringPool &);
};

// This hash function is defined in lookup3.c
uint32_t hashlittle(const void *key, size_t length, uint32_t initval);

class StringHash {
 public:
  uint32_t operator()(const String &str) const {
    return hashlittle(str.ptr(), str.length(), 0);
  }
};