Optimierungen an Modulo



  • Erste Frage:

    Ein Modulo ist im Assembler ja dasselbe wie eine Division, nur dass der Wert aus einem anderen Register genommen wird. Wie siehts aus in folgendem Stück Code:

    int a = 42;
    int b = a / 10;
    int c = a % 10;
    

    Angenommen, der Compiler berechnet hier die Berechnungen nicht zur Compilezeit weg (Oder a steht erst zur Laufzeit fest), wird hier im Assembler zu einer Division optimiert?

    Zweite Frage:

    Teilbarkeiten lassen sich ja oft einfach feststellen, wie zum Beispiel Teilbar von 2 (1er bit auf 0). Ich weiß nicht, ob sich andere Teilbarkeits Regeln, vor allem kompliziertere, wie die Teilbarkeit durch 11, einfach aufs Binärsystem übertragen lassen, aber wird hier von den Compilern optimiert?



  • Dein Compiler hat mit sehr großer Wahrscheinlichkeit ein ASM Listing generieren.
    Da kannst du selber nachschauen.

    Prinzipiell würde ich aber beide Optimierungen von meinem Compiler erwarten.



  • Das lässt sich generell so nicht beantworten, weil im Standard nix dazu festgelegt ist. Die Compilerhersteller können hier rumoptimieren wie sie wollen, solange die Sematik die gleiche bleibt.
    Am besten guckst du dir einfach mal den erzeugten ASM-Code von deinem Compiler mit deinen benutzen Optimierungseinstellungen an.

    Edit: War zu lahm. 😉



  • Visual Studio 2010:

    int b = a / 10;
    00C416C3  mov         eax,66666667h  
    00C416C8  imul        dword ptr [esp+4]  
    00C416CC  sar         edx,2  
    00C416CF  mov         ecx,edx  
    00C416D1  shr         ecx,1Fh  
    00C416D4  add         ecx,edx  
      int c = b % 10;
    00C416D6  mov         eax,66666667h  
    00C416DB  imul        ecx  
    00C416DD  sar         edx,2  
    00C416E0  mov         eax,edx  
    00C416E2  shr         eax,1Fh  
    00C416E5  add         eax,edx  
    00C416E7  lea         edx,[eax+eax*4]  
    00C416EA  add         edx,edx  
    00C416EC  sub         ecx,edx
    

  • Mod

    Auch wenn du so ein bisschen zu den C++-Puristen zählst, die C-Bibliothek sollte man nicht vergessen:
    http://www.cplusplus.com/reference/clibrary/cstdlib/div/
    Das wird garantiert optimiert, dazu ist es da.

    In der C-Biliothek gibt es so manche Schätzchen.

    edit: In diesem Fall würde ich jedoch davon ausgehen, dass ein Compiler das heutzutage erkennt. Es ist relativ offensichtlich, wie das zu optimieren ist. Die genannte Funktion zählt eher zu der Sorte die man gebraucht hat, als die Compiler noch nicht so gut waren.


  • Mod

    314159265358979 schrieb:

    Zweite Frage:

    Teilbarkeiten lassen sich ja oft einfach feststellen, wie zum Beispiel Teilbar von 2 (1er bit auf 0). Ich weiß nicht, ob sich andere Teilbarkeits Regeln, vor allem kompliziertere, wie die Teilbarkeit durch 11, einfach aufs Binärsystem übertragen lassen, aber wird hier von den Compilern optimiert?

    Die Regeln gelten in jedem Positionssystem sinngemäß (kannst du dir induktiv leicht herleiten):
    In einem Zahlensystem Zur Basis B, kann die Teilbarhkeit durch B-1 anhand der Quersumme, die durch B+1 anhand der alternierenden Quersumme getestet werden. Gleiches gilt für die Teiler von B-1 und B+1.
    Die Teilbarkeit durch 2 kann folglich in einem System mit ungerader Basis sowohl an der einfachen als auch an der alternierenden Quersumme erkannt werden.



  • cooky451 schrieb:

    Visual Studio 2010:

    int b = a / 10;
    00C416C3  mov         eax,66666667h  
    00C416C8  imul        dword ptr [esp+4]  
    00C416CC  sar         edx,2  
    00C416CF  mov         ecx,edx  
    00C416D1  shr         ecx,1Fh  
    00C416D4  add         ecx,edx  
      int c = b % 10;
    00C416D6  mov         eax,66666667h  
    00C416DB  imul        ecx  
    00C416DD  sar         edx,2  
    00C416E0  mov         eax,edx  
    00C416E2  shr         eax,1Fh  
    00C416E5  add         eax,edx  
    00C416E7  lea         edx,[eax+eax*4]  
    00C416EA  add         edx,edx  
    00C416EC  sub         ecx,edx
    

    Wenn ich das richtig sehe (Bin kein ASM Experte) hat VS hier nicht optimiert? 😮

    camper schrieb:

    Die Regeln gelten in jedem Positionssystem sinngemäß (kannst du dir induktiv leicht herleiten):
    In einem Zahlensystem Zur Basis B, kann die Teilbarhkeit durch B-1 anhand der Quersumme, die durch B+1 anhand der alternierenden Quersumme getestet werden. Gleiches gilt für die Teiler von B-1 und B+1.
    Die Teilbarkeit durch 2 kann folglich in einem System mit ungerader Basis sowohl an der einfachen als auch an der alternierenden Quersumme erkannt werden.

    Wieder was gelernt. Kann man auch allgemeine Teilbarkeitsregeln für jede beliebige Zahl in jedem beliebigen Zahlensystem aufstellen?



  • Die Teilbarkeitsregelnbeiträge habe ich dorthin http://www.c-plusplus.net/forum/290591 geschubst.



  • @cooky451:
    Du hast falsch abgetippt ( int c = b % 10; gibt's in der Frage von 314 nicht).
    Und ist das "Release" Code, mit a = Konstante , oder vielleicht mit a = rand() um das Wegoptimieren zu unterdrücken?

    Interessant wäre für mich z.B. ob der Compiler schlau genug ist für

    #include <iostream>
    int main()
    {
    int a = 42;
    int b = a / 10;
    int c = a % 10;
    std::cout << b << ", " << c << "\n";
    }
    

    Kann er alles wegoptimieren, und Konstanten ausgeben?

    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    int main()
    {
    std::srand(std::time(0));
    int a = rand();
    int b = a / 10;
    int c = a % 10;
    std::cout << b << ", " << c << "\n";
    }
    

    Checkt er dass er nur 1x div (bzw. den div-ersatzcode) braucht, oder rechnet er für / und % doppelt?

    (Ich bin mir ziemlich sicher dass er in beiden Fällen schlau genug ist, aber habs nicht ausprobiert)


  • Mod

    hustbaer schrieb:

    Kann er alles wegoptimieren, und Konstanten ausgeben?

    Nur mit G++ getestet, der macht es, was ich auch sehr überraschend gefunden hätte, wenn nicht. Dazu ist ein Compiler da.

    Checkt er dass er nur 1x div (bzw. den div-ersatzcode) braucht, oder rechnet er für / und % doppelt?

    Gute Frage, mein Assembler ist nicht gut genug dafür 🙂 . Ich vermute schon.



  • hustbaer schrieb:

    @cooky451:
    Du hast falsch abgetippt ( int c = b % 10; gibt's in der Frage von 314 nicht).
    Und ist das "Release" Code, mit a = Konstante , oder vielleicht mit a = rand() um das Wegoptimieren zu unterdrücken?

    Mein Post wurde wohl versehentlich verschoben:

    cooky451 schrieb:

    314159265358979 schrieb:

    Dann hat cookie sich wohl vertippt 🤡

    Jau, ärgerlich. Hätte eigentlich sofort auffallen sollen, verdammt.

    int b = a / 10;
      int c = a % 10;
    008616C3  mov         ecx,dword ptr [esp+4]  
    008616C7  mov         eax,66666667h  
    008616CC  imul        ecx  
    008616CE  sar         edx,2  
    008616D1  mov         eax,edx  
    008616D3  shr         eax,1Fh  
    008616D6  add         eax,edx  
    008616D8  lea         edx,[eax+eax*4]  
    008616DB  add         edx,edx  
    008616DD  sub         ecx,edx
    


  • @cooky451:

    Ah, in den anderen Fred hab ich nicht geguckt.

    D.h. er ...
    * multipliziert statt zu dividieren
    * check dass er "c = a - 10 * b" rechnen kann
    * rechnet "10 * b" als "2 * (b + 4 * b)" mit nur zwei instructions (lea+add)

    Sehr schön.
    Und ich nehme an du hast für die Initialisierung von a keine Konstante genommen, ja?



  • hustbaer schrieb:

    Und ich nehme an du hast für die Initialisierung von a keine Konstante genommen, ja?

    Nein, dann haut er alles raus. Habe einfach eine Zahl von cin gelesen. 🙂


Anmelden zum Antworten