Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 1 | |
| 2 | #include <algorithm> |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 3 | #include <cstdint> |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 4 | #include <map> |
| 5 | #include <random> |
| 6 | #include <string> |
| 7 | #include <utility> |
| 8 | #include <vector> |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 9 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 10 | #include "CartesianBenchmarks.hpp" |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 11 | #include "GenerateInput.hpp" |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 12 | #include "benchmark/benchmark.h" |
| 13 | #include "test_macros.h" |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 14 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 15 | namespace { |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 16 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 17 | enum class ValueType { Uint32, String }; |
| 18 | struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 2> { |
| 19 | static constexpr const char* Names[] = {"uint32", "string"}; |
| 20 | }; |
| 21 | |
| 22 | template <class V> |
| 23 | using Value = |
| 24 | std::conditional_t<V() == ValueType::Uint32, uint32_t, std::string>; |
| 25 | |
| 26 | enum class Order { |
| 27 | Random, |
| 28 | Ascending, |
| 29 | Descending, |
| 30 | SingleElement, |
| 31 | PipeOrgan, |
| 32 | Heap |
| 33 | }; |
| 34 | struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 6> { |
| 35 | static constexpr const char* Names[] = {"Random", "Ascending", |
| 36 | "Descending", "SingleElement", |
| 37 | "PipeOrgan", "Heap"}; |
| 38 | }; |
| 39 | |
| 40 | void fillValues(std::vector<uint32_t>& V, size_t N, Order O) { |
| 41 | if (O == Order::SingleElement) { |
| 42 | V.resize(N, 0); |
| 43 | } else { |
| 44 | while (V.size() < N) |
| 45 | V.push_back(V.size()); |
| 46 | } |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 47 | } |
| 48 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 49 | void fillValues(std::vector<std::string>& V, size_t N, Order O) { |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 50 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 51 | if (O == Order::SingleElement) { |
| 52 | V.resize(N, getRandomString(1024)); |
| 53 | } else { |
| 54 | while (V.size() < N) |
| 55 | V.push_back(getRandomString(1024)); |
| 56 | } |
| 57 | } |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 58 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 59 | template <class T> |
| 60 | void sortValues(T& V, Order O) { |
| 61 | assert(std::is_sorted(V.begin(), V.end())); |
| 62 | switch (O) { |
| 63 | case Order::Random: { |
| 64 | std::random_device R; |
| 65 | std::mt19937 M(R()); |
| 66 | std::shuffle(V.begin(), V.end(), M); |
| 67 | break; |
| 68 | } |
| 69 | case Order::Ascending: |
| 70 | std::sort(V.begin(), V.end()); |
| 71 | break; |
| 72 | case Order::Descending: |
| 73 | std::sort(V.begin(), V.end(), std::greater<>()); |
| 74 | break; |
| 75 | case Order::SingleElement: |
| 76 | // Nothing to do |
| 77 | break; |
| 78 | case Order::PipeOrgan: |
| 79 | std::sort(V.begin(), V.end()); |
| 80 | std::reverse(V.begin() + V.size() / 2, V.end()); |
| 81 | break; |
| 82 | case Order::Heap: |
| 83 | std::make_heap(V.begin(), V.end()); |
| 84 | break; |
| 85 | } |
| 86 | } |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 87 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 88 | template <class ValueType> |
| 89 | std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N, |
| 90 | Order O) { |
| 91 | // Let's make sure that all random sequences of the same size are the same. |
| 92 | // That way we can compare the different algorithms with the same input. |
| 93 | static std::map<std::pair<size_t, Order>, std::vector<Value<ValueType> > > |
| 94 | Cached; |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 95 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 96 | auto& Values = Cached[{N, O}]; |
| 97 | if (Values.empty()) { |
| 98 | fillValues(Values, N, O); |
| 99 | sortValues(Values, O); |
| 100 | }; |
| 101 | const size_t NumCopies = std::max(size_t{1}, 1000 / N); |
| 102 | return { NumCopies, Values }; |
| 103 | } |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 104 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 105 | template <class T, class U> |
| 106 | TEST_ALWAYS_INLINE void resetCopies(benchmark::State& state, T& Copies, |
| 107 | U& Orig) { |
| 108 | state.PauseTiming(); |
| 109 | for (auto& Copy : Copies) |
| 110 | Copy = Orig; |
| 111 | state.ResumeTiming(); |
| 112 | } |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 113 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 114 | template <class ValueType, class F> |
| 115 | void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O, |
| 116 | bool CountElements, F f) { |
| 117 | auto Copies = makeOrderedValues<ValueType>(Quantity, O); |
| 118 | const auto Orig = Copies[0]; |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 119 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 120 | const size_t Batch = CountElements ? Copies.size() * Quantity : Copies.size(); |
| 121 | while (state.KeepRunningBatch(Batch)) { |
| 122 | for (auto& Copy : Copies) { |
| 123 | f(Copy); |
| 124 | benchmark::DoNotOptimize(Copy); |
| 125 | } |
| 126 | resetCopies(state, Copies, Orig); |
| 127 | } |
| 128 | } |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 129 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 130 | template <class ValueType, class Order> |
| 131 | struct Sort { |
| 132 | size_t Quantity; |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 133 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 134 | void run(benchmark::State& state) const { |
| 135 | runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) { |
| 136 | std::sort(Copy.begin(), Copy.end()); |
| 137 | }); |
| 138 | } |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 139 | |
Samuel Benzaquen | c1f6028 | 2018-11-20 17:15:17 +0000 | [diff] [blame^] | 140 | bool skip() const { return Order() == ::Order::Heap; } |
| 141 | |
| 142 | std::string name() const { |
| 143 | return "BM_Sort" + ValueType::name() + Order::name() + "_" + |
| 144 | std::to_string(Quantity); |
| 145 | }; |
| 146 | }; |
| 147 | |
| 148 | template <class ValueType, class Order> |
| 149 | struct StableSort { |
| 150 | size_t Quantity; |
| 151 | |
| 152 | void run(benchmark::State& state) const { |
| 153 | runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) { |
| 154 | std::stable_sort(Copy.begin(), Copy.end()); |
| 155 | }); |
| 156 | } |
| 157 | |
| 158 | bool skip() const { return Order() == ::Order::Heap; } |
| 159 | |
| 160 | std::string name() const { |
| 161 | return "BM_StableSort" + ValueType::name() + Order::name() + "_" + |
| 162 | std::to_string(Quantity); |
| 163 | }; |
| 164 | }; |
| 165 | |
| 166 | template <class ValueType, class Order> |
| 167 | struct MakeHeap { |
| 168 | size_t Quantity; |
| 169 | |
| 170 | void run(benchmark::State& state) const { |
| 171 | runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) { |
| 172 | std::make_heap(Copy.begin(), Copy.end()); |
| 173 | }); |
| 174 | } |
| 175 | |
| 176 | std::string name() const { |
| 177 | return "BM_MakeHeap" + ValueType::name() + Order::name() + "_" + |
| 178 | std::to_string(Quantity); |
| 179 | }; |
| 180 | }; |
| 181 | |
| 182 | template <class ValueType> |
| 183 | struct SortHeap { |
| 184 | size_t Quantity; |
| 185 | |
| 186 | void run(benchmark::State& state) const { |
| 187 | runOpOnCopies<ValueType>( |
| 188 | state, Quantity, Order::Heap, false, |
| 189 | [](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); }); |
| 190 | } |
| 191 | |
| 192 | std::string name() const { |
| 193 | return "BM_SortHeap" + ValueType::name() + "_" + std::to_string(Quantity); |
| 194 | }; |
| 195 | }; |
| 196 | |
| 197 | template <class ValueType, class Order> |
| 198 | struct MakeThenSortHeap { |
| 199 | size_t Quantity; |
| 200 | |
| 201 | void run(benchmark::State& state) const { |
| 202 | runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) { |
| 203 | std::make_heap(Copy.begin(), Copy.end()); |
| 204 | std::sort_heap(Copy.begin(), Copy.end()); |
| 205 | }); |
| 206 | } |
| 207 | |
| 208 | std::string name() const { |
| 209 | return "BM_MakeThenSortHeap" + ValueType::name() + Order::name() + "_" + |
| 210 | std::to_string(Quantity); |
| 211 | }; |
| 212 | }; |
| 213 | |
| 214 | template <class ValueType, class Order> |
| 215 | struct PushHeap { |
| 216 | size_t Quantity; |
| 217 | |
| 218 | void run(benchmark::State& state) const { |
| 219 | runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) { |
| 220 | for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) { |
| 221 | std::push_heap(Copy.begin(), I + 1); |
| 222 | } |
| 223 | }); |
| 224 | } |
| 225 | |
| 226 | bool skip() const { return Order() == ::Order::Heap; } |
| 227 | |
| 228 | std::string name() const { |
| 229 | return "BM_PushHeap" + ValueType::name() + Order::name() + "_" + |
| 230 | std::to_string(Quantity); |
| 231 | }; |
| 232 | }; |
| 233 | |
| 234 | template <class ValueType> |
| 235 | struct PopHeap { |
| 236 | size_t Quantity; |
| 237 | |
| 238 | void run(benchmark::State& state) const { |
| 239 | runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) { |
| 240 | for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) { |
| 241 | std::pop_heap(B, I); |
| 242 | } |
| 243 | }); |
| 244 | } |
| 245 | |
| 246 | std::string name() const { |
| 247 | return "BM_PopHeap" + ValueType::name() + "_" + std::to_string(Quantity); |
| 248 | }; |
| 249 | }; |
| 250 | |
| 251 | } // namespace |
| 252 | |
| 253 | int main(int argc, char** argv) { |
| 254 | benchmark::Initialize(&argc, argv); |
| 255 | if (benchmark::ReportUnrecognizedArguments(argc, argv)) |
| 256 | return 1; |
| 257 | |
| 258 | const std::vector<size_t> Quantities = {1 << 0, 1 << 2, 1 << 4, 1 << 6, |
| 259 | 1 << 8, 1 << 10, 1 << 14, 1 << 18}; |
| 260 | makeCartesianProductBenchmark<Sort, AllValueTypes, AllOrders>(Quantities); |
| 261 | makeCartesianProductBenchmark<StableSort, AllValueTypes, AllOrders>( |
| 262 | Quantities); |
| 263 | makeCartesianProductBenchmark<MakeHeap, AllValueTypes, AllOrders>(Quantities); |
| 264 | makeCartesianProductBenchmark<SortHeap, AllValueTypes>(Quantities); |
| 265 | makeCartesianProductBenchmark<MakeThenSortHeap, AllValueTypes, AllOrders>( |
| 266 | Quantities); |
| 267 | makeCartesianProductBenchmark<PushHeap, AllValueTypes, AllOrders>(Quantities); |
| 268 | makeCartesianProductBenchmark<PopHeap, AllValueTypes>(Quantities); |
| 269 | benchmark::RunSpecifiedBenchmarks(); |
| 270 | } |