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

source code of libcxx/test/benchmarks/algorithms/lexicographical_compare_three_way.bench.cpp