Binary search with padding, or how to get +30% in performance

bs-padded.cpp

// Demonstration of the "Abdikeev's binary search padding effect":
// increasing the binary search performance by +30%
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <ctime>

template<typename T>
struct randg
{
	T operator()() const { return T((::rand()<<16)|(::rand())); }
};

template<typename T>
T test(const int n, const int disaliasingBits, const int cachelineSizeBytes)
{
	const int sz = n | (((1<<disaliasingBits)-1)*cachelineSizeBytes)/sizeof(T);
	std::vector<T> v; v.reserve(sz); v.resize(n);
	::srand(0);
	std::generate_n(v.begin(), n, randg<T>());
	std::vector<T> vkeys(v);

	std::sort(v.begin(), v.end());
	for(int i= n; i< sz; ++i)
		v.push_back( v[n-1] );

	T sum = T();
	const clock_t tbegin = clock();
	for(int i= 0; i< n; ++i)
	{
		typename std::vector<T>::iterator r = std::lower_bound(v.begin(), v.end(), vkeys[i]);
		assert(r != v.end());
		sum = sum + *r;
	}
	const double tend = clock();
	const double spent = (double(tend-tbegin))*1000.0/double(CLOCKS_PER_SEC);
	std::cout << n << " " << typeid(T).name() << ": " << spent << "ms; sum=" << sum << std::endl;
	return sum;
}

template<int SIZE>
struct intWithPadding
{
	int padding[SIZE];
	intWithPadding() { padding[0] = 0; }
	explicit intWithPadding(int key) { padding[0]= key; }
	intWithPadding& operator=(const intWithPadding& v) { padding[0] = v.padding[0]; return *this; }
	friend bool operator<(const intWithPadding& a, const intWithPadding& b) { return a.padding[0] < b.padding[0]; }
	friend intWithPadding operator+(const intWithPadding& a, const intWithPadding& b) { return intWithPadding(a.padding[0] + b.padding[0]); }
	friend std::ostream& operator<<(std::ostream& os, const intWithPadding& v) { return os << v.padding[0]; }
};

int main()
{
	test<int>(1<<20, 0, 1<<5);
	test<int>(1<<20, 8, 1<<5);
	test<long long int>(1<<20, 0, 1<<5);
	test<long long int>(1<<20, 8, 1<<5);
	test<double>(1<<20, 0, 1<<5);
	test<double>(1<<20, 8, 1<<5);
	test<intWithPadding<16> >(1<<20, 0, 1<<5);
	test<intWithPadding<16> >(1<<20, 8, 1<<5);
}