binary search benchmarks

test.d

import std.range;
import std.random;
import std.stdio;

int[1000] a;

void main()
{
	foreach (ref n; a)
		n = rand()%1000;
	a.sort;
	
	auto r = assumeSorted(a[]);
	foreach (iter; 0..100_000_000)
		r.canFind(rand()%1000);
}

testc.d

import std.random;
import std.stdio;
import core.stdc.stdlib : bsearch;

int[1000] a;

extern(C)
int compareints(in void * a, in void * b)
{
	return *cast(int*)a - *cast(int*)b;
}

void main()
{
	foreach (ref n; a)
		n = rand()%1000;
	a.sort;

	foreach (iter; 0..100_000_000)
	{
		int key = rand()%1000;
		bsearch(&key, a.ptr, a.length, a[0].sizeof, &compareints);
	}
}

testm.d

import std.random;
import std.stdio;

int[1000] a;

bool bsearch(T)(T[] a, T x)
{
	int l=0, r=a.length;
	while (l+1 < r)
	{
		int m = (l+r)/2;
		int am = a[m];
		if (am == x)
			return true;
		else
		if (am > x)
			r = m;
		else
			l = m+1;
	}
	return a[0] == x;
}

void main()
{
	foreach (ref n; a)
		n = rand()%1000;
	a.sort;

	foreach (iter; 0..100_000_000)
		bsearch(a[], cast(int)(rand()%1000));
}

testm2.d

import std.random;
import std.stdio;
import std.functional;

int[1000] a;

bool bsearch(T, alias cmp = "a < b")(T[] a, T x)
{
	int l=0, r=a.length;
	while (l+1 < r)
	{
		int m = (l+r)/2;
		int am = a[m];
		if (binaryFun!(cmp)(x, am))
			r = m;
		else
			l = m;
	}
	return a[0] == x;
}

void main()
{
	foreach (ref n; a)
		n = rand()%1000;
	a.sort;

	foreach (iter; 0..100_000_000)
		bsearch(a[], cast(int)(rand()%1000));
}