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;
    }
}

void main() {
    auto a = [10, 20, 30, 40];
    foreach(x; a) printf("%d ", x); printf("\n");
    a.reverseArr();
    foreach(x; a) printf("%d ", x); printf("\n");
    a.reverse();
    foreach(x; a) printf("%d ", x); printf("\n");
}

------------------------------

reverseArr:
		push	EBX
		mov	ECX,0Ch[ESP]
		mov	EBX,0Ch[ESP]
		push	ESI
		mov	ESI,0Ch[ESP]
		lea	ESI,-4[ESI*4][ECX]
		cmp	ECX,ESI
		jae	L2B
L19:	mov	EAX,[EBX]
		mov	EDX,[ESI]
		mov	[EBX],EDX
		add	EBX,4
		mov	[ESI],EAX
		add	ESI,0FFFFFFFCh
		cmp	EBX,ESI
		jb	L19
L2B:	pop	ESI
		pop	EBX
		ret	8

-------------------

std.algorithm.reverse:
L0:		sub	ESP,020h
		push	EBX
		push	ESI
		push	EDI
		cmp	dword ptr 030h[ESP],0
		je	LE1
L11:	cmp	dword ptr 030h[ESP],0
		mov	EAX,030h[ESP]
		mov	EDX,034h[ESP]
		mov	018h[ESP],EAX
		mov	01Ch[ESP],EDX
		jne	L32
		mov	EAX,022Dh
		call	near ptr _D3std9algorithm7__arrayZ
L32:	mov	EAX,030h[ESP]
		mov	EDX,034h[ESP]
		mov	024h[ESP],EDX
		mov	ECX,030h[ESP]
		lea	EDX,-1[ECX]
		mov	020h[ESP],EAX
		cmp	EDX,ECX
		mov	010h[ESP],EDX
		jb	L5E
		mov	EAX,0258h
		call	near ptr _D3std9algorithm7__arrayZ
L5E:	mov	ECX,01Ch[ESP]
		mov	EBX,030h[ESP]
		mov	EDX,024h[ESP]
		lea	EBX,-4[EBX*4][EDX]
		mov	ESI,[ECX]
		mov	EDX,[EBX]
		mov	[ECX],EDX
		mov	ECX,030h[ESP]
		cmp	ECX,ECX
		mov	[EBX],ESI
		ja	L86
		cmp	ECX,1
		jae	L90
L86:	mov	EAX,0173h
		call	near ptr _D3std9algorithm7__arrayZ
L90:	mov	EDX,034h[ESP]
		mov	EDI,010h[ESP]
		mov	030h[ESP],EDI
		add	EDX,4
		mov	034h[ESP],EDX
		cmp	dword ptr 030h[ESP],0
		je	LE1
		mov	EBX,030h[ESP]
		lea	ECX,-1[EBX]
		cmp	ECX,EBX
		mov	014h[ESP],ECX
		jbe	LC6
		mov	EAX,01E8h
		call	near ptr _D3std9algorithm7__arrayZ
LC6:	mov	ESI,014h[ESP]
		mov	EDX,034h[ESP]
		mov	030h[ESP],ESI
		mov	034h[ESP],EDX
		cmp	dword ptr 030h[ESP],0
		jne	L11
LE1:	pop	EDI
		pop	ESI
		pop	EBX
		add	ESP,020h
		ret	8

------------------------------

Bye,
bearophile

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.

On 11/23/2012 1:14 AM, bearophile wrote:
> Feel free to recompile the code yourself to see if I have done some mistake :-)

You've got array bounds checking turned on for algorithm.reverse, and you avoided that in your code by using unchecked pointers.

Walter Bright:

Sorry for the late reply.

> You've got array bounds checking turned on for algorithm.reverse, and you avoided that in your code by using unchecked pointers.

Right, sorry. This is compiled with the latest DMD 2.061alpha with -O -release -inline -noboundscheck. I have used the same program source code as above.

Now the calls inside std.algorithm.reverse are fully inlined, below there are no "call" istrunctions.

But the number of instructions performed in the loop is rather different.

dpaste is currently down and I don't have gdc2/dc2 installed here, so I can't show the asm from those other compilers.

I have also done benchmarks, and I have seen performance difference in real code between std.algorithm.reverse and a reverseArr function.


reverseArr:
        push EBX
        mov ECX, 0Ch[ESP]
        mov EBX, 0Ch[ESP]
        push ESI
        mov ESI, 0Ch[ESP]
        lea ESI, -4[ESI*4][ECX]
        cmp ECX, ESI
        jae L2B
L19:    mov EAX, [EBX]
        mov EDX, [ESI]
        mov [EBX], EDX
        add EBX, 4
        mov [ESI], EAX
        add ESI, 0FFFFFFFCh
        cmp EBX, ESI
        jb  L19
L2B:    pop ESI
        pop EBX
        ret 8


std.algorithm.reverse:
        sub ESP, 014h
        push EBX
        push ESI
        cmp dword ptr 020h[ESP], 0
        je  L76
LC:     mov EAX, 020h[ESP]
        mov EDX, 024h[ESP]
        mov EBX, 020h[ESP]
        mov 0Ch[ESP], EDX
        mov ECX, 0Ch[ESP]
        mov ESI, [ECX]
        mov 014h[ESP], EDX
        mov EDX, 014h[ESP]
        lea EBX, -4[EBX*4][EDX]
        mov 8[ESP], EAX
        mov EDX, [EBX]
        mov [ECX], EDX
        mov ECX, 020h[ESP]
        mov EDX, 024h[ESP]
        mov 010h[ESP], EAX
        lea EAX, -1[ECX]
        add EDX, 4
        mov 020h[ESP], EAX
        mov [EBX], ESI
        mov 024h[ESP], EDX
        cmp dword ptr 020h[ESP], 0
        je  L76
        mov EBX, 020h[ESP]
        lea ESI, -1[EBX]
        mov ECX, 024h[ESP]
        mov 020h[ESP], ESI
        mov 024h[ESP], ECX
        cmp dword ptr 020h[ESP], 0
        jne LC
L76:    pop ESI
        pop EBX
        add ESP, 014h
        ret 8

Bye,
bearophile

monarch_dodra:

> 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--);
> }


This is the full program:

import core.stdc.stdio: printf;
import std.algorithm: reverse, swap;

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

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

void main() {
    auto a = [10, 20, 30, 40];
    foreach(x; a) printf("%d ", x); printf("\n");
    a.reverseArr();
    foreach(x; a) printf("%d ", x); printf("\n");
    a.reverse();
    foreach(x; a) printf("%d ", x); printf("\n");
    a.reverseArray();
    foreach(x; a) printf("%d ", x); printf("\n");
}


And this is the asm of the reverseArray:

reverseArray:
        push EBX
        mov ECX, 0Ch[ESP]
        mov EBX, 0Ch[ESP]
        push ESI
        mov ESI, 0Ch[ESP]
        lea ESI, -4[ESI*4][ECX]
        push EDI
        cmp ECX, ESI
        jae L30
L1A:    mov EAX, EBX
        mov EDI, ESI
        mov EDX, [EAX]
        mov ECX, [EDI]
        add EBX, 4
        sub ESI, 4
        mov [EAX], ECX
        cmp EBX, ESI
        mov [EDI], EDX
        jb  L1A
L30:    pop EDI
        pop ESI
        pop EBX
        ret 8


So the inner loop is 10 asm instructions instead of the 8 asm instructions of the loop of reverseArr(), that is 2 more register swaps, that are performed very quickly by the hardware register renaming in the modern CPUs. So this is a small difference, probably acceptable in many situations. While the difference between the performance of reverseArray() and std.algorithm.reverse is significant.


> 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.

Right. But my study was mostly about what's inside the loop of those functions. What's outside the loop is not influencing performance significantly.

Bye,
bearophile

On Wednesday, 28 November 2012 at 00:19:33 UTC, bearophile wrote:
> dpaste is currently down and I don't have gdc2/dc2 installed here, so I can't show the asm from those other compilers.

fwiw, here is what LDC produces:

---
_D4test18__T10reverseArrTiZ10reverseArrFAiZv:
	lea	RAX, QWORD PTR [RSI + 4*RDI - 4]
	cmp	RSI, RAX
	jae	.LBB1_3
	lea	RAX, QWORD PTR [RSI + 4*RDI - 8]
	.align	16, 0x90
.LBB1_2:
	mov	ECX, DWORD PTR [RSI]
	mov	EDX, DWORD PTR [RAX + 4]
	mov	DWORD PTR [RSI], EDX
	mov	DWORD PTR [RAX + 4], ECX
	add	RSI, 4
	cmp	RSI, RAX
	lea	RAX, QWORD PTR [RAX - 4]
	jb	.LBB1_2
.LBB1_3:
	ret
---

---
_D3std9algorithm15__T7reverseTAiZ7reverseFAiZv:
	test	RDI, RDI
	je	.LBB2_4
	lea	RAX, QWORD PTR [RSI + 4*RDI - 4]
	.align	16, 0x90
.LBB2_2:
	mov	ECX, DWORD PTR [RSI]
	mov	EDX, DWORD PTR [RAX]
	mov	DWORD PTR [RSI], EDX
	mov	DWORD PTR [RAX], ECX
	cmp	RDI, 1
	je	.LBB2_4
	add	RAX, -4
	add	RSI, 4
	add	RDI, -2
	jne	.LBB2_2
.LBB2_4:
	ret
---

---
_D4test20__T12reverseArrayTiZ12reverseArrayFAiZv:
	lea	RAX, QWORD PTR [RSI + 4*RDI - 4]
	cmp	RSI, RAX
	jae	.LBB3_3
	add	RSI, 4
	.align	16, 0x90
.LBB3_2:
	mov	ECX, DWORD PTR [RSI - 4]
	mov	EDX, DWORD PTR [RAX]
	mov	DWORD PTR [RSI - 4], EDX
	mov	DWORD PTR [RAX], ECX
	add	RAX, -4
	cmp	RSI, RAX
	lea	RSI, QWORD PTR [RSI + 4]
	jb	.LBB3_2
.LBB3_3:
	ret
---

The extra jump in the std.algorithm version is still there – I haven't checked whether it would be feasible to optimize the induction variable away entirely.

David