Ruslan's binary search padding effect demo

binary_search_speedup.cc

// Demo of the binary search padding effect ("+30% performance")
// 2008-2016 (C) Ruslan Abdikeev
//
// This is free and unencumbered software released into the public domain.
// I dedicate any and all copyright interest in this software to the
// public domain. I make this dedication for the benefit of the public at
// large and to the detriment of my heirs and successors. I intend this
// dedication to be an overt act of relinquishment in perpetuity of all
// present and future rights to this software under copyright law.

#include <algorithm>
#include <cassert>
#include <chrono>
#include <iostream>
#include <limits>
#include <random>
#include <vector>

template<typename T>
void test(const int N, const int SZ) {
	assert(N > 0);
	assert(SZ >= N);

	std::mt19937 generator(0);
	std::uniform_int_distribution<T> distribution(
		std::numeric_limits<T>::min(),
		std::numeric_limits<T>::max());
	auto random = [&](){ return distribution(generator); };

	std::vector<T> vkeys; vkeys.resize(N);
	std::generate(vkeys.begin(), vkeys.end(), random);

	std::vector<T> v(vkeys);
	std::sort(v.begin(), v.end());
	v.resize(SZ);
	std::fill(v.begin() + vkeys.size(), v.end(), v[vkeys.size() - 1]);

	auto start = std::chrono::high_resolution_clock::now();
	T sum = T();
	for(auto k : vkeys) {
		auto r = std::lower_bound(v.begin(), v.end(), k);
		assert(r != v.end());
		sum = sum + std::distance(v.begin(), r);
	}
	auto stop = std::chrono::high_resolution_clock::now();
	std::cout << (SZ == N ? "SMALLER" : "BIGGER") << "\t"
			<< std::chrono::duration_cast<std::chrono::microseconds>(stop - start).count() << "\t"
			<< SZ << "\t" << N << "\t" << sizeof(T) << "\t" << "\t" << sum << '\n';
}

int main() {
	std::cout << "Successful searches in an array of 32-bit integers:\n";
	for(int j = 0; j < 2; ++j)
		for(int i = 1; i < 5; ++i) {
			test<unsigned int>(1 << 20, (1 << 20));
			test<unsigned int>(1 << 20, (1 << 20));
			test<unsigned int>(1 << 20, (1 << 20) + i * 64);
			test<unsigned int>(1 << 20, (1 << 20) + i * 64);
		}
}

/* Output from http://ideone.com/7sUnyD
Successful searches in an array of 32-bit integers:
SMALLER	200914	1048576	1048576	4		4294442868
SMALLER	199628	1048576	1048576	4		4294442868
BIGGER	175753	1048640	1048576	4		4294442868
BIGGER	179147	1048640	1048576	4		4294442868
SMALLER	197826	1048576	1048576	4		4294442868
SMALLER	198500	1048576	1048576	4		4294442868
BIGGER	168489	1048704	1048576	4		4294442868
BIGGER	170494	1048704	1048576	4		4294442868
SMALLER	201048	1048576	1048576	4		4294442868
SMALLER	201053	1048576	1048576	4		4294442868
BIGGER	168314	1048768	1048576	4		4294442868
BIGGER	167632	1048768	1048576	4		4294442868
SMALLER	200335	1048576	1048576	4		4294442868
SMALLER	198723	1048576	1048576	4		4294442868
BIGGER	164015	1048832	1048576	4		4294442868
BIGGER	161658	1048832	1048576	4		4294442868
SMALLER	198174	1048576	1048576	4		4294442868
SMALLER	201740	1048576	1048576	4		4294442868
BIGGER	179559	1048640	1048576	4		4294442868
BIGGER	180628	1048640	1048576	4		4294442868
SMALLER	207990	1048576	1048576	4		4294442868
SMALLER	206165	1048576	1048576	4		4294442868
BIGGER	169704	1048704	1048576	4		4294442868
BIGGER	167608	1048704	1048576	4		4294442868
SMALLER	203509	1048576	1048576	4		4294442868
SMALLER	206658	1048576	1048576	4		4294442868
BIGGER	164838	1048768	1048576	4		4294442868
BIGGER	168378	1048768	1048576	4		4294442868
SMALLER	199084	1048576	1048576	4		4294442868
SMALLER	198183	1048576	1048576	4		4294442868
BIGGER	161198	1048832	1048576	4		4294442868
BIGGER	162518	1048832	1048576	4		4294442868
*/