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)