Performance Discrepancy between std::lower_bound and std::ranges::lower_bound

67 views Asked by At

Why does std::lower_bound outperform lower_bound on ranges in C++ benchmarks ?

My code is as follow :

#include <set>
#include <ranges>
#include <algorithm>

std::set<int> my_set;

static void RangeLowerBound(benchmark::State& state) {
  for (auto i = 0; i <= 1'000'000; ++i) {
    my_set.insert(i);  
  }
  // Code inside this loop is measured repeatedly
  auto search{900'000};
  for (auto _ : state) {
    auto it = std::ranges::lower_bound(my_set, search);
    // Make sure the variable is not optimized away by compiler
    benchmark::DoNotOptimize(it);
  }
}
// Register the function as a benchmark
BENCHMARK(RangeLowerBound);

static void StdLowerBound(benchmark::State& state) {
  for (auto i = 0; i <= 1'000'000; ++i) {
    my_set.insert(i);  
  }
  // Code inside this loop is measured repeatedly
  auto search{900'000};
  for (auto _ : state) {
    auto it = std::lower_bound(my_set.begin(), my_set.end(), search);
    // Make sure the variable is not optimized away by compiler
    benchmark::DoNotOptimize(it);
  }
}
// Register the function as a benchmark
BENCHMARK(StdLowerBound);

static void SetLowerBound(benchmark::State& state) {
  for (auto i = 0; i <= 1'000'000; ++i) {
    my_set.insert(i);  
  }
  // Code before the loop is not measured
  auto search{900'000};
  for (auto _ : state) {
    auto it = my_set.lower_bound(search);
    // Make sure the variable is not optimized away by compiler
    benchmark::DoNotOptimize(it);
  }
}
BENCHMARK(SetLowerBound);

https://quick-bench.com/q/iFTe4YdHpXq4f72itFZGU3AGW1w

in which case, std::ranges algo may outperform algos defined on data structures directly (e.g. std::set::lower_bound vs std::ranges::lower_bound)

0

There are 0 answers