rayhamel
11/10/2017 - 3:21 PM

Sorting Benchmarker

Sorting Benchmarker

#include <algorithm>
#include <array>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <random>

#if !defined(__GNUC__) && !defined(__attribute__)
#define __attribute__(A)
#endif//__GNUC__,__attribute__

// algorithm
using std::copy_n;
using std::generate;
using std::is_sorted;
using std::min;
using std::shuffle;
using std::sort;
// array
using std::array;
// chrono
using std::chrono::duration_cast;
using std::chrono::high_resolution_clock;
using std::chrono::nanoseconds;
// cstddef
using std::size_t;
// cstdint
using std::uintmax_t;
// iostream
using std::boolalpha;
using std::cout;
using std::ios;
// iterator
using std::ostream_iterator;
// random
using std::mt19937;
using std::random_device;

namespace {

auto rng = mt19937(random_device()());

using RandomValue = decltype(rng());

constexpr size_t ArraySize = 0x80000 / sizeof(RandomValue); // 512 KB

class BenchmarkArray : public array<RandomValue, ArraySize> {
	void reshuffle() {shuffle(begin(), end(), rng);}

	// Forces the compiler to sort the entire array, & heats the cache.
	void sideeffect() const noexcept
	{
		for (__attribute__((unused)) volatile const auto n : *this) {}
	}
public:
	BenchmarkArray() {generate(begin(), end(), rng);}

	template<typename Sorter=void(iterator, iterator)>
	void sort_benchmark(
		const char name[]="std::sort",
		Sorter &&sorter=sort<iterator>)
	{
		static ostream_iterator<value_type> oi(cout, "\n\t");
		static const auto nprint = min<size_type>(ArraySize / 2, 5);

		cout << "Benchmarking " << name << "\n\t"
			"BEFORE SORT\n\t";
		copy_n(cbegin(), nprint, oi);
		cout << "...\n\t";
		copy_n(cend() - nprint, nprint, oi);

		sideeffect();

		const auto start = high_resolution_clock::now();

		sorter(begin(), end());

		const auto finish = high_resolution_clock::now();
		const auto time_elapsed = uintmax_t(
			duration_cast<nanoseconds>(finish - start).count()
		);

		sideeffect();

		cout << "\n\t"
			"AFTER SORT\n\t";
		copy_n(cbegin(), nprint, oi);
		cout << "...\n\t";
		copy_n(cend() - nprint, nprint, oi);
		cout << "\n\t"
			"Is sorted?\t" << is_sorted(cbegin(), cend()) << "\n\t"
			"Total time\t" << time_elapsed << " ns\n\n";

		reshuffle();
	}
};

}//anonymous namespace
int main()
{
	// `cout` normally acquires a mutex every time you print to it, which
	// risks the OS scheduler preempting this process with another once it
	// releases the mutex, which could throw off the benchmark.
	// `ios::sync_with_stdio(false)` prevents this.
	ios::sync_with_stdio(false);
	cout << boolalpha;
	BenchmarkArray ba;
	for (int i = 0; i < 5; ++i)
		ba.sort_benchmark();
}