144 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#include <cstddef>13#include <deque>14#include <list>15#include <string>16#include <vector>17 18#include <benchmark/benchmark.h>19#include "../../GenerateInput.h"20 21int main(int argc, char** argv) {22 auto std_equal_3leg = [](auto first1, auto last1, auto first2, auto) { return std::equal(first1, last1, first2); };23 auto std_equal_4leg = [](auto first1, auto last1, auto first2, auto last2) {24 return std::equal(first1, last1, first2, last2);25 };26 auto std_equal_3leg_pred = [](auto first1, auto last1, auto first2, auto) {27 return std::equal(first1, last1, first2, [](auto x, auto y) {28 benchmark::DoNotOptimize(x);29 benchmark::DoNotOptimize(y);30 return x == y;31 });32 };33 auto std_equal_4leg_pred = [](auto first1, auto last1, auto first2, auto last2) {34 return std::equal(first1, last1, first2, last2, [](auto x, auto y) {35 benchmark::DoNotOptimize(x);36 benchmark::DoNotOptimize(y);37 return x == y;38 });39 };40 auto ranges_equal_4leg_pred = [](auto first1, auto last1, auto first2, auto last2) {41 return std::ranges::equal(first1, last1, first2, last2, [](auto x, auto y) {42 benchmark::DoNotOptimize(x);43 benchmark::DoNotOptimize(y);44 return x == y;45 });46 };47 48 // Benchmark {std,ranges}::equal where we determine inequality at the very end (worst case).49 {50 auto bm = []<class Container>(std::string name, auto equal) {51 benchmark::RegisterBenchmark(52 name,53 [equal](auto& st) {54 std::size_t const size = st.range(0);55 using ValueType = typename Container::value_type;56 ValueType x = Generate<ValueType>::random();57 ValueType y = random_different_from({x});58 Container c1(size, x);59 Container c2(size, x);60 c2.back() = y;61 62 for ([[maybe_unused]] auto _ : st) {63 benchmark::DoNotOptimize(c1);64 benchmark::DoNotOptimize(c2);65 auto result = equal(c1.begin(), c1.end(), c2.begin(), c2.end());66 benchmark::DoNotOptimize(result);67 }68 })69 ->Arg(8)70 ->Arg(50) // non power-of-two71 ->Arg(1024)72 ->Arg(8192)73 ->Arg(1 << 20);74 };75 76 // std::equal(it, it, it)77 bm.operator()<std::vector<int>>("std::equal(vector<int>) (it, it, it)", std_equal_3leg);78 bm.operator()<std::deque<int>>("std::equal(deque<int>) (it, it, it)", std_equal_3leg);79 bm.operator()<std::list<int>>("std::equal(list<int>) (it, it, it)", std_equal_3leg);80 81 // std::equal(it, it, it, pred)82 bm.operator()<std::vector<int>>("std::equal(vector<int>) (it, it, it, pred)", std_equal_3leg_pred);83 bm.operator()<std::deque<int>>("std::equal(deque<int>) (it, it, it, pred)", std_equal_3leg_pred);84 bm.operator()<std::list<int>>("std::equal(list<int>) (it, it, it, pred)", std_equal_3leg_pred);85 86 // {std,ranges}::equal(it, it, it, it)87 bm.operator()<std::vector<int>>("std::equal(vector<int>) (it, it, it, it)", std_equal_4leg);88 bm.operator()<std::deque<int>>("std::equal(deque<int>) (it, it, it, it)", std_equal_4leg);89 bm.operator()<std::list<int>>("std::equal(list<int>) (it, it, it, it)", std_equal_4leg);90 bm.operator()<std::vector<int>>("rng::equal(vector<int>) (it, it, it, it)", std::ranges::equal);91 bm.operator()<std::deque<int>>("rng::equal(deque<int>) (it, it, it, it)", std::ranges::equal);92 bm.operator()<std::list<int>>("rng::equal(list<int>) (it, it, it, it)", std::ranges::equal);93 94 // {std,ranges}::equal(it, it, it, it, pred)95 bm.operator()<std::vector<int>>("std::equal(vector<int>) (it, it, it, it, pred)", std_equal_4leg_pred);96 bm.operator()<std::deque<int>>("std::equal(deque<int>) (it, it, it, it, pred)", std_equal_4leg_pred);97 bm.operator()<std::list<int>>("std::equal(list<int>) (it, it, it, it, pred)", std_equal_4leg_pred);98 bm.operator()<std::vector<int>>("rng::equal(vector<int>) (it, it, it, it, pred)", ranges_equal_4leg_pred);99 bm.operator()<std::deque<int>>("rng::equal(deque<int>) (it, it, it, it, pred)", ranges_equal_4leg_pred);100 bm.operator()<std::list<int>>("rng::equal(list<int>) (it, it, it, it, pred)", ranges_equal_4leg_pred);101 }102 103 // Benchmark {std,ranges}::equal on vector<bool>.104 {105 auto bm = [](std::string name, auto equal, bool aligned) {106 benchmark::RegisterBenchmark(107 name,108 [=](auto& st) {109 std::size_t const size = st.range();110 std::vector<bool> c1(size, true);111 std::vector<bool> c2(size + 8, true);112 auto first1 = c1.begin();113 auto last1 = c1.end();114 auto first2 = aligned ? c2.begin() : c2.begin() + 4;115 auto last2 = aligned ? c2.end() : c2.end() - 4;116 for ([[maybe_unused]] auto _ : st) {117 benchmark::DoNotOptimize(c1);118 benchmark::DoNotOptimize(c2);119 auto result = equal(first1, last1, first2, last2);120 benchmark::DoNotOptimize(result);121 }122 })123 ->Arg(8)124 ->Arg(50) // non power-of-two125 ->Arg(1024)126 ->Arg(8192)127 ->Arg(1 << 20);128 };129 130 // {std,ranges}::equal(vector<bool>) (aligned)131 bm("std::equal(vector<bool>) (aligned)", std_equal_4leg, true);132 bm("rng::equal(vector<bool>) (aligned)", std::ranges::equal, true);133 134 // {std,ranges}::equal(vector<bool>) (unaligned)135 bm("std::equal(vector<bool>) (unaligned)", std_equal_4leg, false);136 bm("rng::equal(vector<bool>) (unaligned)", std::ranges::equal, false);137 }138 139 benchmark::Initialize(&argc, argv);140 benchmark::RunSpecifiedBenchmarks();141 benchmark::Shutdown();142 return 0;143}144