Demonstration of the "Abdikeev's binary search padding effect"

gistfile1.cpp

// Demonstration of the "Abdikeev's binary search padding effect":
// increasing the binary search performance by +30%
#include <algorithm>
#include <vector>
#include <iostream>
#include <assert.h>
#include <stdlib.h>
#include <time.h>

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

template<typename T>
void test(const int n, const int disaliasingBits, const int cachelineSizeBytes)
{
	const int sz = n + (((1<<disaliasingBits)-1)*cachelineSizeBytes)/sizeof(T);
	std::vector<T> v(sz);
	srand(0);
	std::generate_n(v.begin(), n, randg<T>());
	for(int i= n; i< sz; ++i)
		v[i] = v[n-1];
	std::vector<T> vkeys(v);
	std::sort(v.begin(), v.end());
	std::vector<T> v1(v);
	std::vector<T> v2(v1);
	std::vector<T> v3(v1);

	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 clock_t tend = clock();
	std::cout << n << " " << typeid(T).name() << ": " << (double(tend-tbegin)*1000.0/CLOCKS_PER_SEC) << "ms; sum=" << sum << std::endl;
}

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

int main()
{
	const int n = 1<<20;
	test<int>(n, 0, 32);
	test<int>(n, 4, 32);
	//test<double>(n, 0, 32);
	//test<double>(n, 4, 32);
	//test<long long int>(n, 0, 32);
	//test<long long int>(n, 4, 32);
	//test<intWithPadding<4> >(n, 0, 32);
	//test<intWithPadding<4> >(n, 4, 32);
	//test<intWithPadding<8> >(n, 0, 32);
	//test<intWithPadding<8> >(n, 4, 32);
	//test<intWithPadding<16> >(n, 0, 32);
	//test<intWithPadding<16> >(n, 4, 32);
}