libcxx/benchmarks/lexicographical_compare_three_way.bench.cpp

   1 //===----------------------------------------------------------------------===//
   2 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   3 // See https://llvm.org/LICENSE.txt for license information.
   4 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #include <algorithm>
   9
  10 #include "benchmark/benchmark.h"
  11 #include "test_iterators.h"
  12
  13 static void BM_lexicographical_compare_three_way_slow_path(benchmark::State& state) {
  14   auto size = state.range(0);
  15   std::vector<int> v1;
  16   v1.resize(size);
  17   // v2 is identical except for the last value.
  18   // This means, that `lexicographical_compare_three_way` actually has to
  19   // compare the complete vector and cannot bail out early.
  20   std::vector<int> v2 = v1;
  21   v2.back() += 1;
  22   int* b1 = v1.data();
  23   int* e1 = b1 + v1.size();
  24   int* b2 = v2.data();
  25   int* e2 = b2 + v2.size();
  26
  27   for (auto _ : state) {
  28     auto cmp = std::compare_three_way();
  29     benchmark::DoNotOptimize(std::__lexicographical_compare_three_way_slow_path(b1, e1, b2, e2, cmp));
  30   }
  31 }
  32
  33 BENCHMARK(BM_lexicographical_compare_three_way_slow_path)->RangeMultiplier(4)->Range(1, 1 << 20);
  34
  35 static void BM_lexicographical_compare_three_way_fast_path(benchmark::State& state) {
  36   auto size = state.range(0);
  37   std::vector<int> v1;
  38   v1.resize(size);
  39   // v2 is identical except for the last value.
  40   // This means, that `lexicographical_compare_three_way` actually has to
  41   // compare the complete vector and cannot bail out early.
  42   std::vector<int> v2 = v1;
  43   v2.back() += 1;
  44   int* b1 = v1.data();
  45   int* e1 = b1 + v1.size();
  46   int* b2 = v2.data();
  47   int* e2 = b2 + v2.size();
  48
  49   for (auto _ : state) {
  50     auto cmp = std::compare_three_way();
  51     benchmark::DoNotOptimize(std::__lexicographical_compare_three_way_fast_path(b1, e1, b2, e2, cmp));
  52   }
  53 }
  54
  55 BENCHMARK(BM_lexicographical_compare_three_way_fast_path)->RangeMultiplier(4)->Range(1, 1 << 20);
  56
  57 template <class IteratorT>
  58 static void BM_lexicographical_compare_three_way(benchmark::State& state) {
  59   auto size = state.range(0);
  60   std::vector<int> v1;
  61   v1.resize(size);
  62   // v2 is identical except for the last value.
  63   // This means, that `lexicographical_compare_three_way` actually has to
  64   // compare the complete vector and cannot bail out early.
  65   std::vector<int> v2 = v1;
  66   v2.back() += 1;
  67   auto b1 = IteratorT{v1.data()};
  68   auto e1 = IteratorT{v1.data() + v1.size()};
  69   auto b2 = IteratorT{v2.data()};
  70   auto e2 = IteratorT{v2.data() + v2.size()};
  71
  72   for (auto _ : state) {
  73     benchmark::DoNotOptimize(std::lexicographical_compare_three_way(b1, e1, b2, e2));
  74   }
  75 }
  76
  77 // Type alias to make sure the `*` does not appear in the benchmark name.
  78 // A `*` would confuse the Python test runner running this google benchmark.
  79 using IntPtr = int*;
  80
  81 // `lexicographical_compare_three_way` has a fast path for random access iterators.
  82 BENCHMARK_TEMPLATE(BM_lexicographical_compare_three_way, IntPtr)->RangeMultiplier(4)->Range(1, 1 << 20);
  83 BENCHMARK_TEMPLATE(BM_lexicographical_compare_three_way, random_access_iterator<IntPtr>)
  84     ->RangeMultiplier(4)
  85     ->Range(1, 1 << 20);
  86 BENCHMARK_TEMPLATE(BM_lexicographical_compare_three_way, cpp17_input_iterator<IntPtr>)
  87     ->RangeMultiplier(4)
  88     ->Range(1, 1 << 20);
  89
  90 int main(int argc, char** argv) {
  91   benchmark::Initialize(&argc, argv);
  92   if (benchmark::ReportUnrecognizedArguments(argc, argv))
  93     return 1;
  94
  95   benchmark::RunSpecifiedBenchmarks();
  96 }