llvm-project
96 строк · 3.4 Кб
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
13static void BM_lexicographical_compare_three_way_slow_path(benchmark::State& state) {
14auto size = state.range(0);
15std::vector<int> v1;
16v1.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.
20std::vector<int> v2 = v1;
21v2.back() += 1;
22int* b1 = v1.data();
23int* e1 = b1 + v1.size();
24int* b2 = v2.data();
25int* e2 = b2 + v2.size();
26
27for (auto _ : state) {
28auto cmp = std::compare_three_way();
29benchmark::DoNotOptimize(std::__lexicographical_compare_three_way_slow_path(b1, e1, b2, e2, cmp));
30}
31}
32
33BENCHMARK(BM_lexicographical_compare_three_way_slow_path)->RangeMultiplier(4)->Range(1, 1 << 20);
34
35static void BM_lexicographical_compare_three_way_fast_path(benchmark::State& state) {
36auto size = state.range(0);
37std::vector<int> v1;
38v1.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.
42std::vector<int> v2 = v1;
43v2.back() += 1;
44int* b1 = v1.data();
45int* e1 = b1 + v1.size();
46int* b2 = v2.data();
47int* e2 = b2 + v2.size();
48
49for (auto _ : state) {
50auto cmp = std::compare_three_way();
51benchmark::DoNotOptimize(std::__lexicographical_compare_three_way_fast_path(b1, e1, b2, e2, cmp));
52}
53}
54
55BENCHMARK(BM_lexicographical_compare_three_way_fast_path)->RangeMultiplier(4)->Range(1, 1 << 20);
56
57template <class IteratorT>
58static void BM_lexicographical_compare_three_way(benchmark::State& state) {
59auto size = state.range(0);
60std::vector<int> v1;
61v1.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.
65std::vector<int> v2 = v1;
66v2.back() += 1;
67auto b1 = IteratorT{v1.data()};
68auto e1 = IteratorT{v1.data() + v1.size()};
69auto b2 = IteratorT{v2.data()};
70auto e2 = IteratorT{v2.data() + v2.size()};
71
72for (auto _ : state) {
73benchmark::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.
79using IntPtr = int*;
80
81// `lexicographical_compare_three_way` has a fast path for random access iterators.
82BENCHMARK_TEMPLATE(BM_lexicographical_compare_three_way, IntPtr)->RangeMultiplier(4)->Range(1, 1 << 20);
83BENCHMARK_TEMPLATE(BM_lexicographical_compare_three_way, random_access_iterator<IntPtr>)
84->RangeMultiplier(4)
85->Range(1, 1 << 20);
86BENCHMARK_TEMPLATE(BM_lexicographical_compare_three_way, cpp17_input_iterator<IntPtr>)
87->RangeMultiplier(4)
88->Range(1, 1 << 20);
89
90int main(int argc, char** argv) {
91benchmark::Initialize(&argc, argv);
92if (benchmark::ReportUnrecognizedArguments(argc, argv))
93return 1;
94
95benchmark::RunSpecifiedBenchmarks();
96}
97