248 lines · c
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#ifndef LIBCXX_ALGORITHMS_COMMON_H10#define LIBCXX_ALGORITHMS_COMMON_H11 12#include <algorithm>13#include <numeric>14#include <tuple>15#include <vector>16 17#include "../CartesianBenchmarks.h"18#include "../GenerateInput.h"19 20enum class ValueType { Uint32, Uint64, Pair, Tuple, String, Float };21struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 6> {22 static constexpr const char* Names[] = {23 "uint32", "uint64", "pair<uint32, uint32>", "tuple<uint32, uint64, uint32>", "string", "float"};24};25 26using Types =27 std::tuple<uint32_t,28 uint64_t,29 std::pair<uint32_t, uint32_t>,30 std::tuple<uint32_t, uint64_t, uint32_t>,31 std::string,32 float>;33 34template <class V>35using Value = std::tuple_element_t<(int)V::value, Types>;36 37enum class Order {38 Random,39 Ascending,40 Descending,41 SingleElement,42 PipeOrgan,43 Heap,44 QuickSortAdversary,45};46struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 7> {47 static constexpr const char* Names[] = {48 "Random", "Ascending", "Descending", "SingleElement", "PipeOrgan", "Heap", "QuickSortAdversary"};49};50 51// fillAdversarialQuickSortInput fills the input vector with N int-like values.52// These values are arranged in such a way that they would invoke O(N^2)53// behavior on any quick sort implementation that satisifies certain conditions.54// Details are available in the following paper:55// "A Killer Adversary for Quicksort", M. D. McIlroy, Software-Practice &56// Experience Volume 29 Issue 4 April 10, 1999 pp 341-344.57// https://dl.acm.org/doi/10.5555/311868.311871.58template <class T>59void fillAdversarialQuickSortInput(T& V, size_t N) {60 assert(N > 0);61 // If an element is equal to gas, it indicates that the value of the element62 // is still to be decided and may change over the course of time.63 const unsigned int gas = N - 1;64 V.resize(N);65 for (unsigned int i = 0; i < N; ++i) {66 V[i] = gas;67 }68 // Candidate for the pivot position.69 int candidate = 0;70 int nsolid = 0;71 // Populate all positions in the generated input to gas.72 std::vector<int> ascVals(V.size());73 // Fill up with ascending values from 0 to V.size()-1. These will act as74 // indices into V.75 std::iota(ascVals.begin(), ascVals.end(), 0);76 std::sort(ascVals.begin(), ascVals.end(), [&](int x, int y) {77 if (V[x] == gas && V[y] == gas) {78 // We are comparing two inputs whose value is still to be decided.79 if (x == candidate) {80 V[x] = nsolid++;81 } else {82 V[y] = nsolid++;83 }84 }85 if (V[x] == gas) {86 candidate = x;87 } else if (V[y] == gas) {88 candidate = y;89 }90 return V[x] < V[y];91 });92}93 94template <typename T>95void fillValues(std::vector<T>& V, size_t N, Order O) {96 if (O == Order::SingleElement) {97 V.resize(N, 0);98 } else if (O == Order::QuickSortAdversary) {99 fillAdversarialQuickSortInput(V, N);100 } else {101 while (V.size() < N)102 V.push_back(V.size());103 }104}105 106template <typename T>107void fillValues(std::vector<std::pair<T, T> >& V, size_t N, Order O) {108 if (O == Order::SingleElement) {109 V.resize(N, std::make_pair(0, 0));110 } else {111 while (V.size() < N)112 // Half of array will have the same first element.113 if (V.size() % 2) {114 V.push_back(std::make_pair(V.size(), V.size()));115 } else {116 V.push_back(std::make_pair(0, V.size()));117 }118 }119}120 121template <typename T1, typename T2, typename T3>122void fillValues(std::vector<std::tuple<T1, T2, T3> >& V, size_t N, Order O) {123 if (O == Order::SingleElement) {124 V.resize(N, std::make_tuple(0, 0, 0));125 } else {126 while (V.size() < N)127 // One third of array will have the same first element.128 // One third of array will have the same first element and the same second element.129 switch (V.size() % 3) {130 case 0:131 V.push_back(std::make_tuple(V.size(), V.size(), V.size()));132 break;133 case 1:134 V.push_back(std::make_tuple(0, V.size(), V.size()));135 break;136 case 2:137 V.push_back(std::make_tuple(0, 0, V.size()));138 break;139 }140 }141}142 143inline void fillValues(std::vector<std::string>& V, size_t N, Order O) {144 if (O == Order::SingleElement) {145 V.resize(N, getRandomString(64));146 } else {147 while (V.size() < N)148 V.push_back(getRandomString(64));149 }150}151 152template <class T>153void sortValues(T& V, Order O) {154 switch (O) {155 case Order::Random: {156 std::random_device R;157 std::mt19937 M(R());158 std::shuffle(V.begin(), V.end(), M);159 break;160 }161 case Order::Ascending:162 std::sort(V.begin(), V.end());163 break;164 case Order::Descending:165 std::sort(V.begin(), V.end(), std::greater<>());166 break;167 case Order::SingleElement:168 // Nothing to do169 break;170 case Order::PipeOrgan:171 std::sort(V.begin(), V.end());172 std::reverse(V.begin() + V.size() / 2, V.end());173 break;174 case Order::Heap:175 std::make_heap(V.begin(), V.end());176 break;177 case Order::QuickSortAdversary:178 // Nothing to do179 break;180 }181}182 183constexpr size_t TestSetElements =184#if !TEST_HAS_FEATURE(memory_sanitizer)185 1 << 18;186#else187 1 << 14;188#endif189 190template <class ValueType>191std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N, Order O) {192 std::vector<std::vector<Value<ValueType> > > Ret;193 const size_t NumCopies = std::max(size_t{1}, TestSetElements / N);194 Ret.resize(NumCopies);195 for (auto& V : Ret) {196 fillValues(V, N, O);197 sortValues(V, O);198 }199 return Ret;200}201 202template <class T, class U>203TEST_ALWAYS_INLINE void resetCopies(benchmark::State& state, T& Copies, U& Orig) {204 state.PauseTiming();205 for (auto& Copy : Copies)206 Copy = Orig;207 state.ResumeTiming();208}209 210enum class BatchSize {211 CountElements,212 CountBatch,213};214 215template <class ValueType, class F>216void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O, BatchSize Count, F Body) {217 auto Copies = makeOrderedValues<ValueType>(Quantity, O);218 auto Orig = Copies;219 220 const size_t Batch = Count == BatchSize::CountElements ? Copies.size() * Quantity : Copies.size();221 while (state.KeepRunningBatch(Batch)) {222 for (auto& Copy : Copies) {223 Body(Copy);224 benchmark::DoNotOptimize(Copy);225 }226 state.PauseTiming();227 Copies = Orig;228 state.ResumeTiming();229 }230}231 232const std::vector<size_t> Quantities = {233 1 << 0,234 1 << 2,235 1 << 4,236 1 << 6,237 1 << 8,238 1 << 10,239 1 << 14,240// Running each benchmark in parallel consumes too much memory with MSAN241// and can lead to the test process being killed.242#if !TEST_HAS_FEATURE(memory_sanitizer)243 1 << 18244#endif245};246 247#endif // LIBCXX_ALGORITHMS_COMMON_H248