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