LoginSignup
8
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@Nabetani(鍋谷 武典)

map, unordered_map, flat_map の速度比較(operator[]編)

Posted at

std::map と std::unordered_map と boost::flat_map の速度比較をする。

の続き。

結論

  • std::unordered_map が速い。
  • std::map と boost::flat_map はちょうど同じぐらいの速さ。

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

やったこと

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

やらなかったこと

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

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

C++17

まずは C++17 のソースコード。

c++17(bench.cpp)
// clang++ -std=c++17 -O2 bench.cpp -o bench
# include <iostream>
# include <chrono>
# include <map>
# include <unordered_map>
# include <string>
# include <vector>
# include <cstdlib>
# include <random>
# include <boost/container/flat_map.hpp>

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

template <typename map_t>
std::pair<map_t, std::vector<std::string>> prepare(int len, int count)
{
  map_t map;
  std::vector<std::string> keys;
  keys.reserve(count);
  for (int vi = 0; vi < count; ++vi)
  {
    std::string s;
    s.reserve(len);
    for (int si = 0; si < len; ++si)
    {
      s += randchar();
    }
    keys.push_back(s);
    map.emplace(std::move(s), vi);
  }
  return {map, keys};
}

template <typename map_t>
void run(int len, int count)
{
  auto [map, keys] = prepare<map_t>(len, count); // 構造化束縛(C++17)
  int sum = 0;
  auto start = std::chrono::high_resolution_clock::now();
  for (auto const &key : keys)
  {
    sum += map[key];
  }
  auto end = std::chrono::high_resolution_clock::now();
  std::cout
      << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() * 1e-6
      << "ms"
      << "," << sum // 最適化されないように sum を使ってみる。
      << 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;
  case 'f':
    run<boost::container::flat_map<std::string, int>>(len, count);
    break;
  default:
    std::cout << "unexpected type" << std::endl;
  }
}

まあ前回とほぼ同じだけど。

ruby2.6

上記の C++ のコードを走らせて csv に変換するスクリプト

ruby2.6(run.rb)
require "csv"
require "pp"

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

N=15

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

%x( clang++ -std=c++17 -O2 bench.cpp -o bench )

p :len
CSV.open( "len.csv", "w" ) do |csv|
  data = %w( u m f ).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

p:count
CSV.open( "count.csv", "w" ) do |csv|
  data = %w( u m f ).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

これなんて、前回と全く同じだけど。

R

上記のスクリプトの実行結果をグラフにする R のプログラム

R(graph.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.001,100))
lines(dt$len,dt$u,col="blue",type="o",pch=20,xlab="foo",ylab="hoge")
lines(dt$len,dt$f,col="green",type="o",pch=20,xlab="bar",ylab="fuga")
legend("bottomright", legend=c("map", "unorderd_map", "flat_map"),pch=20,col=c("red","blue","green"),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.001,100))
lines(dt$count,dt$u,col="blue",type="o",pch=20,xlab="foo",ylab="hoge")
lines(dt$count,dt$f,col=" green",type="o",pch=20,xlab="foo",ylab="hoge")
legend("bottomright", legend=c("map", "unorderd_map", "flat_map"),pch=20,col=c("red","blue","green"),lwd=1,lty=1)
dev.off()

これもほぼ同じ。定数が違うだけ。

測定結果

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

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

image.png

対数目盛注意。

最初だけ std::unordered_map が速いけど、文字列の長さが1万になる前に失速して（？） std::map や std::flat_map と同じ速さになる。
しかし、逆転はされない。意外。

std::map と boost::flat_map は、びっくりするぐらい同じ速さ。

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

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

対数目盛注意。

こちらは std::unordered_map が一貫して 2〜3倍速い。
hash 関数が速ければ std::unordered_map の独壇場ということだろう。
std::map と boost::flat_map は、概ね同じ速さ。

要素数が増えると std::map と std::unordered_map の差が開くと予想していたんだけど、そうでもなかった。

まとめ

  • operator[] なら、std::unordered_map が速い。
  • std::map と boost::flat_map は、同じ速さと言っていいと思う。誤差程度。

3つの記事のまとめ

と、3つの連想配列の速度比較をした。

操作 std::map std::unordered_map boost::flat_map
emplace 普通 hash 関数が速ければ速い 遅い
forループ やや遅い 普通 速い
operator[] 普通 hash 関数が速ければ速い 普通

という具合。

選択のフローはこんな感じかな：

image.png

フローだけ見るとわかりにくいけど、ファーストチョイスは std::unordered_map だと思う。
整列が必要な場合は少ないし、速いHASH関数が使える場合は多い。
あと。メモリの消費具合とか、他の視点も必要かもね。

8
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
8
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?