Different array rotation algorithms benchmark

[Miguel L via Digitalmars-d-learn]

On Thursday, 1 September 2016 at 09:53:59 UTC, Miguel L wrote:
> On Thursday, 1 September 2016 at 09:36:16 UTC, Miguel L wrote:
>> 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:
>>
>> [...]
>
> Sorry Rotate4 had a bug, there was an extra for that was not 
> neccesary, this is the correct implementation:
>
> void Rotate4(T)(T[] input, long n) pure
> {
> 	/* 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 - 3 -
> 	 * 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)
> 	{
> 		tmp=input[b];
> 		input[b]=input[a];
> 		input[a]=tmp;
> 		++a;
> 		++b;
> 		if(b>=input.length)
> 			{
> 			b=input.length-n;
> 			}
> 	}
>
> }

Very sorry again: Rotate4 was not correct with negative offsets.
This implementation works correctly:

void Rotar4(T)(T[] input, long n) pure
{
	/* 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 - -2 -
	 * 1,8,3,4,5,6,7,2 - a=7 b=1
	 * 7,8,3,4,5,6,1,2 - a=6 b=0
	 * 7,6,3,4,5,8,1,2 - a=5 b=1
	 * 5,6,3,4,7,8,3,4 - a=4 b=0
	 * 3,6,5,4,7,8,1,2 - a=3 b=1
	 * 3,4,5,6,7,8,1,2 - a=2 b=0

--------------------
        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
	 */
	long a,b;
	T tmp;

	if(n>0)
	{
		a=0;
		b=input.length-n;		
		
		while(a<input.length-n)
		{
			tmp=input[b];
			input[b]=input[a];
			input[a]=tmp;
			++a;
			++b;
			if(b>=input.length)
				b=input.length-n;
		}
	}
	else
	{
		a=input.length-1;
		long b0=-n-1;
		b=b0;		
		
		while(a>=-n)
		{
			tmp=input[b];
			input[b]=input[a];
			input[a]=tmp;
			--a;
			--b;
			if(b<0)
				b=b0;
		}
	}	

}

Also, forgot to specify I am using LDC with -05.
Updated benchmark results:

Rotate0: 0.344186s
Rotate1: 1.76369s
Rotate2: 0.169968s
Rotate3: 0.354091s
Rotate4: 0.156231s