読者です 読者をやめる 読者になる 読者になる

空想犬猫記

※当日記では、犬も猫も空想も扱っておりません。(旧・エト記)

VC++のunordered_set/unordered_mapが遅い件

正確に言うと、insertが同種のset/mapに比べて圧倒的に遅い。

最近、メモリの節約のために辞書的なオブジェクトを作成して、同値のオブジェクト(例えば文字列)を再利用するようなコードを書いたところ、unordered_set/unordered_mapで思うような性能が得られなかった。

コンテナ以外のアロケーションの影響を受けないように、あらかじめ文字列を用意して、それを辞書に登録する以下のサンプルコードを書いて、Visual Studio 2015でプロファイルをとってみた。

#include "stdafx.h"

using namespace std;

namespace
{
  struct char_cmp : public binary_function<const char*, const char*, bool>
  {
    result_type operator()(first_argument_type l, second_argument_type r) const
    {
      if (!l)
      {
        if (!r) return false;
        return true;
      }
      else
      {
        if (!r) return true;
        return strcmp(l, r) < 0;
      }
    }
  };

  struct char_hash : public unary_function<const char*, size_t>
  {
    size_t operator()(argument_type key) const
    {
      return hash_value(key);
    }
  };

  struct char_equal_to
  {
    typedef const char* first_argument_type;
    typedef const char* second_argument_type;
    typedef bool result_type;

    bool operator()(first_argument_type pL, second_argument_type pR) const
    {
      return strcmp(pL, pR) == 0;
    }
  };

  template <typename Set> __declspec(noinline) void TestSet(const vector<string>& samples)
  {
    Set set;
    for (auto& s : samples) set.insert(s.c_str());
  }
}

int main()
{
  vector<string> samples;
  samples.reserve(100000);

  default_random_engine generator;
  uniform_int_distribution<int> distribution(33, 126);

  for (int i = 0; i < 100000; ++i)
  {
    samples.emplace_back();
    auto& str = samples.back();
    str.reserve(300);
    for (int j = 0; j < 300; ++j)
      str += distribution(generator);
  }

  TestSet<unordered_set<const char*, char_hash, char_equal_to>>(samples);
  TestSet<set<const char*, char_cmp>>(samples);
  return 0;
}

で、結果がこちら

f:id:xoinu:20161210085710p:plain

サンプルの要素数が増えれば増えるほど差は広がるばかり。確認のためTDM-GCCで同等のコードを書いてみたところ、むしろunordered_set/unordered_mapの方がinsertは高速だったので、これはVisual StudioSTLの実装特有の問題っぽい。

Visual Studio上でunordered_set/unordered_mapを旧来のset/mapの代わりに使う際には、必ずベンチマークをとって、挿入性能劣化に見合う検索性能の向上の恩恵に与れるかどうかを確認したほうが良さそうだ。

やれやれ……

追記:
xoinu.hatenablog.com
2年前にint型のコンテナで挿入のパフォーマンスのチェックをやってた。そのときの結果と少し矛盾している。これを見るにVC++のxhashヘッダにあったstd::hash_value()関数がよろしくないのかもという気がする。