concurrency for bisectable data structures

biconc.d

struct gray
{
    size_t shifter;
	immutable(size_t)[] basis;
	size_t count;
	invariant ()
	{
		assert (basis.length < size_t.sizeof << 3);
	}
	@property bool empty()
	{
		return 1 << basis.length <= count;
	}
	size_t front()
	{
		size_t ret;// = shifter;
		foreach (i, b; basis)
			if (count & (1 << i))
				ret ^= b;
		return ret ^ shifter;
	}
	void popFront()
	{
		assert (!empty);
		++count;
	}
	@property bool bisectable()
	{
		return 10 < basis.length;
	}
	gray[2] bisect()
	{
		return [
			gray(shifter, basis[1..$]),
			gray(shifter ^ basis[0], basis[1..$])];
	}
}


auto average(alias f)(gray P)
{
	import std.traits;
	double ret = 0;
	foreach (x; P)
	{
		ret += f(x);
	}
	foreach (i; 0..(P.basis.length))
	{
		ret *= 0.5;
	}
	return ret;
}

double biaverage(alias f)(gray P)
{
	import std.traits;
	import std.concurrency;
	alias biaverage!f biaveragef;
	if (P.bisectable)
	{
		auto Q = P.bisect();
		return (biaveragef(Q[0]) + biaveragef(Q[1])) * 0.5; // implementation point
	}
	return P.average!f();
}

version (all)
{	import std.concurrency;
	import std.stdio;
void coaverager(alias f)(Tid tid)
{
	auto P = receiveOnly!gray();
//	"hello coaverager with shifter %d".writefln(P.shifter);
	tid.send(coaverage!f(P));
}

double coaverage(alias f)(gray P)
{
	import std.traits;
	alias coaverage!f coaveragef;
	if (P.bisectable)
	{
//		"hello coaverage with shifter %d".writefln(P.shifter);
		auto Q = P.bisect();
		auto another = spawn(&(coaverager!f), thisTid);
		another.send(Q[1]);
		auto ret = coaveragef(Q[0]);
		ret += receiveOnly!double();
		return ret * 0.5; // implementation point
	}
	return P.average!f();
}
}

double id(size_t x)
{
	return x;
}

import std.stdio;
void main()
{
	import std.datetime;
	auto P = gray(0, [
		1, 2, 4, 8, 16, 32, 64, 128,
		256, 512, 1024, 2048,
		4096, 8192, 16384, 32768
	]);
	StopWatch sw;
	sw.start();
	double normal_result = P.average!id();
	auto normal_time = sw.peek().msecs;
	double bisect_result = P.biaverage!id();
	auto bisect_time = sw.peek().msecs - normal_time;
	auto biconc_result = P.coaverage!id();
	auto biconc_time = sw.peek().msecs - bisect_time;

	"%s: %s [ms] result %s".writefln("normal", normal_time, normal_result);
	"%s: %s [ms] result %s".writefln("bisect", bisect_time, bisect_result);
	"%s: %s [ms] result %s".writefln("biconc", biconc_time, biconc_result);
}

normal: 29 [ms] result 32767.5
bisect: 23 [ms] result 32767.5
biconc: 62 [ms] result 32767.5