97 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_is_partitioned = [](auto first, auto last, auto pred) { return std::is_partitioned(first, last, pred); };32 33 auto bm = []<class Container, bool Partitioned>(std::string name, auto is_partitioned) {34 benchmark::RegisterBenchmark(35 name,36 [is_partitioned](auto& st) {37 std::size_t const size = st.range(0);38 using ValueType = typename Container::value_type;39 Container c;40 std::generate_n(std::back_inserter(c), size, [] { return Generate<ValueType>::random(); });41 42 // Partition the container in two equally-sized halves, ensuring the median43 // value appears in the left half. Note that the median value isn't located44 // in the middle -- this isn't std::nth_element.45 ValueType median = compute_median(c.begin(), c.end());46 auto pred = [median](auto const& element) { return element <= median; };47 std::partition(c.begin(), c.end(), pred);48 assert(std::is_partitioned(c.begin(), c.end(), pred));49 50 if constexpr (!Partitioned) {51 // De-partition the container by swapping the element containing the median52 // value with the last one.53 auto median_it = std::find(c.begin(), c.end(), median);54 auto last_it = std::next(c.begin(), c.size() - 1);55 std::iter_swap(median_it, last_it);56 assert(!std::is_partitioned(c.begin(), c.end(), pred));57 }58 59 for ([[maybe_unused]] auto _ : st) {60 benchmark::DoNotOptimize(c);61 auto result = is_partitioned(c.begin(), c.end(), pred);62 benchmark::DoNotOptimize(result);63 }64 })65 ->Arg(32)66 ->Arg(50) // non power-of-two67 ->Arg(1024)68 ->Arg(8192);69 };70 71 // std::is_partitioned72 bm.operator()<std::vector<int>, true>("std::is_partitioned(vector<int>) (partitioned)", std_is_partitioned);73 bm.operator()<std::vector<int>, false>("std::is_partitioned(vector<int>) (unpartitioned)", std_is_partitioned);74 75 bm.operator()<std::deque<int>, true>("std::is_partitioned(deque<int>) (partitioned)", std_is_partitioned);76 bm.operator()<std::deque<int>, false>("std::is_partitioned(deque<int>) (unpartitioned)", std_is_partitioned);77 78 bm.operator()<std::list<int>, true>("std::is_partitioned(list<int>) (partitioned)", std_is_partitioned);79 bm.operator()<std::list<int>, false>("std::is_partitioned(list<int>) (unpartitioned)", std_is_partitioned);80 81 // ranges::is_partitioned82 bm.operator()<std::vector<int>, true>("rng::is_partitioned(vector<int>) (partitioned)", std::ranges::is_partitioned);83 bm.operator()<std::vector<int>, false>(84 "rng::is_partitioned(vector<int>) (unpartitioned)", std::ranges::is_partitioned);85 86 bm.operator()<std::deque<int>, true>("rng::is_partitioned(deque<int>) (partitioned)", std::ranges::is_partitioned);87 bm.operator()<std::deque<int>, false>("rng::is_partitioned(deque<int>) (unpartitioned)", std::ranges::is_partitioned);88 89 bm.operator()<std::list<int>, true>("rng::is_partitioned(list<int>) (partitioned)", std::ranges::is_partitioned);90 bm.operator()<std::list<int>, false>("rng::is_partitioned(list<int>) (unpartitioned)", std::ranges::is_partitioned);91 92 benchmark::Initialize(&argc, argv);93 benchmark::RunSpecifiedBenchmarks();94 benchmark::Shutdown();95 return 0;96}97