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


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


* [unordered_map と map の速度比較(emplace編)]( https://qiita.com/Nabetani/items/78281cc98547f8edfea4 )
* [map, unordered_map, flat_map の速度比較(forループ編)](https://qiita.com/Nabetani/items/abe39640f9fe5d15ca55) 

の続き。

# 結論

* `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++: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 に変換するスクリプト

```ruby: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: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](https://qiita-image-store.s3.amazonaws.com/0/6854/7a638ae2-cda8-bfdd-13a3-334b47ed5a2e.png)

対数目盛注意。

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

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

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

キーになる文字列は 10文字 固定。要素数を変えて測定。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/6854/b5b076b2-ff4d-472a-92dd-86ae10492f72.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つの記事のまとめ

* [unordered_map と map の速度比較(emplace編)]( https://qiita.com/Nabetani/items/78281cc98547f8edfea4 )
* [map, unordered_map, flat_map の速度比較(forループ編)](https://qiita.com/Nabetani/items/abe39640f9fe5d15ca55) 
* この記事

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

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

という具合。

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

![image.png](https://qiita-image-store.s3.amazonaws.com/0/6854/f664610c-2a06-755b-d4a1-7c25ff2f4eaa.png)


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