C++11 unordered_set benchmark

結論:
insert, erase, find: O(n)
insert ~ 100N
find ~ 50N (N以walk為倍數基準)

#include <iostream>
#include "Timer.h"
#include "Util.h"
#include <unordered_set>

int main()
{
  std::vector<int> v = generateShuffleVector(1000000);
  Timer timer;
  std::vector<int> loop = {100, 1000, 10000, 100000, 1000000};
  std::vector<int> walkt;
  std::vector<int> insertt;
  std::vector<int> findt;
  std::vector<int> eraset;

  for(auto k: loop)
  {
    int ms = 0;
    std::unordered_set<int> s1;
    //s1.rehash(1000000);
    timer.start();
    for(int i = 0; i < k; i++)
    {
      v[i];
    }
    ms = timer.stop();
    walkt.push_back(ms);

    timer.start();
    for(int i = 0; i < k; i++)
    {
      s1.insert(v[i]);
    }
    ms = timer.stop();
    insertt.push_back(ms);

    timer.start();
    for(int i = 0; i < k; i++)
    {
      s1.find(v[i]);
    }
    ms = timer.stop();
    findt.push_back(ms);

    timer.start();
    for(int i = 0; i < k; i++)
    {
      s1.erase(v[i]);
    }
    ms = timer.stop();
    eraset.push_back(ms);
    //μs
  }
  for(int i = 0; i < loop.size(); i++)
  {
    std::cout << "walk: " << walkt[i] << " μs (" << loop[i] << ")" << std::endl;
  }
  for(int i = 0; i < loop.size(); i++)
  {
    std::cout << "insert: " << insertt[i] << " μs (" << loop[i] << ")" << std::endl;
  }
  for(int i = 0; i < loop.size(); i++)
  {
    std::cout << "find: " << findt[i] << " μs (" << loop[i] << ")" << std::endl;
  }
  for(int i = 0; i < loop.size(); i++)
  {
    std::cout << "erase: " << eraset[i] << " μs (" << loop[i] << ")" << std::endl;
  }
  return 0;
}

compare with preallocate 1M bucket rehash(1000000)

No preallocate

walk: 0 μs (100)
walk: 2 μs (1000)
walk: 19 μs (10000)
walk: 196 μs (100000)
walk: 1988 μs (1000000)
insert: 40 μs (100)
insert: 309 μs (1000)
insert: 3057 μs (10000)
insert: 31091 μs (100000)
insert: 344995 μs (1000000)
find: 8 μs (100)
find: 88 μs (1000)
find: 1014 μs (10000)
find: 11328 μs (100000)
find: 130589 μs (1000000)
erase: 17 μs (100)
erase: 174 μs (1000)
erase: 1843 μs (10000)
erase: 20141 μs (100000)
erase: 202869 μs (1000000)

preallocate

walk: 0 μs (100)
walk: 2 μs (1000)
walk: 19 μs (10000)
walk: 196 μs (100000)
walk: 2032 μs (1000000)
insert: 26 μs (100)
insert: 216 μs (1000)
insert: 2147 μs (10000)
insert: 22046 μs (100000)
insert: 230671 μs (1000000)
find: 7 μs (100)
find: 71 μs (1000)
find: 842 μs (10000)
find: 9229 μs (100000)
find: 101268 μs (1000000)
erase: 16 μs (100)
erase: 129 μs (1000)
erase: 1374 μs (10000)
erase: 14663 μs (100000)
erase: 168957 μs (1000000)

上面比較可以發現preallocate bucket insert需要的時間較少，主要的原因是減少了rehash的時間，以下列出insert過程中, bucket count的變化

1:rehashed from 1 to 2
2:rehashed from 2 to 5
5:rehashed from 5 to 11
11:rehashed from 11 to 23
23:rehashed from 23 to 47
47:rehashed from 47 to 97
97:rehashed from 97 to 199
199:rehashed from 199 to 409
409:rehashed from 409 to 823
823:rehashed from 823 to 1741
1741:rehashed from 1741 to 3739
3739:rehashed from 3739 to 7517
7517:rehashed from 7517 to 15173
15173:rehashed from 15173 to 30727
30727:rehashed from 30727 to 62233
62233:rehashed from 62233 to 126271
126271:rehashed from 126271 to 256279
256279:rehashed from 256279 to 520241
520241:rehashed from 520241 to 1056323

可以看出bucket count 每次增加都是倍增 F(m+1)= 2F(m) + 1，這種方式類似vector的運作，insert rehash amortized time complexity會平均到O(n)

順便比較一下 <set>的實作，值得注意的是find那邊的time complexity，跟預期的nlogn有落差，這邊推測主要的原因是因為底層實作如果是用RB tree, 不會完全balance，因此高度不能用最小的nlogn來算，但理論上使用RB tree還是nlogn 只是會有一個constant factor

walk: 0 μs (100)
walk: 1 μs (1000)
walk: 19 μs (10000)
walk: 196 μs (100000)
walk: 1991 μs (1000000)
insert: 36 μs (100)
insert: 427 μs (1000)
insert: 4870 μs (10000)
insert: 60547 μs (100000)
insert: 934594 μs (1000000)
find: 19 μs (100)
find: 269 μs (1000) [ 14.16x ] , expect 15.00x
find: 3582 μs (10000) [ 13.32x ] , expect 13.33x
find: 47652 μs (100000) [ 13.30x ] , expect 12.50x
find: 855063 μs (1000000) [ 17.94x ] , expect 12.00x
erase: 37 μs (100)
erase: 430 μs (1000)
erase: 5532 μs (10000)
erase: 68321 μs (100000)
erase: 1124433 μs (1000000)