Binäre Quersumme in C/Assembler optimieren

escitalopram

Hi Leute,
Ich möchte die Binäre Quersumme einer 32 Bit-Zahl möglichst effizient berechnen.
Ich arbeite auf einem Athlon XP Model 8 Prozessor mit angeblich 128kB split L1 Cache.

Ich habe mich vorläufig für die folgende Variante entschieden:
Ich denke mal im L1-Cache ist Platz für eine Lookup-Tabelle der Quersummen aller 8-Bit-Zahlen, und da könnte man ja 4 mal pro 32-Bit zahl nachschauen und das Ergebnis zusammenaddieren.
Leider bin ich nicht ganz so sattelfest in Assembler wie ich mir das wünsche, deshalb hab ich angefangen die Funktion in C zu programmieren und dann durch hinschauen auf den generierten Assembler-Code zu optimieren.

Code

const char quersumme_8[256] = {
		0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3 ,3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3 ,3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
	};


	unsigned char quersumme32(register unsigned int x) {
		register unsigned char a, b;
		register unsigned char r1,r2;
		a=quersumme_8[x&0xff];
		b=quersumme_8[(x>>8)&0xff];
		r1=a+b;
		x=x>>16;
		a=quersumme_8[x&0xff];
		b=quersumme_8[(x>>8)&0xff];
		r2=a+b;
		return r1+r2;
	}

Alles anzeigen

Mein GCC macht mit -march=athlon-xp -O3 dann folgendes draus:

Code

Dump of assembler code for function _ZN9P211quersumme32Ej:
    0x08048a90 <P2::quersumme32(unsigned int)+0>:    push   %ebp
    0x08048a91 <P2::quersumme32(unsigned int)+1>:    mov    %esp,%ebp
    0x08048a93 <P2::quersumme32(unsigned int)+3>:    mov    0x8(%ebp),%edx
    0x08048a96 <P2::quersumme32(unsigned int)+6>:    movzbl %dh,%eax
    0x08048a99 <P2::quersumme32(unsigned int)+9>:    movzbl %dl,%ecx
    0x08048a9c <P2::quersumme32(unsigned int)+12>:   shr    $0x10,%edx
    0x08048a9f <P2::quersumme32(unsigned int)+15>:   movzbl 0x8049540(%eax),%eax
    0x08048aa6 <P2::quersumme32(unsigned int)+22>:   add    0x8049540(%ecx),%al
    0x08048aac <P2::quersumme32(unsigned int)+28>:   movzbl %dl,%ecx
    0x08048aaf <P2::quersumme32(unsigned int)+31>:   shr    $0x8,%edx
    0x08048ab2 <P2::quersumme32(unsigned int)+34>:   movzbl 0x8049540(%edx),%edx
    0x08048ab9 <P2::quersumme32(unsigned int)+41>:   add    0x8049540(%ecx),%dl
    0x08048abf <P2::quersumme32(unsigned int)+47>:   leave  
    0x08048ac0 <P2::quersumme32(unsigned int)+48>:   add    %edx,%eax
    0x08048ac2 <P2::quersumme32(unsigned int)+50>:   movzbl %al,%eax
    0x08048ac5 <P2::quersumme32(unsigned int)+53>:   ret    
End of assembler dump.

Alles anzeigen

Jetzt frage ich mich: ist dieser Code wirklich optimal? Wenn ich da hinsehe, sehe ich 2 shr, wo eigentlich nur eins benötigt würde? Und überhaupt, was fummelt der da am Stack herum?

Kann mir vielleicht jemand von den technischen Informatikern (oder sonstigen Assembler-Programmieren) helfen das effizienter in C-inline-assembler hinzukriegen (das sollte mit dem GCC ja gehen..)?
Vielen Dank!

Plantschkuh!

Ich hab keine Vergleichsplattform zur Verfügung und meine Assembly-Kenntnisse sind etwas eingerostet, aber: Wenn du willst, daß der Optimierer gute Leistungen bringt, pfusch ihm nicht ins Handwerk. Für folgenden Code:

Code

unsigned char quersumme32(unsigned int x) {
    return quersumme_8[(x>>24) & 0xff] + quersumme_8[(x>>16) & 0xff]
        + quersumme_8[(x>>8) & 0xff] + quersumme_8[x & 0xff];
}

spuckt mein gcc mit -O3 hübscheren, kürzeren Code aus als für deinen. Wieso? Weil die Semantik von dem, was du erreichen willst, viel klarer rüberkommt. Und die Semantik ist das, womit der Optimierer nunmal arbeitet; viele Optimierungen hauen (leider) nicht hin, wenn man die gewünschte Berechnung über mehrere Statements verteilt.

escitalopram

Seltsam, das liefert bei mir längeren Code, mit zusätzlichen ANDs, wieder einem unnötigen shr (das müsste man ja mit den h- und l-registern machen können) und auf dem Stack pfuscht er erst wieder herum (das scheint wohl ohne inline-assembler nicht zu vermeiden zu sein):

Code

Dump of assembler code for function _ZN9P211quersumme32Ej:
    0x08048a90 <P2::quersumme32(unsigned int)+0>:    push   %ebp
    0x08048a91 <P2::quersumme32(unsigned int)+1>:    mov    %esp,%ebp
    0x08048a93 <P2::quersumme32(unsigned int)+3>:    mov    0x8(%ebp),%ecx
    0x08048a96 <P2::quersumme32(unsigned int)+6>:    mov    %ecx,%eax
    0x08048a98 <P2::quersumme32(unsigned int)+8>:    mov    %ecx,%edx
    0x08048a9a <P2::quersumme32(unsigned int)+10>:   shr    $0x10,%eax
    0x08048a9d <P2::quersumme32(unsigned int)+13>:   shr    $0x18,%edx
    0x08048aa0 <P2::quersumme32(unsigned int)+16>:   and    $0xff,%eax
    0x08048aa5 <P2::quersumme32(unsigned int)+21>:   movzbl 0x8049540(%eax),%eax
    0x08048aac <P2::quersumme32(unsigned int)+28>:   add    0x8049540(%edx),%al
    0x08048ab2 <P2::quersumme32(unsigned int)+34>:   movzbl %ch,%edx
    0x08048ab5 <P2::quersumme32(unsigned int)+37>:   and    $0xff,%ecx
    0x08048abb <P2::quersumme32(unsigned int)+43>:   add    0x8049540(%edx),%al
    0x08048ac1 <P2::quersumme32(unsigned int)+49>:   add    0x8049540(%ecx),%al
    0x08048ac7 <P2::quersumme32(unsigned int)+55>:   leave  
    0x08048ac8 <P2::quersumme32(unsigned int)+56>:   movzbl %al,%eax
    0x08048acb <P2::quersumme32(unsigned int)+59>:   ret    
End of assembler dump.

Alles anzeigen

Was für eine GCC-Version verwendest du, und wie sieht dein Assembler-Code aus?

Edit: Langsamer ist der Code auch

Edit2: mit -fomit-frame-pointer lässt er den Stack in Ruhe und der Code schrumpft auf 50 Byte und wird auch entsprechend schneller *freu*

Plantschkuh!

Ich verwend den gcc 3.3, aber halt auf meinem iBook, da wird natürgemäß PowerPC-Code generiert. Variante 1:

Code

_quersumme32:
        mflr r7
        bcl 20,31,"L00000000001$pb"
"L00000000001$pb":
        mflr r2
        srwi r11,r3,16
        addis r6,r2,ha16(_quersumme_8-"L00000000001$pb")
        rlwinm r5,r3,0,24,31
        la r12,lo16(_quersumme_8-"L00000000001$pb")(r6)
        rlwinm r4,r3,24,24,31
        rlwinm r8,r11,0,24,31
        srwi r9,r11,8
        lbzx r10,r12,r5
        mtlr r7
        lbzx r0,r12,r4
        lbzx r5,r12,r9
        lbzx r6,r12,r8
        add r7,r10,r0
        rlwinm r3,r7,0,0xff
        add r2,r6,r5
        rlwinm r4,r2,0,0xff
        add r2,r3,r4
        rlwinm r3,r2,0,0xff
        blr

Alles anzeigen

Variante 2:

Code

_quersumme32:
        mflr r6
        bcl 20,31,"L00000000001$pb"
"L00000000001$pb":
        mflr r2
        srwi r11,r3,24
        addis r5,r2,ha16(_quersumme_8-"L00000000001$pb")
        rlwinm r10,r3,16,24,31
        la r12,lo16(_quersumme_8-"L00000000001$pb")(r5)
        rlwinm r8,r3,24,24,31
        lbzx r4,r12,r11
        rlwinm r7,r3,0,24,31
        lbzx r9,r12,r10
        mtlr r6
        lbzx r6,r12,r8
        add r0,r4,r9
        lbzx r4,r12,r7
        add r5,r6,r0
        add r2,r4,r5
        rlwinm r3,r2,0,0xff
        blr

Alles anzeigen

Sicher kein weltbewegender Unterschied, und ich wüßt nichtmal, ob zweiteres schneller ist. Schaut aber etwas besser aus.

escitalopram

Hmm... na gut, zum ersten kann ich PPC-Assembler noch weniger lesen und zum zweiten hat der einen ganz anderen Registersatz... Aber ich glaub es reicht mir 4 Milliarden Bit-Quersummen in ~30 Sekunden berechnen zu können (ist das gut bei 1,6 GHz?)... Im Notfall kann ich mein Programm ja noch später optimieren...

escitalopram

Falls es jemanden interessiert: Hab mich jetzt ein bisschen in die Dokumentation eingegraben und folgendes implementiert, scheint noch schneller zu sein:

Code

inline unsigned char q32(register unsigned int x) {
        register unsigned char result;
        asm("xor %%ecx,%%ecx; xlatb; movb %%al,%%cl; shr $8, %%eax; xlatb; add %%al,%%cl; shr $8, %%eax; xlatb; add %%al,%%cl; shr $8, %%eax; xlatb; add %%al,%%cl; ":"=c" (result):[tabelle] "b" (quersumme_8), [wert] "a" (x));
        return result;
    }

volatile_void

Hallo!

Hätte da eine Idee für eine Variante die ohne Table-lookup auskommt. Ist aber noch nicht getestet (weder auf Korrektheit noch auf Performanz) und möglicherweise nicht ganz so schnell.

Code

unsigned char quersumme32(register unsigned int x) 
{
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555); /* 2bit sums */
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333); /* 4bit sums */
    x = (x + (x >> 4)) & 0x0f0f0f0f;                /* byte sums */
    x = x + (x >> 8) + (x >> 16) + (x >> 24);
    return x & 0xff;
}

Meiner Ansicht nach müsste sich das in x86 Assembler superskalar in 12 Takten ausführen lassen, um zwar in etwa so:

Code

/* x in %eax */
mov %eax, %edx           //  1.1
shr $1, %eax             //  1.2
and $0x55555555, %edx    //  2.1
and $0x55555555, %eax    //  2.2
add %edx, %eax           //  3
mov %eax, %edx           //  4.1
shr $2, %eax             //  4.2
and $0x33333333, %edx    //  5.1
and $0x33333333, %eax    //  5.2
add %edx, %eax           //  6
mov %eax, %edx           //  7.1
shr $4, %eax             //  7.2
add %edx, %eax           //  8
and $0x0f0f0f0f, %eax    //  9
mov %eax, %edx           // 10.1
shr $16, %eax            // 10.2
add %dx, %ax             // 11
add %ah, %al             // 12.1
mov $0, %ah              // 12.2

Alles anzeigen

Jetzt mitmachen!