Different array rotation algorithms benchmark

[Miguel L via Digitalmars-d-learn]

Hi

I recently needed a very optimized array rotation algorithm, so I 
did this benchmark, hope you find it interesting. I am a bit 
surprised by the poor results of std.algorithm.bringToFront:

These are the different algorithms:


void Rotate0(T)(T[] input, int n) pure
{
	if(n>0)input=input[($-n)..$]~input[0..($-n)];
	if(n<0)input=input[(-n)..$]~input[0..(-n)];
}

void Rotate(T)(T[] input, int n) pure
{
	if(n>0) 
std.algorithm.bringToFront(input[0..($-n)],input[($-n)..$]);
	else if(n<0) 
std.algorithm.bringToFront(input[0..(-n)],input[(-n)..$]);
}

  void reverse(T)(T[] a, long sz) pure {
     long i, j;
     for (i = 0, j = sz; i < j; ++i, --j) {
         T tmp = a[i];
         a[i] = a[j];
         a[j] = tmp;
     }
}

void Rotate2(T)(T[] array, long amt) pure  {
/*
the algorithm from Jon Bentley's book, "Programming Pearls 2nd 
Edition"
O(n) time and no extra memory usage (since array was specified),
*/
     if (amt < 0)
         amt = array.length + amt;
     reverse(array, array.length-amt-1);
     reverse(array[array.length-amt..$], amt-1);
     reverse(array, array.length-1);
}


void Rotate3(T)(T[] input, long n) pure
{
	if(n<0)
		n=input.length+n;

	auto tmp=input[($-n)..$].dup;
	for(auto j=input.length-1;j>=n;--j)
		input[j]=input[j-n];
	input[0..n]=tmp;
}



void Rotate4(T)(T[] input, long n) pure
//No extra memory, just swapping of elements
{
	/* 1,2,3,4,5,6,7,8 - 2 -
	 * 7,2,3,4,5,6,1,8 - a=0 b=8-2=6
	 * 7,8,3,4,5,6,1,2 - a=1 b=7
  	 * 7,8,1,4,5,6,3,2 - a=2 b=6
	 * 7,8,1,2,5,6,3,4 - a=3 b=7
	 * 7,8,1,2,3,6,5,4 - a=4 b=6
	 * 7,8,1,2,3,4,5,6 - a=5 b=7
--------------------
        1,2,3,4,5,6,7,8,9 - 2 -
	 * 7,2,3,4,5,6,1,8,9 - a=0 b=9-3=6
	 * 7,8,3,4,5,6,1,2,9 - a=1 b=7
	 * 7,8,9,4,5,6,1,2,3 - a=2 b=8
	 * 7,8,9,1,5,6,4,2,3 - a=3 b=6
	 * 7,8,9,1,2,6,4,5,3 - a=4 b=7
	 * 7,8,9,1,2,3,4,5,6 - a=5 b=8
	 */

	if(n<0)
		n=input.length+n;

	long a=0,b=input.length-n;
	T tmp;

	while(a<input.length-n-1)
	for(auto k=0;k<input.length-n;k++)
	{
		tmp=input[b];
		input[b]=input[a];
		input[a]=tmp;
		++a;
		++b;
		if(b>=input.length)
			{
			b=input.length-n;
			}
	}

}

This is the times I got for 4000000 iterations of each  rotating 
an array of 29 elements 2 positions(2000000 iterations to the 
left, and 2000000 iterations to the right).

Rotate0: 0.300493s
Rotate1: 1.60528s
Rotate2: 0.145162s
Rotate3: 0.337595s
Rotate4: 0.0853269s



This is the test/benchmark function code, sorry for the long 
asserts.

void RotateBenchmark()
{
	int[] 
a=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30];

	Rotate0(a,2);
	assert(a==[29,30,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28]);
	Rotate0(a,-2);
	assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);

	Rotate1(a,2);
	assert(a==[29,30,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28]);
	Rotate1(a,-2);
	assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);

	Rotate2(a,2);
	assert(a==[29,30,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28]);
	Rotate2(a,-2);
	assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);

	Rotate3(a,2);
	assert(a==[29,30,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28]);
	Rotate3(a,-2);
	assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);

	Rotate4(a,2);
	assert(a==[29,30,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28]);
	Rotate4(a,-2);
	assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);

	auto init1 = TickDuration.currSystemTick();
	for(auto i=0;i<2000000;++i)
		Rotate0(a,2);
	for(auto i=0;i<2000000;++i)
		Rotate0(a,-2);
	assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
	writeln("Rotate0: ",(TickDuration.currSystemTick() - 
init1).to!("seconds",float),"s");

	init1 = TickDuration.currSystemTick();
	for(auto i=0;i<2000000;++i)
		Rotate1(a,2);
	for(auto i=0;i<2000000;++i)
		Rotate1(a,-2);
	assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
	writeln("Rotate1: ",(TickDuration.currSystemTick() - 
init1).to!("seconds",float),"s");

	init1 = TickDuration.currSystemTick();
	for(auto i=0;i<2000000;++i)
		Rotate2(a,2);
	for(auto i=0;i<2000000;++i)
		Rotate2(a,-2);
	assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
	writeln("Rotate2: ",(TickDuration.currSystemTick() - 
init1).to!("seconds",float),"s");


	init1 = TickDuration.currSystemTick();
	for(auto i=0;i<2000000;++i)
		Rotate3(a,2);
	for(auto i=0;i<2000000;++i)
		Rotate3(a,-2);
	assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
	writeln("Rotate3: ",(TickDuration.currSystemTick() - 
init1).to!("seconds",float),"s");


	init1 = TickDuration.currSystemTick();
	for(auto i=0;i<2000000;++i)
		Rotate4(a,2);
	for(auto i=0;i<2000000;++i)
		Rotate4(a,-2);
	assert(a==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
	writeln("Rotate4: ",(TickDuration.currSystemTick() - 
init1).to!("seconds",float),"s");

}