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
BM_lexicographical_compare_three_way_slow_path(benchmark::State & state)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
BM_lexicographical_compare_three_way_fast_path(benchmark::State & state)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>
BM_lexicographical_compare_three_way(benchmark::State & state)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
main(int argc,char ** argv)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