Benchmark code for the indexed iterator (see comments for results)

bench.cpp

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

#include "buf_idx_iter.hpp"

template <typename T>
void BM_std_sort(benchmark::State& state)
{
    // Set up the test data
    std::size_t size = state.range(0);
    std::vector<T> data(size);
    std::iota(data.begin(), data.end(), 0);
    std::random_shuffle(data.begin(), data.end());

    // Measure the performance of std::sort
    for (auto _ : state)
    {
        std::sort(data.begin(), data.end());
    }
}


template <typename T>
void BM_buf_idx_iter_sort(benchmark::State& state)
{
    // Set up the test data
    std::size_t size = state.range(0);
    std::vector<T> data(size);
    std::iota(data.begin(), data.end(), 0);
    std::random_shuffle(data.begin(), data.end());

    // Measure the performance of std::sort on std::vector
    for (auto _ : state)
    {
        std::sort(ibegin(data), iend(data));
    }
}



template <typename T>
void BM_std_accumulate(benchmark::State& state)
{
    // Set up the test data
    std::size_t size = state.range(0);
    std::vector<T> data(size);
    std::iota(data.begin(), data.end(), 0);

    // Measure the performance of std::accumulate
    for (auto _ : state)
    {
        benchmark::DoNotOptimize(std::accumulate(data.begin(), data.end(), T{}));
    }
}

template <typename T>
void BM_buf_idx_iter_accumulate(benchmark::State& state)
{
    // Set up the test data
    std::size_t size = state.range(0);
    std::vector<T> data(size);
    std::iota(data.begin(), data.end(), 0);

    // Measure the performance of std::accumulate on std::vector
    for (auto _ : state)
    {
        benchmark::DoNotOptimize(std::accumulate(ibegin(data), iend(data), T{}));
    }
}


template <typename T>
void BM_std_copy_backward(benchmark::State& state)
{
    // Set up the test data
    std::size_t size = state.range(0);
    std::vector<T> data(size);
    std::iota(data.begin(), data.end(), 0);
    std::vector<T> dest(size);

    // Measure the performance of std::copy_backward
    for (auto _ : state)
    {
        std::copy_backward(data.begin(), data.end(), dest.end());
    }
}

template <typename T>
void BM_buf_idx_iter_copy_backward(benchmark::State& state)
{
    // Set up the test data
    std::size_t size = state.range(0);
    std::vector<T> data(size);
    std::iota(data.begin(), data.end(), 0);
    std::vector<T> dest(size);

    // Measure the performance of std::copy_backward on std::vector
    for (auto _ : state)
    {
        std::copy_backward(ibegin(data), iend(data), dest.end());
    }
}

template <typename T>
void BM_std_copy(benchmark::State& state)
{
  // Set up the test data
  std::size_t size = state.range(0);
  std::vector<T> data(size);
  std::iota(data.begin(), data.end(), 0);
  std::vector<T> dest(size);

  // Measure the performance of std::copy
  for (auto _ : state)
  {
    std::copy(data.begin(), data.end(), dest.begin());
  }
}

template <typename T>
void BM_buf_idx_iter_copy(benchmark::State& state)
{
  // Set up the test data
  std::size_t size = state.range(0);
  std::vector<T> data(size);
  std::iota(data.begin(), data.end(), 0);
  std::vector<T> dest(size);

  // Measure the performance of std::copy on std::vector
  for (auto _ : state)
  {
    std::copy(ibegin(data), iend(data), dest.begin());
  }
}


BENCHMARK_TEMPLATE(BM_std_sort, size_t)->Range(1 << 10, 1 << 24);
BENCHMARK_TEMPLATE(BM_buf_idx_iter_sort, size_t)->Range(1 << 10, 1 << 24);

BENCHMARK_TEMPLATE(BM_std_accumulate, size_t)->Range(1 << 10, 1 << 24);
BENCHMARK_TEMPLATE(BM_buf_idx_iter_accumulate, size_t)->Range(1 << 10, 1 << 24);

BENCHMARK_TEMPLATE(BM_std_copy_backward, size_t)->Range(1 << 10, 1 << 24);
BENCHMARK_TEMPLATE(BM_buf_idx_iter_copy_backward, size_t)->Range(1 << 10, 1 << 24);

BENCHMARK_TEMPLATE(BM_std_copy, size_t)->Range(1 << 10, 1 << 24);
BENCHMARK_TEMPLATE(BM_buf_idx_iter_copy, size_t)->Range(1 << 10, 1 << 24);

// remove_if doesnt work
//BENCHMARK_TEMPLATE(BM_std_remove_if, size_t)->Range(1 << 10, 1 << 24);
//BENCHMARK_TEMPLATE(BM_buf_idx_iter_remove_if, size_t)->Range(1 << 10, 1 << 24);

BENCHMARK_MAIN();

rep ~/projects/gpt/idx_iter * main $ g++ bench.cpp -O3 -std=c++20 -isystem benchmark/include -Lbenchmark/build/src -lbenchmark -lpthread -o mybenchmark
rep ~/projects/gpt/idx_iter * main $ ./mybenchmark 
2022-12-04T19:15:03+05:30
Running ./mybenchmark
Run on (16 X 4600 MHz CPU s)
CPU Caches:
  L1 Data 48 KiB (x8)
  L1 Instruction 32 KiB (x8)
  L2 Unified 1280 KiB (x8)
  L3 Unified 24576 KiB (x1)
Load Average: 0.56, 0.60, 0.70
***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead.
-----------------------------------------------------------------------------------------
Benchmark                                               Time             CPU   Iterations
-----------------------------------------------------------------------------------------
BM_std_sort<size_t>/1024                             3843 ns         3842 ns       181742
BM_std_sort<size_t>/4096                            18703 ns        18695 ns        37129
BM_std_sort<size_t>/32768                          183663 ns       183604 ns         3782
BM_std_sort<size_t>/262144                        1777065 ns      1776270 ns          363
BM_std_sort<size_t>/2097152                      20624978 ns     20610836 ns           31
BM_std_sort<size_t>/16777216                   1020846903 ns   1020330443 ns            1
BM_buf_idx_iter_sort<size_t>/1024                    3899 ns         3897 ns       179611
BM_buf_idx_iter_sort<size_t>/4096                   19545 ns        19538 ns        36044
BM_buf_idx_iter_sort<size_t>/32768                 200984 ns       200915 ns         3478
BM_buf_idx_iter_sort<size_t>/262144               1986178 ns      1985379 ns          339
BM_buf_idx_iter_sort<size_t>/2097152             23342220 ns     23328018 ns           28
BM_buf_idx_iter_sort<size_t>/16777216          1077417286 ns   1076868108 ns            1
BM_std_accumulate<size_t>/1024                        170 ns          170 ns      4112861
BM_std_accumulate<size_t>/4096                        652 ns          652 ns      1066997
BM_std_accumulate<size_t>/32768                      5354 ns         5352 ns       130791
BM_std_accumulate<size_t>/262144                    43718 ns        43699 ns        16098
BM_std_accumulate<size_t>/2097152                  468835 ns       468430 ns         1494
BM_std_accumulate<size_t>/16777216                6469210 ns      6462215 ns          107
BM_buf_idx_iter_accumulate<size_t>/1024               172 ns          171 ns      4086506
BM_buf_idx_iter_accumulate<size_t>/4096               662 ns          662 ns      1037466
BM_buf_idx_iter_accumulate<size_t>/32768             5386 ns         5384 ns       127197
BM_buf_idx_iter_accumulate<size_t>/262144           43335 ns        43316 ns        16207
BM_buf_idx_iter_accumulate<size_t>/2097152         466761 ns       466300 ns         1504
BM_buf_idx_iter_accumulate<size_t>/16777216       6577604 ns      6570879 ns          106
BM_std_copy_backward<size_t>/1024                    70.3 ns         70.3 ns      9949273
BM_std_copy_backward<size_t>/4096                     554 ns          553 ns      1260890
BM_std_copy_backward<size_t>/32768                   4418 ns         4416 ns       158280
BM_std_copy_backward<size_t>/262144                 65133 ns        65103 ns        10697
BM_std_copy_backward<size_t>/2097152               602117 ns       601247 ns         1092
BM_std_copy_backward<size_t>/16777216             8487423 ns      8478130 ns           81
BM_buf_idx_iter_copy_backward<size_t>/1024           70.3 ns         70.3 ns      9957051
BM_buf_idx_iter_copy_backward<size_t>/4096            554 ns          554 ns      1263269
BM_buf_idx_iter_copy_backward<size_t>/32768          4429 ns         4427 ns       158574
BM_buf_idx_iter_copy_backward<size_t>/262144        65220 ns        65192 ns        10103
BM_buf_idx_iter_copy_backward<size_t>/2097152      599852 ns       599049 ns         1164
BM_buf_idx_iter_copy_backward<size_t>/16777216    8910469 ns      8845321 ns           80
BM_std_copy<size_t>/1024                             70.1 ns         70.1 ns      9989575
BM_std_copy<size_t>/4096                              555 ns          555 ns      1267788
BM_std_copy<size_t>/32768                            4416 ns         4414 ns       157877
BM_std_copy<size_t>/262144                          65528 ns        65497 ns        10563
BM_std_copy<size_t>/2097152                        614978 ns       614170 ns         1133
BM_std_copy<size_t>/16777216                      8625481 ns      8615847 ns           82
BM_buf_idx_iter_copy<size_t>/1024                    70.2 ns         70.2 ns      9938515
BM_buf_idx_iter_copy<size_t>/4096                     551 ns          551 ns      1266220
BM_buf_idx_iter_copy<size_t>/32768                   4423 ns         4422 ns       158327
BM_buf_idx_iter_copy<size_t>/262144                 64436 ns        64410 ns        10661
BM_buf_idx_iter_copy<size_t>/2097152               602840 ns       602063 ns         1092
BM_buf_idx_iter_copy<size_t>/16777216             8582354 ns      8572356 ns           78
rep ~/projects/gpt/idx_iter * main $