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.
