llvm-project

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
}
97