Binäre Quersumme in C/Assembler optimieren

NetzUnity und Informatik-forum wurden zusammengelegt. Eine entsprechende Ankündigung wird demnächst noch folgen. Für 2025 ist hier einiges geplant! Bei Fragen bitte per DM an Maximilian Rupp wenden.

    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*

    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