blob: 93383e2b9cd6a518f4beec073b284f3c9d92198c [file] [log] [blame]
#include <algorithm>
#include <cstdint>
#include <map>
#include <random>
#include <string>
#include <utility>
#include <vector>
#include "CartesianBenchmarks.h"
#include "GenerateInput.h"
#include "benchmark/benchmark.h"
#include "test_macros.h"
namespace {
enum class ValueType { Uint32, Uint64, Pair, Tuple, String };
struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 5> {
static constexpr const char* Names[] = {
"uint32", "uint64", "pair<uint32, uint32>",
"tuple<uint32, uint64, uint32>", "string"};
};
template <class V>
using Value = std::conditional_t<
V() == ValueType::Uint32, uint32_t,
std::conditional_t<
V() == ValueType::Uint64, uint64_t,
std::conditional_t<
V() == ValueType::Pair, std::pair<uint32_t, uint32_t>,
std::conditional_t<V() == ValueType::Tuple,
std::tuple<uint32_t, uint64_t, uint32_t>,
std::string> > > >;
enum class Order {
Random,
Ascending,
Descending,
SingleElement,
PipeOrgan,
Heap
};
struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 6> {
static constexpr const char* Names[] = {"Random", "Ascending",
"Descending", "SingleElement",
"PipeOrgan", "Heap"};
};
template <typename T>
void fillValues(std::vector<T>& V, size_t N, Order O) {
if (O == Order::SingleElement) {
V.resize(N, 0);
} else {
while (V.size() < N)
V.push_back(V.size());
}
}
template <typename T>
void fillValues(std::vector<std::pair<T, T> >& V, size_t N, Order O) {
if (O == Order::SingleElement) {
V.resize(N, std::make_pair(0, 0));
} else {
while (V.size() < N)
// Half of array will have the same first element.
if (V.size() % 2) {
V.push_back(std::make_pair(V.size(), V.size()));
} else {
V.push_back(std::make_pair(0, V.size()));
}
}
}
template <typename T1, typename T2, typename T3>
void fillValues(std::vector<std::tuple<T1, T2, T3> >& V, size_t N, Order O) {
if (O == Order::SingleElement) {
V.resize(N, std::make_tuple(0, 0, 0));
} else {
while (V.size() < N)
// One third of array will have the same first element.
// One third of array will have the same first element and the same second element.
switch (V.size() % 3) {
case 0:
V.push_back(std::make_tuple(V.size(), V.size(), V.size()));
break;
case 1:
V.push_back(std::make_tuple(0, V.size(), V.size()));
break;
case 2:
V.push_back(std::make_tuple(0, 0, V.size()));
break;
}
}
}
void fillValues(std::vector<std::string>& V, size_t N, Order O) {
if (O == Order::SingleElement) {
V.resize(N, getRandomString(64));
} else {
while (V.size() < N)
V.push_back(getRandomString(64));
}
}
template <class T>
void sortValues(T& V, Order O) {
assert(std::is_sorted(V.begin(), V.end()));
switch (O) {
case Order::Random: {
std::random_device R;
std::mt19937 M(R());
std::shuffle(V.begin(), V.end(), M);
break;
}
case Order::Ascending:
std::sort(V.begin(), V.end());
break;
case Order::Descending:
std::sort(V.begin(), V.end(), std::greater<>());
break;
case Order::SingleElement:
// Nothing to do
break;
case Order::PipeOrgan:
std::sort(V.begin(), V.end());
std::reverse(V.begin() + V.size() / 2, V.end());
break;
case Order::Heap:
std::make_heap(V.begin(), V.end());
break;
}
}
constexpr size_t TestSetElements =
#if !TEST_HAS_FEATURE(memory_sanitizer)
1 << 18;
#else
1 << 14;
#endif
template <class ValueType>
std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N,
Order O) {
std::vector<std::vector<Value<ValueType> > > Ret;
const size_t NumCopies = std::max(size_t{1}, TestSetElements / N);
Ret.resize(NumCopies);
for (auto& V : Ret) {
fillValues(V, N, O);
sortValues(V, O);
}
return Ret;
}
template <class T, class U>
TEST_ALWAYS_INLINE void resetCopies(benchmark::State& state, T& Copies,
U& Orig) {
state.PauseTiming();
for (auto& Copy : Copies)
Copy = Orig;
state.ResumeTiming();
}
enum class BatchSize {
CountElements,
CountBatch,
};
template <class ValueType, class F>
void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O,
BatchSize Count, F Body) {
auto Copies = makeOrderedValues<ValueType>(Quantity, O);
auto Orig = Copies;
const size_t Batch = Count == BatchSize::CountElements
? Copies.size() * Quantity
: Copies.size();
while (state.KeepRunningBatch(Batch)) {
for (auto& Copy : Copies) {
Body(Copy);
benchmark::DoNotOptimize(Copy);
}
state.PauseTiming();
Copies = Orig;
state.ResumeTiming();
}
}
template <class ValueType, class Order>
struct Sort {
size_t Quantity;
void run(benchmark::State& state) const {
runOpOnCopies<ValueType>(
state, Quantity, Order(), BatchSize::CountElements,
[](auto& Copy) { std::sort(Copy.begin(), Copy.end()); });
}
bool skip() const { return Order() == ::Order::Heap; }
std::string name() const {
return "BM_Sort" + ValueType::name() + Order::name() + "_" +
std::to_string(Quantity);
};
};
template <class ValueType, class Order>
struct StableSort {
size_t Quantity;
void run(benchmark::State& state) const {
runOpOnCopies<ValueType>(
state, Quantity, Order(), BatchSize::CountElements,
[](auto& Copy) { std::stable_sort(Copy.begin(), Copy.end()); });
}
bool skip() const { return Order() == ::Order::Heap; }
std::string name() const {
return "BM_StableSort" + ValueType::name() + Order::name() + "_" +
std::to_string(Quantity);
};
};
template <class ValueType, class Order>
struct MakeHeap {
size_t Quantity;
void run(benchmark::State& state) const {
runOpOnCopies<ValueType>(
state, Quantity, Order(), BatchSize::CountElements,
[](auto& Copy) { std::make_heap(Copy.begin(), Copy.end()); });
}
std::string name() const {
return "BM_MakeHeap" + ValueType::name() + Order::name() + "_" +
std::to_string(Quantity);
};
};
template <class ValueType>
struct SortHeap {
size_t Quantity;
void run(benchmark::State& state) const {
runOpOnCopies<ValueType>(
state, Quantity, Order::Heap, BatchSize::CountElements,
[](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); });
}
std::string name() const {
return "BM_SortHeap" + ValueType::name() + "_" + std::to_string(Quantity);
};
};
template <class ValueType, class Order>
struct MakeThenSortHeap {
size_t Quantity;
void run(benchmark::State& state) const {
runOpOnCopies<ValueType>(state, Quantity, Order(), BatchSize::CountElements,
[](auto& Copy) {
std::make_heap(Copy.begin(), Copy.end());
std::sort_heap(Copy.begin(), Copy.end());
});
}
std::string name() const {
return "BM_MakeThenSortHeap" + ValueType::name() + Order::name() + "_" +
std::to_string(Quantity);
};
};
template <class ValueType, class Order>
struct PushHeap {
size_t Quantity;
void run(benchmark::State& state) const {
runOpOnCopies<ValueType>(
state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) {
std::push_heap(Copy.begin(), I + 1);
}
});
}
bool skip() const { return Order() == ::Order::Heap; }
std::string name() const {
return "BM_PushHeap" + ValueType::name() + Order::name() + "_" +
std::to_string(Quantity);
};
};
template <class ValueType>
struct PopHeap {
size_t Quantity;
void run(benchmark::State& state) const {
runOpOnCopies<ValueType>(
state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) {
std::pop_heap(B, I);
}
});
}
std::string name() const {
return "BM_PopHeap" + ValueType::name() + "_" + std::to_string(Quantity);
};
};
} // namespace
int main(int argc, char** argv) {
benchmark::Initialize(&argc, argv);
if (benchmark::ReportUnrecognizedArguments(argc, argv))
return 1;
const std::vector<size_t> Quantities = {1 << 0, 1 << 2, 1 << 4, 1 << 6,
1 << 8, 1 << 10, 1 << 14,
// Running each benchmark in parallel consumes too much memory with MSAN
// and can lead to the test process being killed.
#if !TEST_HAS_FEATURE(memory_sanitizer)
1 << 18
#endif
};
makeCartesianProductBenchmark<Sort, AllValueTypes, AllOrders>(Quantities);
makeCartesianProductBenchmark<StableSort, AllValueTypes, AllOrders>(
Quantities);
makeCartesianProductBenchmark<MakeHeap, AllValueTypes, AllOrders>(Quantities);
makeCartesianProductBenchmark<SortHeap, AllValueTypes>(Quantities);
makeCartesianProductBenchmark<MakeThenSortHeap, AllValueTypes, AllOrders>(
Quantities);
makeCartesianProductBenchmark<PushHeap, AllValueTypes, AllOrders>(Quantities);
makeCartesianProductBenchmark<PopHeap, AllValueTypes>(Quantities);
benchmark::RunSpecifiedBenchmarks();
}