134 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 <cassert>13#include <cstddef>14#include <deque>15#include <iterator>16#include <list>17#include <string>18#include <vector>19 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_partition = [](auto first, auto last, auto pred) { return std::partition(first, last, pred); };32 33 // Benchmark {std,ranges}::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 partition) {37 benchmark::RegisterBenchmark(38 name,39 [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 = partition(c.begin(), c.end(), pred1);56 benchmark::DoNotOptimize(result);57 } else {58 auto result = 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::partition71 bm.operator()<std::vector<int>>("std::partition(vector<int>) (dense)", std_partition);72 bm.operator()<std::deque<int>>("std::partition(deque<int>) (dense)", std_partition);73 bm.operator()<std::list<int>>("std::partition(list<int>) (dense)", std_partition);74 75 // ranges::partition76 bm.operator()<std::vector<int>>("rng::partition(vector<int>) (dense)", std::ranges::partition);77 bm.operator()<std::deque<int>>("rng::partition(deque<int>) (dense)", std::ranges::partition);78 bm.operator()<std::list<int>>("rng::partition(list<int>) (dense)", std::ranges::partition);79 }80 81 // Benchmark {std,ranges}::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 partition) {85 benchmark::RegisterBenchmark(86 name,87 [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 = 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::partition119 bm.operator()<std::vector<int>>("std::partition(vector<int>) (sparse)", std_partition);120 bm.operator()<std::deque<int>>("std::partition(deque<int>) (sparse)", std_partition);121 bm.operator()<std::list<int>>("std::partition(list<int>) (sparse)", std_partition);122 123 // ranges::partition124 bm.operator()<std::vector<int>>("rng::partition(vector<int>) (sparse)", std::ranges::partition);125 bm.operator()<std::deque<int>>("rng::partition(deque<int>) (sparse)", std::ranges::partition);126 bm.operator()<std::list<int>>("rng::partition(list<int>) (sparse)", std::ranges::partition);127 }128 129 benchmark::Initialize(&argc, argv);130 benchmark::RunSpecifiedBenchmarks();131 benchmark::Shutdown();132 return 0;133}134