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 <cstddef>
13#include <deque>
14#include <list>
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_copy = [](auto first, auto last, auto dfirst, auto dlast) {
23 return std::partial_sort_copy(first, last, dfirst, dlast);
24 };
25
26 // Benchmark {std,ranges}::partial_sort_copy on various types of data. We always partially
27 // sort only half of the full range.
28 //
29 // Also note that we intentionally don't benchmark the predicated version of the algorithm
30 // because that makes the benchmark run too slowly.
31 {
32 auto bm = []<class Container>(std::string name, auto partial_sort_copy, auto generate_data) {
33 benchmark::RegisterBenchmark(
34 name,
35 [partial_sort_copy, generate_data](auto& st) {
36 std::size_t const size = st.range(0);
37 using ValueType = typename Container::value_type;
38 std::vector<ValueType> data = generate_data(size);
39 Container c(data.begin(), data.end());
40 std::vector<ValueType> out(size / 2);
41
42 for ([[maybe_unused]] auto _ : st) {
43 benchmark::DoNotOptimize(c);
44 benchmark::DoNotOptimize(out);
45 auto result = partial_sort_copy(c.begin(), c.end(), out.begin(), out.end());
46 benchmark::DoNotOptimize(result);
47 }
48 })
49 ->Arg(8)
50 ->Arg(1024)
51 ->Arg(8192);
52 };
53
54 auto register_bm = [&](auto generate, std::string variant) {
55 auto gen2 = [generate](auto size) {
56 std::vector<int> data = generate(size);
57 std::vector<support::NonIntegral> real_data(data.begin(), data.end());
58 return real_data;
59 };
60 auto name = [variant](std::string op) { return op + " (" + variant + ")"; };
61 bm.operator()<std::vector<int>>(name("std::partial_sort_copy(vector<int>)"), std_partial_sort_copy, generate);
62 bm.operator()<std::vector<support::NonIntegral>>(
63 name("std::partial_sort_copy(vector<NonIntegral>)"), std_partial_sort_copy, gen2);
64 bm.operator()<std::deque<int>>(name("std::partial_sort_copy(deque<int>)"), std_partial_sort_copy, generate);
65 bm.operator()<std::list<int>>(name("std::partial_sort_copy(list<int>)"), std_partial_sort_copy, generate);
66
67 bm.operator()<std::vector<int>>(
68 name("rng::partial_sort_copy(vector<int>)"), std::ranges::partial_sort_copy, generate);
69 bm.operator()<std::vector<support::NonIntegral>>(
70 name("rng::partial_sort_copy(vector<NonIntegral>)"), std::ranges::partial_sort_copy, gen2);
71 bm.operator()<std::deque<int>>(
72 name("rng::partial_sort_copy(deque<int>)"), std::ranges::partial_sort_copy, generate);
73 bm.operator()<std::list<int>>(
74 name("rng::partial_sort_copy(list<int>)"), std::ranges::partial_sort_copy, generate);
75 };
76
77 register_bm(support::quicksort_adversarial_data<int>, "qsort adversarial");
78 register_bm(support::ascending_sorted_data<int>, "ascending");
79 register_bm(support::descending_sorted_data<int>, "descending");
80 register_bm(support::pipe_organ_data<int>, "pipe-organ");
81 register_bm(support::heap_data<int>, "heap");
82 register_bm(support::shuffled_data<int>, "shuffled");
83 register_bm(support::single_element_data<int>, "repeated");
84 }
85
86 benchmark::Initialize(&argc, argv);
87 benchmark::RunSpecifiedBenchmarks();
88 benchmark::Shutdown();
89 return 0;
90}
91

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