branchless_binary_seach_benchmark.cpp

#include <iostream>
#include <vector>
#include <chrono>

namespace branchless {

template<typename It>
It lower_bound(It begin, It end, const typename It::value_type& value)
{
  auto len = std::distance(begin, end);
  auto pos = begin;

  while (len > 1) {
    auto half = len / 2;
    pos += (*(pos + (half - 1)) < value) * half;
    len -= half;
  }
  return pos;
}

};

namespace utils {

template<typename Func>
auto benchmark(Func&& func, size_t iterations = 1000)
{
  auto start = std::chrono::high_resolution_clock::now();
  auto result = func();
  for (size_t i = 0; i < iterations; ++i) {
    result = func();
  }
  auto end = std::chrono::high_resolution_clock::now();
  return std::make_pair(end - start, result);
}

auto generateVector(size_t size) {
  std::vector<int> data;
  data.reserve(size);
  for (size_t i = 0; i < size; ++i) {
    data.push_back(i);
  }
  return data;
}

};


int main() {
  int result = 0;
  for (auto i = 1; i < (1 << 28); i *= 2) {
    const auto data = utils::generateVector(i);
    std::cout << "=============================" << std::endl;
    std::cout << "array size = " << i << std::endl;
    auto [branchless, branchlessResult] = utils::benchmark([&]() {
      const auto numberToFind = std::rand() % i;
      return branchless::lower_bound(data.begin(), data.end(), numberToFind);
    });
    std::cout << "branchlessTime = " << branchless.count() << std::endl;
    auto [std, stdResult] = utils::benchmark([&]() {
      const auto numberToFind = std::rand() % i;
      return std::lower_bound(data.begin(), data.end(), numberToFind);
    });
    std::cout << "stdTime        = " << std.count() << std::endl;

    result ^= std::distance(data.begin(), branchlessResult) ^ std::distance(data.begin(), stdResult);
  }

  std::cout << "result = " << result << std::endl;

  return EXIT_SUCCESS;
}