187 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 <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 types23struct 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 lie40enum class OverlapPosition {41 None,42 Front,43 // performance-wise, matches at the back are identical to ones at the front44 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 elements52template <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 memory95// this is especially important for containers with non-contiguous element96// storage, but it will affect even a std::vector, because when you copy a97// std::vector<std::string> the underlying data storage position for the char98// arrays of the copy are likely to have high locality99template <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 if116 // we copy after sorting it will likely have high locality, so we sort117 // each copy separately118 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 could137 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 runs150 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(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(size1_) + '_' + std::to_string(size2_);172 }173};174 175} // namespace176 177int main(int argc, char** argv) { /**/178 benchmark::Initialize(&argc, argv);179 if (benchmark::ReportUnrecognizedArguments(argc, argv))180 return 1;181 182 makeCartesianProductBenchmark<SetIntersection, AllValueTypes, AllContainerTypes, AllOverlapPositions>(183 Quantities, Quantities);184 benchmark::RunSpecifiedBenchmarks();185 return 0;186}187