184 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 "count_new.h"20#include "benchmark/benchmark.h"21#include "../../GenerateInput.h"22 23auto compute_median(auto first, auto last) {24 std::vector v(first, last);25 auto middle = v.begin() + v.size() / 2;26 std::nth_element(v.begin(), middle, v.end());27 return *middle;28}29 30int main(int argc, char** argv) {31 auto std_stable_partition = [](auto first, auto last, auto pred) { return std::stable_partition(first, last, pred); };32 33 // Benchmark {std,ranges}::stable_partition on a fully unpartitionned sequence, i.e. a lot of elements34 // have to be moved around in order to partition the range.35 {36 auto bm = []<class Container>(std::string name, auto stable_partition) {37 benchmark::RegisterBenchmark(38 name,39 [stable_partition](auto& st) {40 std::size_t const size = st.range(0);41 using ValueType = typename Container::value_type;42 Container c;43 std::generate_n(std::back_inserter(c), size, [] { return Generate<ValueType>::random(); });44 45 ValueType median = compute_median(c.begin(), c.end());46 auto pred1 = [median](auto const& element) { return element < median; };47 auto pred2 = [median](auto const& element) { return element > median; };48 bool toggle = false;49 50 for ([[maybe_unused]] auto _ : st) {51 benchmark::DoNotOptimize(c);52 // By toggling the predicate, we have to move almost all elements in the sequence53 // to restore the partition.54 if (toggle) {55 auto result = stable_partition(c.begin(), c.end(), pred1);56 benchmark::DoNotOptimize(result);57 } else {58 auto result = stable_partition(c.begin(), c.end(), pred2);59 benchmark::DoNotOptimize(result);60 }61 toggle = !toggle;62 }63 })64 ->Arg(32)65 ->Arg(50) // non power-of-two66 ->Arg(1024)67 ->Arg(8192);68 };69 70 // std::stable_partition71 bm.operator()<std::vector<int>>("std::stable_partition(vector<int>) (dense)", std_stable_partition);72 bm.operator()<std::deque<int>>("std::stable_partition(deque<int>) (dense)", std_stable_partition);73 bm.operator()<std::list<int>>("std::stable_partition(list<int>) (dense)", std_stable_partition);74 75 // ranges::stable_partition76 bm.operator()<std::vector<int>>("rng::stable_partition(vector<int>) (dense)", std::ranges::stable_partition);77 bm.operator()<std::deque<int>>("rng::stable_partition(deque<int>) (dense)", std::ranges::stable_partition);78 bm.operator()<std::list<int>>("rng::stable_partition(list<int>) (dense)", std::ranges::stable_partition);79 }80 81 // Benchmark {std,ranges}::stable_partition on a mostly partitioned sequence, i.e. only 10% of the elements82 // have to be moved around in order to partition the range.83 {84 auto bm = []<class Container>(std::string name, auto stable_partition) {85 benchmark::RegisterBenchmark(86 name,87 [stable_partition](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 ValueType median = compute_median(c.begin(), c.end());93 auto pred = [median](auto const& element) { return element < median; };94 std::partition(c.begin(), c.end(), pred);95 96 // Between iterations, we swap 5% of the elements to the left of the median with 5% of the elements97 // to the right of the median. This ensures that the range is slightly unpartitioned.98 auto median_it = std::partition_point(c.begin(), c.end(), pred);99 auto low = std::next(c.begin(), std::distance(c.begin(), median_it) - (size / 20));100 auto high = std::next(median_it, size / 20);101 auto shuffle = [&] { std::swap_ranges(low, median_it, high); };102 shuffle();103 assert(!std::is_partitioned(c.begin(), c.end(), pred));104 105 for ([[maybe_unused]] auto _ : st) {106 benchmark::DoNotOptimize(c);107 auto result = stable_partition(c.begin(), c.end(), pred);108 benchmark::DoNotOptimize(result);109 shuffle();110 }111 })112 ->Arg(32)113 ->Arg(50) // non power-of-two114 ->Arg(1024)115 ->Arg(8192);116 };117 118 // std::stable_partition119 bm.operator()<std::vector<int>>("std::stable_partition(vector<int>) (sparse)", std_stable_partition);120 bm.operator()<std::deque<int>>("std::stable_partition(deque<int>) (sparse)", std_stable_partition);121 bm.operator()<std::list<int>>("std::stable_partition(list<int>) (sparse)", std_stable_partition);122 123 // ranges::stable_partition124 bm.operator()<std::vector<int>>("rng::stable_partition(vector<int>) (sparse)", std::ranges::stable_partition);125 bm.operator()<std::deque<int>>("rng::stable_partition(deque<int>) (sparse)", std::ranges::stable_partition);126 bm.operator()<std::list<int>>("rng::stable_partition(list<int>) (sparse)", std::ranges::stable_partition);127 }128 129 // Benchmark {std,ranges}::stable_partition when memory allocation fails. The algorithm must fall back to130 // a different algorithm that has different complexity guarantees.131 {132 auto bm = []<class Container>(std::string name, auto stable_partition) {133 benchmark::RegisterBenchmark(134 name,135 [stable_partition](auto& st) {136 std::size_t const size = st.range(0);137 using ValueType = typename Container::value_type;138 Container c;139 std::generate_n(std::back_inserter(c), size, [] { return Generate<ValueType>::random(); });140 141 ValueType median = compute_median(c.begin(), c.end());142 auto pred1 = [median](auto const& element) { return element < median; };143 auto pred2 = [median](auto const& element) { return element > median; };144 bool toggle = false;145 146 for ([[maybe_unused]] auto _ : st) {147 benchmark::DoNotOptimize(c);148 // Disable the ability to allocate memory inside this block149 globalMemCounter.reset();150 globalMemCounter.throw_after = 0;151 152 if (toggle) {153 auto result = stable_partition(c.begin(), c.end(), pred1);154 benchmark::DoNotOptimize(result);155 } else {156 auto result = stable_partition(c.begin(), c.end(), pred2);157 benchmark::DoNotOptimize(result);158 }159 toggle = !toggle;160 }161 })162 ->Arg(32)163 ->Arg(50) // non power-of-two164 ->Arg(1024)165 ->Arg(8192);166 };167 168 // std::stable_partition169 bm.operator()<std::vector<int>>("std::stable_partition(vector<int>) (alloc fails)", std_stable_partition);170 bm.operator()<std::deque<int>>("std::stable_partition(deque<int>) (alloc fails)", std_stable_partition);171 bm.operator()<std::list<int>>("std::stable_partition(list<int>) (alloc fails)", std_stable_partition);172 173 // ranges::stable_partition174 bm.operator()<std::vector<int>>("rng::stable_partition(vector<int>) (alloc fails)", std::ranges::stable_partition);175 bm.operator()<std::deque<int>>("rng::stable_partition(deque<int>) (alloc fails)", std::ranges::stable_partition);176 bm.operator()<std::list<int>>("rng::stable_partition(list<int>) (alloc fails)", std::ranges::stable_partition);177 }178 179 benchmark::Initialize(&argc, argv);180 benchmark::RunSpecifiedBenchmarks();181 benchmark::Shutdown();182 return 0;183}184