Warum spielt der shift-left Operator zum Berechnen von 2-er Potenzen auf heutigen CPUs keine Rolle mehr



  • Wie in folgendem Artikel unter Details, 6. Absatz behauptet wird:
    http://manderc.com/operators/shiftleftoperator/

    Erkennt die HW automatisch, dass man 2-er Potenzen berechnen will und führt dann selber ein Shift durch, anstatt die normale Multiplikationseinheit zu nutzen oder woran liegt das?



  • PS:

    CPU Architektur soll x86 bzw. x64 sein.



  • weil multiplikation 1 cycle kostet auf modernen cpus.



  • shift operator useless? schrieb:

    Erkennt die HW automatisch, dass man 2-er Potenzen berechnen will und führt dann selber ein Shift durch, anstatt die normale Multiplikationseinheit zu nutzen oder woran liegt das?

    Nicht die Hardware, der Compiler. Es bringt in der Regel auf jeden Fall nix, zur "Optimierung" manuell mit Shifts rumzumachen, das macht bestenfalls den Code schwerer lesbar und schlechtestensfalls fängt man sich dabei einen Bug ein...

    rapso schrieb:

    weil multiplikation 1 cycle kostet auf modernen cpus.

    Also auf Ivy Bridge hat ein IMUL immer noch eine Latency von 3 Cycles.


  • Mod

    dot schrieb:

    shift operator useless? schrieb:

    Erkennt die HW automatisch, dass man 2-er Potenzen berechnen will und führt dann selber ein Shift durch, anstatt die normale Multiplikationseinheit zu nutzen oder woran liegt das?

    Nicht die Hardware, der Compiler. Es bringt in der Regel auf jeden Fall nix, zur "Optimierung" manuell mit Shifts rumzumachen, das macht bestenfalls den Code schwerer lesbar und schlechtestensfalls fängt man sich dabei einen Bug ein...

    Für kleine Zweierpotenzen (2, 4, 😎 habe ich Compiler das sogar zu lea(l) (load effective address (long)) optimieren sehen (beziehungsweise geht das sogar allgemein für kleine Multiplikationen), was eigentlich für nochmals ganz andere Zwecke gedacht ist (Adressberechnung eben). Das kann dann noch mal einen Tacken schneller sein kann als ein arithmetischer Shift, weil es die Rechnung in weniger beanspruchte Teilen der CPU verschiebt und auch etwas flexibler ist hinsichtlich, wo das Ergebnis landet. Quasi eine 0-Cycle Anweisung.

    Wobei man sagen sollte, dass das ein ganz alter Hut für Assemblerexperten ist. Aber es ist eben eine Optimierung, die nur auf Assemblerebene geht und keine direkte Entsprechung in C hat. Das heißt, man muss entweder sowieso dem Compiler vertrauen (Eine gute Idee!) oder direkt Assembler programmieren, wenn man hier den bestmöglich optimierten Code haben möchte.



  • dot schrieb:

    rapso schrieb:

    weil multiplikation 1 cycle kostet auf modernen cpus.

    Also auf Ivy Bridge hat ein IMUL immer noch eine Latency von 3 Cycles.

    du kannst pro cycle ein mul machen und darauf kommt es an.



  • rapso schrieb:

    weil multiplikation 1 cycle kostet auf modernen cpus.

    Ab welchen CPU Typen (Intel/AMD) ist das so?



  • SeppJ schrieb:

    ... weil es die Rechnung in weniger beanspruchte Teilen der CPU verschiebt und auch etwas flexibler ist hinsichtlich, wo das Ergebnis landet. Quasi eine 0-Cycle Anweisung.

    addressberechnung beim lesen/schreiben wird zwar von der address generation unit gemacht, LEA laeuft aber auf den ganz normalen integer units. Deswegen hat LEA auf haswell auch 3 cycles latency.

    wenn du pech hast, laeuft LEA sogar langsammer, weil du 4ports hast die integer ALU "verstehen" aber nur 2 die auch noch LEA "verstehen". Einer der LEA ports hat zwar fuer spezialfaelle einen bypass, aber du weisst nicht, ob deine op gerade darauf laufen wird oder auf dem langsamen.



  • shift operator useless? schrieb:

    rapso schrieb:

    weil multiplikation 1 cycle kostet auf modernen cpus.

    Ab welchen CPU Typen (Intel/AMD) ist das so?

    PentiumPro/K8



  • rapso schrieb:

    dot schrieb:

    rapso schrieb:

    weil multiplikation 1 cycle kostet auf modernen cpus.

    Also auf Ivy Bridge hat ein IMUL immer noch eine Latency von 3 Cycles.

    du kannst pro cycle ein mul machen und darauf kommt es an.

    Also worauf es ankommt das entscheidet wohl immer noch der Anwendungsfall und nicht der rapso.



  • hustbaer schrieb:

    rapso schrieb:

    dot schrieb:

    rapso schrieb:

    weil multiplikation 1 cycle kostet auf modernen cpus.

    Also auf Ivy Bridge hat ein IMUL immer noch eine Latency von 3 Cycles.

    du kannst pro cycle ein mul machen und darauf kommt es an.

    Also worauf es ankommt das entscheidet wohl immer noch der Anwendungsfall und nicht der rapso.

    Hat der hustbaer so entschieden.



  • Genau 😃
    Ne aber ehrlich, es gibt sicher genug Fälle wo 3 Zyklen Latenz nicht egal sind.



  • hustbaer schrieb:

    Genau 😃
    Ne aber ehrlich, es gibt sicher genug Fälle wo 3 Zyklen Latenz nicht egal sind.

    das mueste ein fall sein wo du nichts anderes machst ausser auf auf das resultat des muls zu warten und das zu soeinem extrem dass es messbar ist. ich kann mir keinen nicht kuenstlichen fall dazu denken.

    aber versuchen wir es mal

    a) du hast eine power of 2 multiplikation einmal irgendwo im source aber genug instruktionen um sie zu verstecken -> es macht keinen performance unterschied
    z.b. wird

    imul eax,2
    add edi,edi
    imul ebx,2
    add edi,edi
    imul edx,2
    add edi,edi
    

    genau so schnell laufen wie

    shl eax,1
    add edi,edi
    shl ebx,1
    add edi,edi
    shl edx,1
    

    a+)und waehrend dir einfaellt, dass du daraus ein shl machen kannst, weil es doch eine kleine dependency gibt, geht mehr deiner lebenszeit verloren als diese seltene operation jemals wieder gutmachen wird unter der sehr sehr seltenen voraus

    a++)nein, ok, es ist ein sehr intensiver loop, ohne dependancy der unmengen von multiplikationen braucht, sagen wir es ist ein

    for(int a=0;a<1024;a++)
        pData[a]*=16;
    

    dann kannst du natuerlich ein SHL bauen
    aber vorher solltest du den loop unrollen, sonst ist der overhead groesser
    jetzt saturieren wir mit muls, weil du 3cycles latenz und und 2 loads in parallel mit 2 stores hast, wir braeuchten 6 ALU ports, haben aber nur 4,ergo brauchen wir 1.5mal laenger mit muls....
    aber warte, vielleicht kannst du das mit SSE/AVX loesen?
    noch besser, am besten noch alignst du den pointer damit du aligned loads machen kannst, mit vectorized SHL dann sind wir bei

    movq      %rdi, %rsi                                    #5.2
            andq      $15, %rsi                                     #5.2
            movb      $0, %r8b                                      #5.2
            movl      %esi, %edx                                    #5.2
            testl     %edx, %edx                                    #5.2
            je        ..B1.7        # Prob 50%                      #5.2
            testb     $3, %dl                                       #5.2
            jne       ..B1.22       # Prob 10%                      #5.2
            negl      %edx                                          #5.2
            xorl      %ecx, %ecx                                    #5.2
            addl      $16, %edx                                     #5.2
            movq      %rdi, %rax                                    #
            shrl      $2, %edx                                      #5.2
            movl      %edx, %esi                                    #5.2
    ..B1.4:                         # Preds ..B1.4 ..B1.3
            incq      %rcx                                          #5.2
            shll      $4, (%rax)                                    #6.7
            addq      $4, %rax                                      #5.2
            cmpq      %rsi, %rcx                                    #5.2
            jb        ..B1.4        # Prob 99%                      #5.2
    ..B1.7:                         # Preds ..B1.1 ..B1.4
            negl      %edx                                          #5.2
            andl      $15, %edx                                     #5.2
            negl      %edx                                          #5.2
            addl      $1024, %edx                                   #5.2
            movl      %edx, %eax                                    #5.2
    ..B1.8:                         # Preds ..B1.8 ..B1.7
            movdqa    (%rdi,%rsi,4), %xmm0                          #6.7
            movdqa    16(%rdi,%rsi,4), %xmm1                        #6.7
            pslld     $4, %xmm0                                     #6.7
            movdqa    32(%rdi,%rsi,4), %xmm2                        #6.7
            pslld     $4, %xmm1                                     #6.7
            movdqa    48(%rdi,%rsi,4), %xmm3                        #6.7
            pslld     $4, %xmm2                                     #6.7
            pslld     $4, %xmm3                                     #6.7
            movdqa    %xmm0, (%rdi,%rsi,4)                          #6.7
            movdqa    %xmm1, 16(%rdi,%rsi,4)                        #6.7
            movdqa    %xmm2, 32(%rdi,%rsi,4)                        #6.7
            movdqa    %xmm3, 48(%rdi,%rsi,4)                        #6.7
            addq      $16, %rsi                                     #5.2
            cmpq      %rax, %rsi                                    #5.2
            jb        ..B1.8        # Prob 99%                      #5.2
    ..B1.10:                        # Preds ..B1.8 ..B1.22
            lea       1(%rdx), %eax                                 #5.2
            cmpl      $1024, %eax                                   #5.2
            ja        ..B1.21       # Prob 50%                      #5.2
            movl      %edx, %eax                                    #5.2
            negl      %eax                                          #5.2
            addl      $1024, %eax                                   #5.2
            cmpb      $1, %r8b                                      #5.2
            jne       ..B1.13       # Prob 50%                      #5.2
    ..B1.12:                        # Preds ..B1.13 ..B1.11
            xorl      %esi, %esi                                    #5.2
            jmp       ..B1.17       # Prob 100%                     #5.2
    ..B1.13:                        # Preds ..B1.11
            cmpl      $4, %eax                                      #5.2
            jb        ..B1.12       # Prob 10%                      #5.2
            movl      %eax, %esi                                    #5.2
            xorl      %ecx, %ecx                                    #5.2
            andl      $-4, %esi                                     #5.2
    ..B1.15:                        # Preds ..B1.15 ..B1.14
            lea       (%rdx,%rcx), %r8d                             #6.7
            addl      $4, %ecx                                      #5.2
            movslq    %r8d, %r8                                     #6.7
            cmpl      %esi, %ecx                                    #5.2
            movdqa    (%rdi,%r8,4), %xmm0                           #6.7
            pslld     $4, %xmm0                                     #6.7
            movdqa    %xmm0, (%rdi,%r8,4)                           #6.7
            jb        ..B1.15       # Prob 99%                      #5.2
    ..B1.17:                        # Preds ..B1.15 ..B1.12
            cmpl      %eax, %esi                                    #5.2
            jae       ..B1.21       # Prob 0%                       #5.2
    ..B1.19:                        # Preds ..B1.17 ..B1.19
            lea       (%rdx,%rsi), %ecx                             #6.7
            incl      %esi                                          #5.2
            movslq    %ecx, %rcx                                    #6.7
            shll      $4, (%rdi,%rcx,4)                             #6.7
            cmpl      %eax, %esi                                    #5.2
            jb        ..B1.19       # Prob 99%                      #5.2
    ..B1.21:                        # Preds ..B1.19 ..B1.10 ..B1.17
            ret                                                     #8.1
    ..B1.22:                        # Preds ..B1.2                  # Infreq
            movb      $1, %r8b                                      #5.2
            xorl      %edx, %edx                                    #5.2
    

    (ja, ich war zu faul, das hat ICC fuer mich gemacht)
    woohoo, 4 bzw 8 mal schneller als vorher.

    a+++)ok, aber das ist doch zu einfach, wir reden hier ja schliesslich ueber latenz, wir sollten entsprechend auf ein und derselben stelle shiften damit das zum vorschein kommt, das kann man nicht vektorisieren..

    mul eax,2
    mul eax,2
    mul eax,2
    mul eax,2
    mul eax,2
    mul eax,2
    
    shl eax,1
    shl eax,1
    shl eax,1
    shl eax,1
    shl eax,1
    shl eax,1
    

    ok, jetzt haben wir den case wo die latenz voll reinhaut :D... super optimierung von uns, jetzt muessen wir nur noch Jesters lachanfall ueberstehen bevor er fragt wieso wir nicht einfach *64 multiplizieren. hmmm...

    nein, ich weiss ehrlich nicht wo jemals ein fall noch aufkommen koennte SHL zu nutzen. entweder es ist so minor dass deine denkzeit die laufzeitersparnis mehr als abdeckt, oder es ist ein problemfall der gross genug ist, dass es keinen sinn macht nur ein SHL zu verbauen und sich zu freuen, wenn andere loesungen das 4 oder 8mal beschleunigen.

    frueher stallte die cpu bei einem mul grundsaetzlich, das waren in guten faellen 10cycles. selbst auf einem in order ARM (z.b. GBA) waren es 3 cycles und wenn man eine linie zeichnete, dann konnte man dort einige beschleunigen (ARM hat shift in vielen instructions gratis dabei gehabt damals).

    aber heute? sogar diese super optimierung von ARM wurde aus der hardware genommen, ein shift kostet dort 1 cycle extra. einfach weil er nichts nuetzliches macht.

    Manchmal optimieren compiler sogar ein shift zu einem mul um weil shift und rol partial flag stalls verursachen (koennen). (das ist wie partial register stall, also wenn du vom EAX nur al oder ah modifizierst).

    und ja, compiler wuerden dir * zu shl oder lea optimieren, manchmal zu mehreren lea statt einem imul, weil sie das aus prinzip machen. aber eine rolle spielt das auf der (modernen) cpu dann am ende nicht.

    bin gespannt auf den real world fall den du jetzt bringst wo SHL wirklich was bringt 😉



  • Will ja euer Rumzicken nicht unbedingt stören, aber grundsätzlich find ich die lea-Geschichte interessant. War mir vorher so nicht bewusst.


Log in to reply