## digitalmars.D.learn - Different array rotation algorithms benchmark

• Miguel L (158/158) Sep 01 2016 Hi
• Miguel L (38/43) Sep 01 2016 Sorry Rotate4 had a bug, there was an extra for that was not
• Miguel L (72/118) Sep 01 2016 Very sorry again: Rotate4 was not correct with negative offsets.
• Johan Engelen (2/4) Sep 01 2016 And the version of LDC too please ;-)
• Miguel L (3/7) Sep 01 2016 LDC version is: ldc2-1.1.0-beta2-win64-msvc
Miguel L <mlabayru gmail.com> writes:
```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");

}
```
Sep 01 2016
Miguel L <mlabayru gmail.com> writes:
```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;
}
}

}
```
Sep 01 2016
Miguel L <mlabayru gmail.com> writes:
```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
```
Sep 01 2016
Johan Engelen <j j.nl> writes:
```On Thursday, 1 September 2016 at 10:37:18 UTC, Miguel L wrote:

Also, forgot to specify I am using LDC with -05.

And the version of LDC too please ;-)
```
Sep 01 2016
Miguel L <mlabayru gmail.com> writes:
```On Thursday, 1 September 2016 at 13:16:19 UTC, Johan Engelen
wrote:
On Thursday, 1 September 2016 at 10:37:18 UTC, Miguel L wrote:

Also, forgot to specify I am using LDC with -05.

And the version of LDC too please ;-)

LDC version is: ldc2-1.1.0-beta2-win64-msvc
```
Sep 01 2016