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 <cstdlib>
13#include <iterator>
14#include <set>
15#include <vector>
16
17#include "common.h"
18#include "test_iterators.h"
19
20namespace {
21
22// types of containers we'll want to test, covering interesting iterator types
23struct VectorContainer {
24 template <typename... Args>
25 using type = std::vector<Args...>;
26
27 static constexpr const char* Name = "Vector";
28};
29
30struct SetContainer {
31 template <typename... Args>
32 using type = std::set<Args...>;
33
34 static constexpr const char* Name = "Set";
35};
36
37using AllContainerTypes = std::tuple<VectorContainer, SetContainer>;
38
39// set_intersection performance may depend on where matching values lie
40enum class OverlapPosition {
41 None,
42 Front,
43 // performance-wise, matches at the back are identical to ones at the front
44 Interlaced,
45};
46
47struct AllOverlapPositions : EnumValuesAsTuple<AllOverlapPositions, OverlapPosition, 3> {
48 static constexpr const char* Names[] = {"None", "Front", "Interlaced"};
49};
50
51// forward_iterator wrapping which, for each increment, moves the underlying iterator forward Stride elements
52template <typename Wrapped>
53struct StridedFwdIt {
54 Wrapped base_;
55 unsigned stride_;
56
57 using iterator_category = std::forward_iterator_tag;
58 using difference_type = typename Wrapped::difference_type;
59 using value_type = typename Wrapped::value_type;
60 using pointer = typename Wrapped::pointer;
61 using reference = typename Wrapped::reference;
62
63 StridedFwdIt(Wrapped base, unsigned stride) : base_(base), stride_(stride) { assert(stride_ != 0); }
64
65 StridedFwdIt operator++() {
66 for (unsigned i = 0; i < stride_; ++i)
67 ++base_;
68 return *this;
69 }
70 StridedFwdIt operator++(int) {
71 auto tmp = *this;
72 ++*this;
73 return tmp;
74 }
75 value_type& operator*() { return *base_; }
76 const value_type& operator*() const { return *base_; }
77 value_type& operator->() { return *base_; }
78 const value_type& operator->() const { return *base_; }
79 bool operator==(const StridedFwdIt& o) const { return base_ == o.base_; }
80 bool operator!=(const StridedFwdIt& o) const { return !operator==(o); }
81};
82template <typename Wrapped>
83StridedFwdIt(Wrapped, unsigned) -> StridedFwdIt<Wrapped>;
84
85template <typename T>
86std::vector<T> getVectorOfRandom(size_t N) {
87 std::vector<T> v;
88 fillValues(v, N, Order::Random);
89 sortValues(v, Order::Random);
90 return std::vector<T>(v);
91}
92
93// Realistically, data won't all be nicely contiguous in a container,
94// we'll go through some effort to ensure that it's shuffled through memory
95// this is especially important for containers with non-contiguous element
96// storage, but it will affect even a std::vector, because when you copy a
97// std::vector<std::string> the underlying data storage position for the char
98// arrays of the copy are likely to have high locality
99template <class Container>
100std::pair<Container, Container> genCacheUnfriendlyData(size_t size1, size_t size2, OverlapPosition pos) {
101 using ValueType = typename Container::value_type;
102 auto move_into = [](auto first, auto last) {
103 Container out;
104 std::move(first, last, std::inserter(out, out.begin()));
105 return out;
106 };
107 const auto src_size = pos == OverlapPosition::None ? size1 + size2 : std::max(size1, size2);
108 std::vector<ValueType> src = getVectorOfRandom<ValueType>(src_size);
109
110 if (pos == OverlapPosition::None) {
111 std::sort(src.begin(), src.end());
112 return std::make_pair(move_into(src.begin(), src.begin() + size1), move_into(src.begin() + size1, src.end()));
113 }
114
115 // All other overlap types will have to copy some part of the data, but if
116 // we copy after sorting it will likely have high locality, so we sort
117 // each copy separately
118 auto copy = src;
119 std::sort(src.begin(), src.end());
120 std::sort(copy.begin(), copy.end());
121
122 switch (pos) {
123 case OverlapPosition::None:
124 // we like -Wswitch :)
125 break;
126
127 case OverlapPosition::Front:
128 return std::make_pair(move_into(src.begin(), src.begin() + size1), move_into(copy.begin(), copy.begin() + size2));
129
130 case OverlapPosition::Interlaced:
131 const auto stride1 = size1 < size2 ? size2 / size1 : 1;
132 const auto stride2 = size2 < size1 ? size1 / size2 : 1;
133 return std::make_pair(move_into(StridedFwdIt(src.begin(), stride1), StridedFwdIt(src.end(), stride1)),
134 move_into(StridedFwdIt(copy.begin(), stride2), StridedFwdIt(copy.end(), stride2)));
135 }
136 std::abort(); // would be std::unreachable() if it could
137 return std::pair<Container, Container>();
138}
139
140template <class ValueType, class Container, class Overlap>
141struct SetIntersection {
142 using ContainerType = typename Container::template type<Value<ValueType>>;
143 size_t size1_;
144 size_t size2_;
145
146 SetIntersection(size_t size1, size_t size2) : size1_(size1), size2_(size2) {}
147
148 bool skip() const noexcept {
149 // let's save some time and skip simmetrical runs
150 return size1_ < size2_;
151 }
152
153 void run(benchmark::State& state) const {
154 auto input = genCacheUnfriendlyData<ContainerType>(size1_, size2_, Overlap());
155 std::vector<Value<ValueType>> out(std::min(size1_, size2_));
156
157 const auto BATCH_SIZE = std::max(size_t{512}, (2 * TestSetElements) / (size1_ + size2_));
158 for (const auto& _ : state) {
159 while (state.KeepRunningBatch(n: BATCH_SIZE)) {
160 for (unsigned i = 0; i < BATCH_SIZE; ++i) {
161 const auto& [c1, c2] = input;
162 auto res = std::set_intersection(c1.begin(), c1.end(), c2.begin(), c2.end(), out.begin());
163 benchmark::DoNotOptimize(res);
164 }
165 }
166 }
167 }
168
169 std::string name() const {
170 return std::string("SetIntersection") + Overlap::name() + '_' + Container::Name + ValueType::name() + '_' +
171 std::to_string(val: size1_) + '_' + std::to_string(val: size2_);
172 }
173};
174
175} // namespace
176
177int main(int argc, char** argv) { /**/
178 benchmark::Initialize(argc: &argc, argv);
179 if (benchmark::ReportUnrecognizedArguments(argc, argv))
180 return 1;
181
182 makeCartesianProductBenchmark<SetIntersection, AllValueTypes, AllContainerTypes, AllOverlapPositions>(
183 A: Quantities, A: Quantities);
184 benchmark::RunSpecifiedBenchmarks();
185 return 0;
186}
187

source code of libcxx/test/benchmarks/algorithms/set_intersection.bench.cpp