MinMax aus Int32Array so schnell wie möglich ermitteln

07/07/2008 - 21:47 von Hubert Seidel | Report spam
Hallo allerseits,

nun frag ich doch mal die echten Profis:
seit ein paar Tagen suchern wir eine sehr schnelle Möglichkeit
Minimum und Maximun in teine Integer-Array (32Bit-Ints) zu suchen.
news:xn0fscgvig4ilqm01unewsgroups@rvelthuis.de
"I need the fastest routine" in "borland.public.delphi.language.basm"

Sehr spannende Angelegenheit...

Das Array, sagen wir mal einmal mit 4096, 50000 und 10Mio. Int32-Werte
mal komplet mit 0 gefüllt, mal aufsteigend 0,1,2,..., mal absteigend
0,-1,-2,-...
und mal mit Zufallszahlen gefüllt sollte möglichst schnell sein.
(Multi-Threading ist auch schon im Hinterkopf, habe aber nur ne Single-Cpu)

Das ganze sollte schàter mit Delphi laufen (ok, ich portiere ggf ;-)

Meine bisherige beste Lösung sieht wie folgt aus
(bereits ca. 7x schneller als das Original :-):

procedure MinMaxArray(const aArray:array of integer; out aMax,
aMin:integer);
asm // in the hope to use a little bit better U- and V-pipeline //
push ebx
push esi
push edi
push ecx
push ebp

mov ebx, [eax]
mov edi, ebx

inc edx
test edx, edx
jle @@Output

mov ebp, edx // ebp := edx mod 4
and ebp, 7
shr edx, 3 // edx := edx div 4

test edx, edx
jle @@RestMod4

mov esi, [eax]
@@LpMainBegin:
mov ecx, [eax+4]
cmp esi, edi
db $0F,$4C,$FE { cmovl edi, esi }
cmp ebx, esi
db $0F,$4C,$DE { cmovl ebx, esi }

mov esi, [eax+8]
cmp ecx, edi
db $0F,$4C,$F9 { cmovl edi, ecx }
cmp ebx, ecx
db $0F,$4C,$D9 { cmovl ebx, ecx }

mov ecx, [eax+12]
cmp esi, edi
db $0F,$4C,$FE { cmovl edi, esi }
cmp ebx, esi
db $0F,$4C,$DE { cmovl ebx, esi }

mov esi, [eax+16]
cmp ecx, edi
db $0F,$4C,$F9 { cmovl edi, ecx }
cmp ebx, ecx
db $0F,$4C,$D9 { cmovl ebx, ecx }

mov ecx, [eax+20]
cmp esi, edi
db $0F,$4C,$FE { cmovl edi, esi }
cmp ebx, esi
db $0F,$4C,$DE { cmovl ebx, esi }

mov esi, [eax+24]
cmp ecx, edi
db $0F,$4C,$F9 { cmovl edi, ecx }
cmp ebx, ecx
db $0F,$4C,$D9 { cmovl ebx, ecx }

mov ecx, [eax+28]
add eax, 32
cmp esi, edi
db $0F,$4C,$FE { cmovl edi, esi }
cmp ebx, esi
db $0F,$4C,$DE { cmovl ebx, esi }

mov esi, [eax]
cmp ecx, edi
db $0F,$4C,$F9 { cmovl edi, ecx }
cmp ebx, ecx
db $0F,$4C,$D9 { cmovl ebx, ecx }

@@LpMainEnd:
dec edx
jnz @@LpMainBegin

@@RestMod4:

test ebp, ebp
jle @@Output

@@LpRestBegin:
mov esi, [eax]
cmp esi, edi
db $0F,$4C,$FE { cmovl edi, esi }
cmp ebx, esi
db $0F,$4C,$DE { cmovl ebx, esi }

@@LpRestEnd:
add eax, 4
dec ebp
jnz @@LpRestBegin

@@Output:
pop ebp
pop ecx

mov eax, [ebp+$08]
mov [ecx], ebx // Output aMin //
mov [eax], edi // Output aMax //

pop edi
pop esi
pop ebx
end;

Ich kann mich waage daran erinnern das es doch z.b. beim Umkopieren
vom Speicher ein Trick mit dem Cache gab... wenn ich mich nicht ire.
Hat jemand eine coole Idee wie man das noch schneller hinbekommt?

mfg.
Herby

P.S:
Kein Crossposting da Engisch/Deutsch

http://www.hubert-seidel.de
 

Lesen sie die antworten

#1 Jan Seiffert
08/07/2008 - 23:51 | Warnen spam
Hubert Seidel wrote:
Hallo allerseits,

nun frag ich doch mal die echten Profis:
seit ein paar Tagen suchern wir eine sehr schnelle Möglichkeit
Minimum und Maximun in teine Integer-Array (32Bit-Ints) zu suchen.
news:
"I need the fastest routine" in "borland.public.delphi.language.basm"

Sehr spannende Angelegenheit...




Ist SSE2 erlaubt? (Mit MMX muesste es auch gehen)

Das Array, sagen wir mal einmal mit 4096, 50000 und 10Mio. Int32-Werte
mal komplet mit 0 gefüllt, mal aufsteigend 0,1,2,..., mal absteigend
0,-1,-2,-...
und mal mit Zufallszahlen gefüllt sollte möglichst schnell sein.
(Multi-Threading ist auch schon im Hinterkopf, habe aber nur ne Single-Cpu)




Multithreading eher ab groesseren Arrays (>>50000), sonst ist der
Overhead IMHO zu gross (auch wenn uns die Juenger von OpenMP was andres
sagen wollen, nagut kann sein, die fuddeln da ja mit "fiesen Tricks"...)

Das ganze sollte schàter mit Delphi laufen (ok, ich portiere ggf ;-)




Gut .-)

Meine bisherige beste Lösung sieht wie folgt aus
(bereits ca. 7x schneller als das Original :-):


[snip]

Ich gebe zu, ich habe geschummelt, und den Compiler die "Drecksarbeit"
machen lassen (dafuer werde ich jetzt hier sicher gesteinigt :-( ):

in den gcc schmeissen mit "-O3 -msse2"

%<
#include <stdlib.h>

struct ret
{
int min, max;
};

typedef unsigned long long v2di __attribute__((vector_size (16)));
typedef int v4si __attribute__((vector_size (16)));

void minmax(int data[], size_t len, struct ret *ret_val)
{
v4si *work = (v4si *)data;
v4si mmin, mmax;
union vec
{
v4si v;
int i[4];
} x;
int min, max;
size_t i;

mmin = mmax = work[0];

for(i = 1; i < len/4; i++)
{
register v4si rmin, rmax, wdata = work[i];
rmax = __builtin_ia32_pcmpgtd128(mmax, wdata);
mmax = __builtin_ia32_pand128(rmax, mmax);
rmax = __builtin_ia32_pandn128(rmax, wdata);
mmax = __builtin_ia32_por128(rmax, mmax);

rmin = __builtin_ia32_pcmpgtd128(wdata, mmin);
mmin = __builtin_ia32_pand128(rmin, mmin);
rmin = __builtin_ia32_pandn128(rmin, wdata);
mmin = __builtin_ia32_por128(rmin, mmin);
}

x.v = mmin;
min = x.i[0] < x.i[1] ? x.i[0] : x.i[1];
min = min < x.i[2] ? min : x.i[2];
min = min < x.i[3] ? min : x.i[3];
x.v = mmax;
max = x.i[0] > x.i[1] ? x.i[0] : x.i[1];
max = max > x.i[2] ? max : x.i[2];
max = max > x.i[3] ? max : x.i[3];

for(i *= 4; i < len; i++)
{
int d = data[i];
min = min < d ? min : d;
max = max > d ? max : d;
}
ret_val->min = min;
ret_val->max = max;
}
%



gibt sowas (Achtung, gas syntax, also "verkehrt herum"):
%<
.text
.p2align 4,,15
.globl minmax
.type minmax, @function
minmax:
pushl %ebp
movl %esp, %ebp
pushl %edi
movl $4, %edi
pushl %esi
pushl %ebx
subl $28, %esp
movl 8(%ebp), %ebx
movl 12(%ebp), %ecx
movdqa (%ebx), %xmm4
shrl $2, %ecx
cmpl $1, %ecx
movdqa %xmm4, %xmm3
jbe .L4
leal 16(%ebx), %eax
movl $1, %edx
.p2align 4,,7
.L5:
movdqa (%eax), %xmm1
incl %edx
movdqa %xmm4, %xmm0
addl $16, %eax
cmpl %edx, %ecx
pcmpgtd %xmm1, %xmm0
movdqa %xmm0, %xmm2
pandn %xmm1, %xmm0
pand %xmm4, %xmm2
por %xmm2, %xmm0
movdqa %xmm0, %xmm4
movdqa %xmm1, %xmm0
pcmpgtd %xmm3, %xmm0
movdqa %xmm0, %xmm2
pandn %xmm1, %xmm0
pand %xmm3, %xmm2
por %xmm2, %xmm0
movdqa %xmm0, %xmm3
jne .L5
leal 0(,%ecx,4), %edi
.L4:
movaps %xmm3, -40(%ebp)
movl -40(%ebp), %edx
cmpl %edx, -36(%ebp)
cmovle -36(%ebp), %edx
movl -28(%ebp), %eax
cmpl %eax, -32(%ebp)
cmovle -32(%ebp), %eax
movaps %xmm4, -40(%ebp)
cmpl %eax, %edx
movl %eax, %esi
cmovle %edx, %esi
movl -40(%ebp), %edx
cmpl %edx, -36(%ebp)
cmovge -36(%ebp), %edx
movl -28(%ebp), %eax
cmpl %eax, -32(%ebp)
cmovge -32(%ebp), %eax
cmpl %eax, %edx
movl %eax, %ecx
cmovge %edx, %ecx
cmpl %edi, 12(%ebp)
jbe .L7
movl 12(%ebp), %eax
leal (%ebx,%edi,4), %edx
xorl %ebx, %ebx
subl %edi, %eax
movl %eax, %edi
.p2align 4,,7
.L9:
movl (%edx), %eax
cmpl %eax, %esi
cmovg %eax, %esi
cmpl %eax, %ecx
cmovl %eax, %ecx
incl %ebx
addl $4, %edx
cmpl %edi, %ebx
jne .L9
.L7:
movl 16(%ebp), %eax
movl %esi, (%eax)
movl %ecx, 4(%eax)
addl $28, %esp
popl %ebx
popl %esi
popl %edi
leave
ret
.size minmax, .-minmax
%



Interressant ist es zwischen .L5 und .L4, Rest ist dann Vector
Zusammenfuehrung und ungrade Arraylaengen Behandlung. Vorher auf das
richtige Alignment bringen lass ich dann mal als "exercise for the reader".
Ohh, sicher kann man da noch ein paar Instruktionen
rausfummeln/umsortieren und die Geschwindigkeit ausmessen muesstest du
dann auch noch...

Die passenden Instruktionen fuer MMX gibt es auch (pcmpgtd, pand, pandn,
por).
Es gibt fuer 16 und 8 Bit gleich die richten Befehle (z.B. pminsw,
pmaxsw) seit MMX, Ab SSE4.1 auch fuer 32Bit (z.B. pminsd). Da SSE4.1
aber recht neu ist hab ich hier die "Zufuss-Version" gemacht.
Hmmm, ich bin mir nur grad nicht sicher, ob es da nicht noch nen Trick
gibt mit den ganzen pschuf,punpck und dem gedoense...


Ich kann mich waage daran erinnern das es doch z.b. beim Umkopieren
vom Speicher ein Trick mit dem Cache gab... wenn ich mich nicht ire.
Hat jemand eine coole Idee wie man das noch schneller hinbekommt?




Cache hints ab SSE und MMX (prefetchnta, movnti und sowas)

mfg.
Herby



Gruss
Jan

"Ich fühle nichts außer einer Schwierigkeit zu existieren."
Bernard Le Bovier de Fontenelle

Ähnliche fragen