90 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// UNSUPPORTED: c++03, c++11, c++14, c++1710 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(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 to22 // 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(4)->Range(1, 1 << 20);37 38static void BM_lexicographical_compare_three_way_fast_path(benchmark::State& state) {39 auto size = state.range(0);40 std::vector<int> v1;41 v1.resize(size);42 // v2 is identical except for the last value.43 // This means, that `lexicographical_compare_three_way` actually has to44 // 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(b1, e1, b2, e2, cmp));55 }56}57 58BENCHMARK(BM_lexicographical_compare_three_way_fast_path)->RangeMultiplier(4)->Range(1, 1 << 20);59 60template <class IteratorT>61static void BM_lexicographical_compare_three_way(benchmark::State& state) {62 auto size = state.range(0);63 std::vector<int> v1;64 v1.resize(size);65 // v2 is identical except for the last value.66 // This means, that `lexicographical_compare_three_way` actually has to67 // 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(4)->Range(1, 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