benchmark.cpp

#include <set>
#include <unordered_set>
#include <vector>
#include <algorithm>

// number of rows already in table
int N = 100;
// number of values to insert
int M = 1;

// werte: 
// rows: 1...N
// values to insert: 1...M

//  M=1: vector 1.7x schneller als set, unordered set 7.6x langsamer
//  M=5: vector 1.6x schneller als set
// M=10: vector 2.1x schneller als set, unordered set 3.6x langsamer
// M=50: vector = unordered set, set 1.3x langsamer
// M=100: set etwas schneller als vector, unordered_set etwa 1.6x schneller
// M=1000: set 5.1x schneller, unordered_set 6.7x schneller als vector jeweils

static void SearchVector(benchmark::State& state) {
  std::vector<int> rows;
  for (int i = 0; i < N; i++) {
    rows.emplace_back(i);
  }
  std::vector<int> values;
  for (int i = 0; i < M; i++) {
    values.emplace_back(i);
  }

  for (auto _ : state) {
    for (int i = 0; i < N; i++) {
      int row = rows[i];
      bool found = std::find(values.begin(), values.end(), row) != values.end();
      benchmark::DoNotOptimize(found);
    }
  }
}
BENCHMARK(SearchVector);

static void SearchVectorBin(benchmark::State& state) {
  std::vector<int> rows;
  for (int i = 0; i < N; i++) {
    rows.emplace_back(i);
  }
  std::vector<int> values;
  for (int i = 0; i < M; i++) {
    values.emplace_back(i);
  }

  for (auto _ : state) {
    for (int i = 0; i < N; i++) {
      int row = rows[i];
      bool found = std::binary_search(values.begin(), values.end(), row);
      benchmark::DoNotOptimize(found);
    }
  }
}
BENCHMARK(SearchVectorBin);

static void SearchVectorBinOr1(benchmark::State& state) {
  std::vector<int> rows;
  for (int i = 0; i < N; i++) {
    rows.emplace_back(i);
  }
  std::vector<int> values;
  for (int i = 0; i < M; i++) {
    values.emplace_back(i);
  }

  bool only_one = values.size() == 1;
  int only_one_value = only_one ? values[0] : 0;
  for (auto _ : state) {
    for (int i = 0; i < N; i++) {
      int row = rows[i];
      bool found = only_one ? only_one_value == row : std::binary_search(values.begin(), values.end(), row);
      benchmark::DoNotOptimize(found);
    }
  }
}
BENCHMARK(SearchVectorBinOr1);

static void SearchSet(benchmark::State& state) {
  std::vector<int> rows;
  for (int i = 0; i < N; i++) {
    rows.emplace_back(i);
  }
  std::set<int> values;
  for (int i = 0; i < M; i++) {
    values.insert(i);
  }

  for (auto _ : state) {
    for (int i = 0; i < N; i++) {
      int row = rows[i];
      bool found = values.count(row);
      benchmark::DoNotOptimize(found);
    }
  }
}
BENCHMARK(SearchSet);

static void SearchUnorderedSet(benchmark::State& state) {
  std::vector<int> rows;
  for (int i = 0; i < N; i++) {
    rows.emplace_back(i);
  }
  std::unordered_set<int> values;
  for (int i = 0; i < M; i++) {
    values.insert(i);
  }

  for (auto _ : state) {
    for (int i = 0; i < N; i++) {
      int row = rows[i];
      bool found = values.count(row);
      benchmark::DoNotOptimize(found);
    }
  }
}
BENCHMARK(SearchUnorderedSet);