Binäre Quersumme in C/Assembler optimieren

    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.

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

    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!

    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.

    *plantsch*

    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):

    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*

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

    Variante 2:

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

    *plantsch*

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

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

    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:

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!

Benutzerkonto erstellen Anmelden