Gesetzte Bits im Byte zählen



  • www.cygwin.com *g*

    void populate()
    {
    char *BitFeld; //nur definition, muss vorher generiert werden
    char *felda,*feldb; //nur definition, sollten vorher geladen werden
    short unterschiede=0; //char ist ein bit zu klein 😉
    char i; //reicht später für meine zwecke, schleife wird immer nur bis 64 gehen
    for (i=0; i < 64;i++)
    unterschiede += BitFeld[felda[i] ^ feldb[i]];
    }

    darf ich mal posten, was der GCC bei verschiedenen Optimierungsstufen draus gemacht hat? ich hab irgendwie das gefühl, das ab -O2 da nur noch mist rauskommt.



  • zeig her.



  • -O2

    populate:
            pushl %ebp
            movl %esp,%ebp
            movl $63,%ecx
            .p2align 4,,7
    .L6:
            decl %ecx
            jns .L6
            movl %ebp,%esp
            popl %ebp
            ret
    

    hmm, so ohne XOR doch verdächtig *g*

    -O

    populate:
            pushl %ebp
            movl %esp,%ebp
            xorl %eax,%eax
            .p2align 4,,7
    .L6:
            incl %eax
            cmpl $63,%eax
            jle .L6
            movl %ebp,%esp
            popl %ebp
            ret
    

    wenigstens mal ein XOR, aber irgendwie sieht der code total komisch aus... kann jemand was dazu sagen?



  • kannste des mal in menschenlesbaren Code verwandeln *g*?



  • wenn ich den verstehen würde, dann vielleicht. aber ich bin eher ein assembler anfänger 😞
    schon die % vor den registern stört mich irgendwie.



  • eigentlich sieht der code doch ganz gut aus, nur der inhalt der schleife fehlt mir irgendwie
    die % kommen von der AT&T syntax

    -O2

    populate:
    pushl %ebp //
    movl %esp,%ebp // Stack frame setzen
    movl $63,%ecx // zähler setzen
    .p2align 4,,7
    .L6: // hier fehlt mir der inhalt
    decl %ecx // zähler -1
    jns .L6 // solange zähler > 0 loop zu .L6
    movl %ebp,%esp // stack zurücksetzen
    popl %ebp //
    ret // return

    hmm, so ohne XOR doch verdächtig *g*
    -O

    populate:
    pushl %ebp
    movl %esp,%ebp
    xorl %eax,%eax // hier wird nur andersrum gezählt
    .p2align 4,,7
    .L6:
    incl %eax
    cmpl $63,%eax
    jle .L6
    movl %ebp,%esp
    popl %ebp
    ret



  • werd´s am WE mal ausprobieren. GCC wird bei so einfachem code wohl kaum mist machen.



  • Original erstellt von Evil Azrael:
    werd´s am WE mal ausprobieren. GCC wird bei so einfachem code wohl kaum mist machen.

    Ganz im Gegenteil, GCC ist ein Genie 🙂
    ab O2 merkt GCC nämlich, dass du das Ergebnis garnicht weiter benutzt und schmeißt es einfach raus, weil wozu was berechnen, was keinen interessiert.

    Hab den Code einfach mal Testweise so abgeändert, dass BitFeld nur 1en, felda nur einsen und feldb nur Nullen enthält. Desweiteren gibt die Funktion einen int zurück (nämlich unterschiede), der danach noch per printf ausgegeben wird. Und schon hast du einen Riesigen Klumpen asm-Code 🙂



  • der wäre dann auch interessanter.
    ich hatte das auch so ausprobiert, dass ich den felder mit malloc speicher zugewiesen habe (später sollten dann über mmap die daten eingelesen werden (zum test)) , aber das hatte an der schleife nix geändert..
    aber das es daran liegen könnte, dass das ergebnis nicht verwendet wird, daran hatte ich nicht gedacht. *kopf_gegen_die_wand_donnert*
    wollte den code so gering wie möglich halten, um besser sehen zu können, was die schleife "kostet"
    naja, geht auch so :

    .L6:
            movb (%edx,%esi),%al
            xorb (%edx,%edi),%al
            movsbl %al,%eax
            incl %edx
            movsbw (%eax,%ebx),%ax
            addw %ax,%cx
            cmpl $63,%edx
            jle .L6
    

    ist doch ok. dafür lohnt es sich doch echt nicht, da inline assembler zu verwenden und dafür die portabilität zu opfern. braver GCC!

    ich glaube, bei großen datenmengen die verglichen werden müssen, könnte sich sogar lohnen, vorher eine tabelle mit 2^16 elementen zu generieren und die sich dann mit mmap (ich liebe diese funktion *g*) rein zu ziehen.



  • Also Bits zählen würde ich ungefähr so machen (mal ganz ohne Optimierungen, Wert soll in EAX sein, Ergebnis in EDX):

    xor edx,edx
       mov ecx,32
    looping:
       ror eax,1
       jnc no_inc
       inc edx
    no_inc:
       dec ecx
       jnz looping
    

    🙂



  • lies dir mal den ganzen Thread durch. ab Seite 1.



  • Das ist doch nahezu optimiert, allerdings auf Platz für selten ausgeführte BitCounts(). 😃
    *ich glaube ich werde diesen thread noch richtig vermissen*

    mfg
    -bg-



  • @malfunction:
    meinst du rcr oder wirklich ror(bei dem wird das cflag doch garnicht gesetzt 😕)



  • Original erstellt von -bg-:
    Das ist doch nahezu optimiert, allerdings auf Platz für selten ausgeführte BitCounts(). 😃
    *ich glaube ich werde diesen thread noch richtig vermissen*
    ...

    Ich habe mir die Tabellen-Version nochmal genauer angesehen und herausgefunden, dass nicht die ganze Tabelle mit 0xFFFF Einträgen berechnet werden muss, sondern nur etwas mehr als die Hälfte der Daten. Ich konnte das aber bis jetzt noch nicht so weit optimieren, dass der Algo "messbar" schneller arbeitet ...



  • naja, sehr optimiert find ich das nicht. außerdem ist es stark von den Daten abhängig und verwendet sprünge (was prediction-fehler ermöglicht)


Anmelden zum Antworten