159 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 <iterator>15#include <list>16#include <string>17#include <vector>18 19#include "benchmark/benchmark.h"20#include "../../GenerateInput.h"21#include "test_macros.h"22 23int main(int argc, char** argv) {24 auto std_rotate = [](auto first, auto middle, auto last) { return std::rotate(first, middle, last); };25 26 // Benchmark {std,ranges}::rotate where we rotate various fractions of the range. It is possible to27 // special-case some of these fractions to cleverly perform swap_ranges.28 {29 auto bm = []<class Container>(std::string name, auto rotate, double fraction) {30 benchmark::RegisterBenchmark(31 name,32 [=](auto& st) {33 std::size_t const size = st.range(0);34 using ValueType = typename Container::value_type;35 Container c;36 std::generate_n(std::back_inserter(c), size, [] { return Generate<ValueType>::random(); });37 38 auto nth = std::next(c.begin(), static_cast<std::size_t>(size * fraction));39 for ([[maybe_unused]] auto _ : st) {40 benchmark::DoNotOptimize(c);41 auto result = rotate(c.begin(), nth, c.end());42 benchmark::DoNotOptimize(result);43 }44 })45 ->Arg(32)46 ->Arg(50) // non power-of-two47 ->Arg(1024)48 ->Arg(8192);49 };50 bm.operator()<std::vector<int>>("std::rotate(vector<int>) (by 1/4)", std_rotate, 0.25);51 bm.operator()<std::deque<int>>("std::rotate(deque<int>) (by 1/4)", std_rotate, 0.25);52 bm.operator()<std::list<int>>("std::rotate(list<int>) (by 1/4)", std_rotate, 0.25);53 bm.operator()<std::vector<int>>("rng::rotate(vector<int>) (by 1/4)", std::ranges::rotate, 0.25);54 bm.operator()<std::deque<int>>("rng::rotate(deque<int>) (by 1/4)", std::ranges::rotate, 0.25);55 bm.operator()<std::list<int>>("rng::rotate(list<int>) (by 1/4)", std::ranges::rotate, 0.25);56 57 bm.operator()<std::vector<int>>("std::rotate(vector<int>) (by 1/3)", std_rotate, 0.33);58 bm.operator()<std::deque<int>>("std::rotate(deque<int>) (by 1/3)", std_rotate, 0.33);59 bm.operator()<std::list<int>>("std::rotate(list<int>) (by 1/3)", std_rotate, 0.33);60 bm.operator()<std::vector<int>>("rng::rotate(vector<int>) (by 1/3)", std::ranges::rotate, 0.33);61 bm.operator()<std::deque<int>>("rng::rotate(deque<int>) (by 1/3)", std::ranges::rotate, 0.33);62 bm.operator()<std::list<int>>("rng::rotate(list<int>) (by 1/3)", std::ranges::rotate, 0.33);63 64 bm.operator()<std::vector<int>>("std::rotate(vector<int>) (by 1/2)", std_rotate, 0.50);65 bm.operator()<std::deque<int>>("std::rotate(deque<int>) (by 1/2)", std_rotate, 0.50);66 bm.operator()<std::list<int>>("std::rotate(list<int>) (by 1/2)", std_rotate, 0.50);67 bm.operator()<std::vector<int>>("rng::rotate(vector<int>) (by 1/2)", std::ranges::rotate, 0.50);68 bm.operator()<std::deque<int>>("rng::rotate(deque<int>) (by 1/2)", std::ranges::rotate, 0.50);69 bm.operator()<std::list<int>>("rng::rotate(list<int>) (by 1/2)", std::ranges::rotate, 0.50);70 71 bm.operator()<std::vector<bool>>("std::rotate(vector<bool>) (by 1/4)", std_rotate, 0.25);72 bm.operator()<std::vector<bool>>("std::rotate(vector<bool>) (by 1/3)", std_rotate, 0.33);73 bm.operator()<std::vector<bool>>("std::rotate(vector<bool>) (by 1/2)", std_rotate, 0.50);74 75#if TEST_STD_VER >= 23 // vector<bool>::iterator is not std::permutable before C++2376 bm.operator()<std::vector<bool>>("rng::rotate(vector<bool>) (by 1/4)", std::ranges::rotate, 0.25);77 bm.operator()<std::vector<bool>>("rng::rotate(vector<bool>) (by 1/3)", std::ranges::rotate, 0.33);78 bm.operator()<std::vector<bool>>("rng::rotate(vector<bool>) (by 1/2)", std::ranges::rotate, 0.50);79#endif80 }81 82 // Benchmark {std,ranges}::rotate where we rotate a single element from the beginning to the end of the range.83 {84 auto bm = []<class Container>(std::string name, auto rotate) {85 benchmark::RegisterBenchmark(86 name,87 [rotate](auto& st) {88 std::size_t const size = st.range(0);89 using ValueType = typename Container::value_type;90 Container c;91 std::generate_n(std::back_inserter(c), size, [] { return Generate<ValueType>::random(); });92 93 auto pivot = std::next(c.begin());94 for ([[maybe_unused]] auto _ : st) {95 benchmark::DoNotOptimize(c);96 auto result = rotate(c.begin(), pivot, c.end());97 benchmark::DoNotOptimize(result);98 }99 })100 ->Arg(32)101 ->Arg(50) // non power-of-two102 ->Arg(1024)103 ->Arg(8192);104 };105 bm.operator()<std::vector<int>>("std::rotate(vector<int>) (1 element forward)", std_rotate);106 bm.operator()<std::deque<int>>("std::rotate(deque<int>) (1 element forward)", std_rotate);107 bm.operator()<std::list<int>>("std::rotate(list<int>) (1 element forward)", std_rotate);108 bm.operator()<std::vector<int>>("rng::rotate(vector<int>) (1 element forward)", std::ranges::rotate);109 bm.operator()<std::deque<int>>("rng::rotate(deque<int>) (1 element forward)", std::ranges::rotate);110 bm.operator()<std::list<int>>("rng::rotate(list<int>) (1 element forward)", std::ranges::rotate);111 112 bm.operator()<std::vector<bool>>("std::rotate(vector<bool>) (1 element forward)", std_rotate);113#if TEST_STD_VER >= 23 // vector<bool>::iterator is not std::permutable before C++23114 bm.operator()<std::vector<bool>>("rng::rotate(vector<bool>) (1 element forward)", std::ranges::rotate);115#endif116 }117 118 // Benchmark {std,ranges}::rotate where we rotate a single element from the end to the beginning of the range.119 {120 auto bm = []<class Container>(std::string name, auto rotate) {121 benchmark::RegisterBenchmark(122 name,123 [rotate](auto& st) {124 std::size_t const size = st.range(0);125 using ValueType = typename Container::value_type;126 Container c;127 std::generate_n(std::back_inserter(c), size, [] { return Generate<ValueType>::random(); });128 129 auto pivot = std::next(c.begin(), size - 1);130 for ([[maybe_unused]] auto _ : st) {131 benchmark::DoNotOptimize(c);132 auto result = rotate(c.begin(), pivot, c.end());133 benchmark::DoNotOptimize(result);134 }135 })136 ->Arg(32)137 ->Arg(50) // non power-of-two138 ->Arg(1024)139 ->Arg(8192);140 };141 bm.operator()<std::vector<int>>("std::rotate(vector<int>) (1 element backward)", std_rotate);142 bm.operator()<std::deque<int>>("std::rotate(deque<int>) (1 element backward)", std_rotate);143 bm.operator()<std::list<int>>("std::rotate(list<int>) (1 element backward)", std_rotate);144 bm.operator()<std::vector<int>>("rng::rotate(vector<int>) (1 element backward)", std::ranges::rotate);145 bm.operator()<std::deque<int>>("rng::rotate(deque<int>) (1 element backward)", std::ranges::rotate);146 bm.operator()<std::list<int>>("rng::rotate(list<int>) (1 element backward)", std::ranges::rotate);147 148 bm.operator()<std::vector<bool>>("std::rotate(vector<bool>) (1 element backward)", std_rotate);149#if TEST_STD_VER >= 23 // vector<bool>::iterator is not std::permutable before C++23150 bm.operator()<std::vector<bool>>("rng::rotate(vector<bool>) (1 element backward)", std::ranges::rotate);151#endif152 }153 154 benchmark::Initialize(&argc, argv);155 benchmark::RunSpecifiedBenchmarks();156 benchmark::Shutdown();157 return 0;158}159