Help us understand the problem. What is going on with this article?

unordered_map と map の速度比較(emplace編)

std::mapstd::unordered_map のどちらが速いのかを比較する。
コメント欄で、boost::flat_map も参戦。

この記事の続編は

結論

unordered_map の方が速いこともあるし、 map の方が速いこともある。

やったこととやってないこと

やったこと

  • C++11 で、std::map<std::string, int>std::unordered_map<std::string, int>emplace をたくさん呼んで、その部分の時間を測定するコードを書いた。
    • キーはランダムな文字列。長さはコマンドライン引数で指定
    • emplace する要素の数は、コマンドライン引数で指定
  • 上記コードからできたバイナリをたくさん呼んで csv化するスクリプトを ruby で書いた。
  • 上記コードで出来上がった csv をグラフにするスクリプトを R で書いた。
  • 全部実行した。

やってないこと

  • emplace 以外の操作の時間を測ること
  • <std::string, int> 以外のテンプレートパラメータについての調査
  • ランダムな文字列以外のキーについての調査
  • ランダムな順序以外での挿入

実験に使ったソースコード

まずは C++11 のコード。

c++11
// clang++ -std=c++11 -O2 bench.cpp -o bench
#include <iostream>
#include <chrono>
#include <map>
#include <unordered_map>
#include <string>
#include <vector>
#include <cstdlib>
#include <random>

char randchar()
{
  static std::mt19937_64 rng(0xbeef);
  std::uniform_int_distribution<> dist(1, 255);
  return static_cast<char>(dist(rng));
}

std::vector<std::string>
prepare(int len, int count)
{
  std::vector<std::string> r;
  r.reserve(count);
  for (int vi = 0; vi < count; ++vi)
  {
    std::string s;
    s.reserve(len);
    for (int si = 0; si < len; ++si)
    {
      s += randchar();
    }
    r.push_back(std::move(s));
  }
  return r;
}

template <typename map_t>
void run(int len, int count)
{
  using mapped_type = typename map_t::mapped_type;
  std::vector<std::string> srces = prepare(len, count);
  auto start = std::chrono::high_resolution_clock::now();
  map_t map;
  for (auto &&s : srces)
  {
    map.emplace(std::move(s), mapped_type());
  }
  auto end = std::chrono::high_resolution_clock::now();
  std::cout
      << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() * 1e-3
      << "ms"
      << std::endl;
}

int main(int argc, char const *argv[])
{
  char type = *argv[1];
  int len = std::atoi(argv[2]);
  int count = std::atoi(argv[3]);
  switch (type)
  {
  case 'm':
    run<std::map<std::string, int>>(len, count);
    break;
  case 'u':
    run<std::unordered_map<std::string, int>>(len, count);
    break;
  default:
    std::cout << "unexpected type" << std::endl;
  }
}

上記のソースをコンパイルした結果を、ruby で走らせる:

ruby2.5
require "csv"

def run( t, len, count )
  r = %x( ./bench #{t} #{len} #{count} ).gsub( /ms\s*/, "" )
  [t, len, count, r]
end

N=16

def out(csv,data)
  csv << %w( len count u m )
  data[0].zip(data[1]).each do |a,b|
    csv << [ a[1], a[2], a[3], b[3] ]
  end
end

CSV.open( "len.csv", "w" ) do |csv|
  data = %w( u m ).map do |t|
    N.downto(6).map do |e|
      p e
      run(t, (10**(e/3.0)).round, 1000) # 平準化のために走らせる
      run(t, (10**(e/3.0)).round, 1000)
    end
  end
  out(csv,data)
end

CSV.open( "count.csv", "w" ) do |csv|
  data = %w( u m ).map do |t|
    N.downto(6).map do |e|
      p e
      run(t, 10, (10**(e/3.0)).round) # 平準化のために走らせる
      run(t, 10, (10**(e/3.0)).round)
    end
  end
  out(csv,data)
end

そして出来上がった CSV を R でグラフにする

R
pdf("len.pdf", width=8, height=5) # 8×5 inch
dt<-read.csv("len.csv")
plot(
  dt$len,dt$m,
  col="red",
  type="o",
  pch=20,
  log="xy",
  xlab="string length",ylab="time(ms)",
  ylim=c(0.1,30))
lines(dt$len,dt$u,col="blue",type="o",pch=20,xlab="foo",ylab="hoge")
legend("bottomright", legend=c("map", "unorderd_map"),pch=20,col=c("red","blue"),lwd=1,lty=1)
dev.off()

pdf("count.pdf", width=8, height=5) # 8×5 inch
dt<-read.csv("count.csv")
plot(
  dt$count,dt$m,
  col="red",
  type="o",
  pch=20,
  xlab="item count",ylab="time(ms)",
  log="xy",
  ylim=c(0.01,200))
lines(dt$count,dt$u,col="blue",type="o",pch=20,xlab="foo",ylab="hoge")
legend("bottomright", legend=c("map", "unorderd_map"),pch=20,col=c("red","blue"),lwd=1,lty=1)
dev.off()

測定結果

結果その1 - 文字列長を変えて、要素数固定

キーになる文字列の長さを変えて測定。要素数は 1000 で固定。
image.png

両対数グラフ注意。

今回の実験ではランダムな文字列を使っている。
map の場合は比較ができればよい。比較の場合最初の数文字を見ればいいだけなので、文字数が多くなっても比較に要する時間は変わらない。
したがって、mapの方は文字列長の影響を受けない。
※ グラフがデコボコしていて気持ち悪けど、気にしないことにした。

一方unorderd_mapの場合、Hash値を計算するために文字列を最後まで舐める必要がある(と思われる)。そのため、文字列が長くなると遅くなる。

予想通りの結果だった。

結果その2 - 要素数を変えて、文字列長固定

キーになる文字列は 10文字 固定。要素数を変えて測定。
image.png

両対数グラフ注意。

unordered_map の方が速いものの、その差は1〜1.8倍程度。要素数が多くなっても差が開くことはなかった。
差が開くと予想していたので、予想は外れた。

まとめ

  • 文字列が長い要素がたくさんある(そして、最初の数文字を見れば比較が終わる事が多い)場合は、map の方が速くなりがち。
  • それ以外の場合は、unordered_map の方が速くなりがち。
  • 今回の実験は、ランダムなキーをランダムな順序で挿入している。それ以外のパターンについては今回の実験からはわからない。
Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away