sort_bench.cpp

#include <benchmark/benchmark.h>
#include <vector>
#include <algorithm>

size_t linear_search(int* buffer, size_t count, int to_find)
{
#if 1
   const size_t batch = 0;
   size_t count_4 = 0;
#else
    // try to unroll the loop. 
    const size_t batch = 4;
    size_t count_4 = count / batch;
    for (size_t i = 0; i < count; i+=batch)
    {
        for (size_t j = 0; j < batch; ++j)
        {
            size_t idx = i + j;
            int sample = buffer[idx];
            if (sample == to_find) return idx;
            if (sample > to_find) return count + 1;
        }
    }
#endif
    // loop remaining elements
    for (size_t i = count_4*batch; i < count; i++)
    {
            size_t idx = i;
            int sample = buffer[idx];
            if (sample == to_find) return idx;
            if (sample > to_find) return count + 1;
    }
    return count + 1;
}

size_t binary_search(int* buffer, size_t count, int to_find)
{
    size_t low = 0;
    size_t high = count;
    size_t pivot = count / 2;
    while (high > low)
    {
        int sample = buffer[pivot];
        if (sample == to_find) return pivot;
        if (sample > to_find)
        {
            low = pivot + 1;
        }
        else
        {
            high = pivot;
        }
        pivot = (high + low) / 2;
    }
    return count + 1;
}

static const size_t max_elements = 32*1024;

class VectorFixture : public benchmark::Fixture
{
public:
    VectorFixture()
    {
    }
    void SetUp(const ::benchmark::State& state)
    {
        Fixture::SetUp(state);
        g_data = std::vector<int>(max_elements);
        std::generate_n(g_data.begin(), max_elements, []() { return rand(); });
        std::sort(g_data.begin(), g_data.end());
    }

    void TearDown(const ::benchmark::State& state)
    {
        Fixture::TearDown(state);
    }
    std::vector<int> g_data;
};

BENCHMARK_DEFINE_F(VectorFixture, search_linear)(benchmark::State& state)
{
    int higher = g_data[state.range(0)-1];
    for (auto _ : state)
    {
        int to_find = rand() % higher;
        auto found = linear_search(g_data.data(), state.range(0), to_find);
        benchmark::DoNotOptimize(found);
    }
}

BENCHMARK_DEFINE_F(VectorFixture, search_binary)(benchmark::State& state)
{
    int higher = g_data[state.range(0)-1];
    for (auto _ : state)
    {
        int to_find = rand() % higher;
        auto found = binary_search(g_data.data(), state.range(0), to_find);
        benchmark::DoNotOptimize(found);
    }
}
BENCHMARK_REGISTER_F(VectorFixture, search_linear)->RangeMultiplier(2)->Range(8, max_elements);
BENCHMARK_REGISTER_F(VectorFixture, search_binary)->RangeMultiplier(2)->Range(8, max_elements);

BENCHMARK_MAIN();