benchmarks/algorithms.bench.cpp - llvm-project/libcxx - Git at Google


 #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();
 }

	#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();
	}