View mode: basic / threaded / horizontal-split · Log in · Help
November 23, 2012
Array reverse
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
November 23, 2012
Re: Array reverse
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.
November 23, 2012
Re: Array reverse
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.
November 28, 2012
Re: Array reverse
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
November 28, 2012
Re: Array reverse
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
November 28, 2012
Re: Array reverse
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
Top | Discussion index | About this forum | D home