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-exception
6//
7//===----------------------------------------------------------------------===//
8
9// UNSUPPORTED: c++03, c++11, c++14, c++17
10
11#include <algorithm>
12#include <array>
13#include <cstddef>
14#include <deque>
15#include <string>
16#include <vector>
17
18#include "benchmark/benchmark.h"
19#include "common.h"
20
21int main(int argc, char** argv) {
22 auto std_partial_sort = [](auto first, auto mid, auto last) { return std::partial_sort(first, mid, last); };
23
24 // Benchmark {std,ranges}::partial_sort on various types of data. We always partially sort only
25 // half of the full range.
26 //
27 // We perform this benchmark in a batch because we need to restore the
28 // state of the container after the operation.
29 //
30 // Also note that we intentionally don't benchmark the predicated version of the algorithm
31 // because that makes the benchmark run too slowly.
32 {
33 auto bm = []<class Container>(std::string name, auto partial_sort, auto generate_data) {
34 benchmark::RegisterBenchmark(
35 name,
36 [partial_sort, generate_data](auto& st) {
37 std::size_t const size = st.range(0);
38 constexpr std::size_t BatchSize = 32;
39 using ValueType = typename Container::value_type;
40 std::vector<ValueType> data = generate_data(size);
41 std::array<Container, BatchSize> c;
42 std::fill_n(c.begin(), BatchSize, Container(data.begin(), data.end()));
43
44 std::size_t const half = size / 2;
45 while (st.KeepRunningBatch(BatchSize)) {
46 for (std::size_t i = 0; i != BatchSize; ++i) {
47 benchmark::DoNotOptimize(c[i]);
48 partial_sort(c[i].begin(), c[i].begin() + half, c[i].end());
49 benchmark::DoNotOptimize(c[i]);
50 }
51
52 st.PauseTiming();
53 for (std::size_t i = 0; i != BatchSize; ++i) {
54 std::copy(data.begin(), data.end(), c[i].begin());
55 }
56 st.ResumeTiming();
57 }
58 })
59 ->Arg(8)
60 ->Arg(1024)
61 ->Arg(8192);
62 };
63
64 auto register_bm = [&](auto generate, std::string variant) {
65 auto gen2 = [generate](auto size) {
66 std::vector<int> data = generate(size);
67 std::vector<support::NonIntegral> real_data(data.begin(), data.end());
68 return real_data;
69 };
70 auto name = [variant](std::string op) { return op + " (" + variant + ")"; };
71 bm.operator()<std::vector<int>>(name("std::partial_sort(vector<int>"), std_partial_sort, generate);
72 bm.operator()<std::vector<support::NonIntegral>>(
73 name("std::partial_sort(vector<NonIntegral>"), std_partial_sort, gen2);
74 bm.operator()<std::deque<int>>(name("std::partial_sort(deque<int>"), std_partial_sort, generate);
75
76 bm.operator()<std::vector<int>>(name("rng::partial_sort(vector<int>"), std::ranges::partial_sort, generate);
77 bm.operator()<std::vector<support::NonIntegral>>(
78 name("rng::partial_sort(vector<NonIntegral>"), std::ranges::partial_sort, gen2);
79 bm.operator()<std::deque<int>>(name("rng::partial_sort(deque<int>"), std::ranges::partial_sort, generate);
80 };
81
82 register_bm(support::quicksort_adversarial_data<int>, "qsort adversarial");
83 register_bm(support::ascending_sorted_data<int>, "ascending");
84 register_bm(support::descending_sorted_data<int>, "descending");
85 register_bm(support::pipe_organ_data<int>, "pipe-organ");
86 register_bm(support::heap_data<int>, "heap");
87 register_bm(support::shuffled_data<int>, "shuffled");
88 register_bm(support::single_element_data<int>, "repeated");
89 }
90
91 benchmark::Initialize(&argc, argv);
92 benchmark::RunSpecifiedBenchmarks();
93 benchmark::Shutdown();
94 return 0;
95}
96

source code of libcxx/test/benchmarks/algorithms/sorting/partial_sort.bench.cpp