benchmark_find_insert_int_pairs.cpp

#include <algorithm>
#include <chrono>
#include <iostream>
#include <map>
#include <random>
#include <set>
#include <vector>

// GOAL : benchmark containers for these 2 operations
// - Insert a pair of ints into the container
// - Find if a pair of ints is present within the container

// What's been tried so far
// std::set<std::pair<int, int>> 
// std::map<int, int>
// std::vector<std::set<int>>

// The best candidate seems to be std::vector<std::set<int>>, see below.

class Set
{
public:
  Set(size_t N) {}
  inline void insert(int a, int b)
  {
       set_.emplace(a, b);
  }
  bool find(int a, int b) const
  {
      return set_.find(std::pair(a, b)) != set_.end();
  }
  static const char* name() {
      return "set";
  }
private:
  std::set<std::pair<int, int>> set_;
};

class Map
{
public:
  Map(size_t N) {}
  inline void insert(int a, int b)
  {
       map_.emplace(a, b);
  }
  bool find(int a, int b) const
  {
      if (map_.count(a) > 0)
         return map_.at(a) == b;
      else
         return false;
  }
  static const char* name() {
      return "map";
  }
private:
  std::map<int, int> map_;
};

class VectorSet
{
public:
  VectorSet(size_t N) : v_(N) {}
  inline void insert(int a, int b)
  {
      v_[a].insert(b);
  }
  bool find(int a, int b) const
  {
      return v_[a].count(b) > 0;
  }
  static const char* name() {
      return "vector_set";
  }
private:
  std::vector<std::set<int>> v_;
};

template<class Container>
void time_it(size_t N)
{
    using sclock = std::chrono::steady_clock;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> distrib(0, N-1);

    Container p(N);
    auto t0 = sclock::now();
    for (std::size_t ii = 0; ii < N; ii++)
        p.insert(distrib(gen), distrib(gen));
    auto t1 = sclock::now();
    std::vector<bool> found(N);
    for (std::size_t ii = 0; ii < N; ii++)
        found[ii] = p.find(distrib(gen), distrib(gen));
    auto t2 = sclock::now();
    std::map<std::string, int> durations;
    durations["Insertion"] = std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0).count();
    durations["Find"] = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
    std::cout << Container::name() << "[" << N << "]" << std::endl;
    for (auto& [k, v] : durations)
        std::cout << '\t'<< k << ": " << v << " ms" << std::endl;
}

int main() {
  constexpr size_t ii_min = 100;
  constexpr size_t ii_max = 10000000;
  for (size_t ii = ii_min; ii < ii_max; ii *= 10)
      time_it<Set>(ii);
  for (size_t ii = ii_min; ii < ii_max; ii *= 10)
      time_it<Map>(ii);
  for (size_t ii = ii_min; ii < ii_max; ii *= 10)
      time_it<VectorSet>(ii);
}

// g++ -std=c++17 -O3 bench.cpp
// set[100]
// 	Find: 0 ms
// 	Insertion: 0 ms
// set[1000]
// 	Find: 0 ms
// 	Insertion: 0 ms
// set[10000]
// 	Find: 6 ms
// 	Insertion: 9 ms
// set[100000]
// 	Find: 22 ms
// 	Insertion: 38 ms
// set[1000000]
// 	Find: 628 ms
// 	Insertion: 548 ms
// map[100]
// 	Find: 0 ms
// 	Insertion: 0 ms
// map[1000]
// 	Find: 0 ms
// 	Insertion: 0 ms
// map[10000]
// 	Find: 119 ms
// 	Insertion: 1 ms
// map[100000]
// 	Find: 29 ms
// 	Insertion: 26 ms
// map[1000000]
// 	Find: 604 ms
// 	Insertion: 479 ms
// vector_set[100]
// 	Find: 0 ms
// 	Insertion: 0 ms
// vector_set[1000]
// 	Find: 0 ms
// 	Insertion: 0 ms
// vector_set[10000]
// 	Find: 0 ms
// 	Insertion: 0 ms
// vector_set[100000]
// 	Find: 9 ms
// 	Insertion: 12 ms
// vector_set[1000000]
// 	Find: 189 ms
// 	Insertion: 194 ms