Array reverse

[monarch_dodra]

On Friday, 23 November 2012 at 09:14:20 UTC, bearophile wrote:
> I've seen a difference in the performance of 
> std.algorithm.reverse applied on an array compared to home-made 
> code, so I have written a little test.
>
> Below you see the code, and the asm of the functions, compiled 
> with DMD 2.060, 32 bit (-O -release -inline).
>
> Feel free to recompile the code yourself to see if I have done 
> some mistake :-)
>
> ------------------------------
>
> import core.stdc.stdio: printf;
> import std.algorithm: reverse;
>
> void reverseArr(T)(T[] arr) {
>     for (auto x = arr.ptr, y = &arr[$ - 1]; x < y; ) {
>         auto aux = *x;
>         *x++ = *y;
>         *y-- = aux;
>     }
> }
>
> [SNIP]
>
> Bye,
> bearophile

I'm not surprised: Algorithm's reverse is written for the generic 
bidir range. It could be made faster using an approach like 
yours', and even faster using a specialized pointer 
implementation for pointers (no bounds checking when accessing 
elements).

The *1* thing I'd be curious about is what costs are 
iteration-related, and what costs are "swap" related.

In theory, swap's implementation should be reduced to what you 
have for integers.

Could you maybe also add this in your study?

void reverseArr(T)(T[] arr) {
     for (auto x = arr.ptr, y = &arr[$ - 1]; x < y; )
         swap(*x++, *y--);
}

--------
Related, the starting condition, as written: "y = &arr[$ - 1]" 
will choke on empty ranges.

I'd have suggested: "y = arr.ptr + arr.length - 1", but that will 
also choke if the arr.ptr is null. I'd say you should just add an 
empty short-circuit test int there.