Schnellste Methode zur Berechnung der Größenordnung in der x86-Assembly

12

Die Aufgabe ist einfach: Schreiben Sie eine Assembly, die die Größenordnung einer Ganzzahl mit möglichst wenigen Taktzyklen berechnet.

  • Größenordnung ist definiert als log10, nicht log2.
  • Der gültige Eingabebereich ist 0bis einschließlich. Das Eingabeverhalten außerhalb dieses Bereichs ist undefiniert.1012
  • Die Werte sollten auf die nächste Ganzzahl abgerundet werden, mit der Ausnahme, dass bei einer bestimmten Eingabe 0die Ausgabe erfolgen sollte 0. (Sie können dies als die beste Darstellung der negativen Unendlichkeit betrachten, die in vorzeichenlosen ganzen Zahlen möglich ist).
  • Muss x86-Assembly sein.
  • Die Ganzzahl muss ein Laufzeitwert sein, keine statische / inline Ganzzahl. Wir wissen also nicht, was es zur Kompilierungszeit ist.
  • Angenommen, Sie haben bereits eine Ganzzahl in ein Register geladen. (Setzen Sie jedoch den Wert in das Register in der Antwort ein, um die Übersichtlichkeit zu gewährleisten.)
  • Es können keine externen Bibliotheken oder Funktionen aufgerufen werden.
  • Befreien Sie sich von den verfügbaren Anweisungen in den Intel-Dokumenten .
  • Nein C.
  • Jede der ~ 7 Intel Core-Architekturen ist akzeptabel (siehe Seite 10 ). Idealerweise Nehalem (Intel Core i7).

Die gewinnende Antwort ist eine, die die wenigsten möglichen Taktzyklen verwendet. Das heißt, es können die meisten Vorgänge pro Sekunde ausgeführt werden. Ungefähre Zusammenfassungen der Taktzyklen finden Sie hier: http://www.agner.org/optimize/instruction_tables.pdf . Die Berechnung von Taktzyklen kann erfolgen, nachdem die Antwort gesendet wurde.

math fastest-algorithm assembly Lance Pollard
quelle
Sind "FYL2X" und andere FPU-Anweisungen zulässig?
Digital Trauma
1
Sollte das Ergebnis eine ganze Zahl sein? Wenn ja, wie sollte es gerundet werden?
Digital Trauma
3
Also sind die Eingabe und Ausgabe beide ganze Zahlen, ja? Die Eingabe kann jedoch bis zu 10 ^ 12 betragen, sodass sie für ein 32-Bit-Int zu groß ist. Nehmen wir also eine 64-Bit-Ganzzahleingabe an?
Paul R
3
Basiert das Gewinnkriterium auf der maximalen oder durchschnittlichen Anzahl von Zyklen? Und wenn es durchschnittlich ist, wie ist die Verteilung der Eingaben?
Runer112
2
Welcher Prozessor ist betroffen? Das verknüpfte Dokument listet mehr als 20 verschiedene Prozesse auf (AMD, Intel usw.), und die Latenzen variieren erheblich.
Digital Trauma

Antworten:

8

7 Zyklen, konstante Zeit

Hier ist eine Lösung, die auf meiner Antwort auf diese SO-Frage basiert . Es verwendet BSR, um zu zählen, wie viele Bits benötigt werden, um die Nummer zu halten. Es wird nachgeschlagen, wie viele Dezimalstellen erforderlich sind, um die größte Zahl darzustellen, die viele Bits enthalten können. Dann wird 1 abgezogen, wenn die tatsächliche Zahl kleiner ist als die nächste Zehnerpotenz mit so vielen Stellen.

    .intel_syntax noprefix
    .globl  main
main:
    mov rdi, 1000000000000              #;your value here
    bsr rax, rdi
    movzx   eax, BYTE PTR maxdigits[1+rax]
    cmp rdi, QWORD PTR powers[0+eax*8]
    sbb al, 0
    ret
maxdigits:
    .byte   0
    .byte   0
    .byte   0
    .byte   0
    .byte   1
    .byte   1
    .byte   1
    .byte   2
    .byte   2
    .byte   2
    .byte   3
    .byte   3
    .byte   3
    .byte   3
    .byte   4
    .byte   4
    .byte   4
    .byte   5
    .byte   5
    .byte   5
    .byte   6
    .byte   6
    .byte   6
    .byte   6
    .byte   7
    .byte   7
    .byte   7
    .byte   8
    .byte   8
    .byte   8
    .byte   9
    .byte   9
    .byte   9
    .byte   9
    .byte   10
    .byte   10
    .byte   10
    .byte   11
    .byte   11
    .byte   11
    .byte   12
powers:
    .quad   0
    .quad   10
    .quad   100
    .quad   1000
    .quad   10000
    .quad   100000
    .quad   1000000
    .quad   10000000
    .quad   100000000
    .quad   1000000000
    .quad   10000000000
    .quad   100000000000
    .quad   1000000000000

Kompiliert unter GCC 4.6.3 für Ubuntu und gibt den Wert im Exit-Code zurück.

Ich bin nicht sicher, ob ich diese Zyklustabelle für einen modernen Prozessor interpretieren kann, aber wenn ich die @ DigitalTrauma-Methode auf dem Nehalim-Prozessor verwende, erhalte ich 7 ?

ins        uOps Latency
---        -    - 
BSR r,r  : 1    3
MOVZX r,m: 1    -
CMP m,r/i: 1    1 
SBB r,r/i: 2    2
Ashelly
quelle
Oh - ich habe DigitalTrauma's gesehen, nachdem ich angefangen habe, meine zu schreiben. Ähnliche Ideen. Nach seiner Zählmethode erhalte ich 3,1,1,1 = 6 für BSR, MOV, CMP, SBB
AShelly
Ja, ich denke, deine schlägt meine. Nur um zu zeigen, a) ich bin kein Montageprogrammierer und b) Montage wird am besten von uns Sterblichen alleine gelassen ;-)
Digitales Trauma
The integer must be a runtime value, not a static/inline integer. So we don't know what it is at compile time.
Katze
1
In der nächsten Zeile heißt es: "Angenommen, Sie haben bereits eine Ganzzahl in ein Register geladen. (Setzen Sie jedoch den Wert in das Register in der Antwort, um die Übersichtlichkeit zu gewährleisten." Welches ist, was ich getan habe.
AShelly
Ersetzen Sie den movzx eax durch mov al. Die obersten 24 Bits von eax sind bereits Null, sodass das zx redundant ist (und teuer ist).
Peter Ferrie
6

Bester Fall 8 Zyklen, schlechtester Fall 12 Zyklen

Da es in der Frage nicht klar ist, begründe ich dies mit den Ivy Bridge-Latenzen.

Der Ansatz besteht hier darin, die bsrAnweisung (Bit-Scan-Umkehrung) als log2 () eines armen Mannes zu verwenden. Das Ergebnis wird als Index für eine Sprungtabelle verwendet, die Einträge für die Bits 0 bis 42 enthält. Ich gehe davon aus, dass die Verwendung des bsrBefehls OK ist , wenn die Operation für 64-Bit-Daten implizit erforderlich ist.

Im besten Fall kann der Eintrag jumptable die bsr Ergebnis direkt auf die Größe . Beispiel: Für Eingaben im Bereich 32-63 ist das bsrErgebnis 5, was einer Größe von 1 zugeordnet wird. In diesem Fall lautet der Befehlspfad:

Instruction    Latency

bsrq                 3
jmp                  2
movl                 1
jmp                  2

total                8

Im schlimmsten Fall wird das bsrErgebnis auf zwei mögliche Größen abgebildet, sodass der Eintrag für die Sprungtabelle eine weitere machtcmp , um zu überprüfen, ob die Eingabe> 10 n ist . ZB für Eingaben im Bereich 64-127 ist das bsrErgebnis 6. Der entsprechende Sprungtabelleneintrag prüft dann, ob die Eingabe> 100 ist, und stellt die Ausgabegröße entsprechend ein.

Zusätzlich zum Worst-Case-Pfad haben wir einen zusätzlichen mov-Befehl, um einen 64-Bit-Direktwert für die Verwendung in zu laden. cmpDer Worst-Case-Befehlspfad lautet also:

Instruction    Latency

bsrq                 3
jmp                  2
movabsq              1
cmpq                 1
ja                   2
movl                 1
jmp                  2

total               12

Hier ist der Code:

    /* Input is loaded in %rdi */
    bsrq    %rdi, %rax
    jmp *jumptable(,%rax,8)
.m0:
    movl    $0, %ecx
    jmp .end
.m0_1:
    cmpq    $9, %rdi
    ja  .m1
    movl    $0, %ecx
    jmp .end
.m1:
    movl    $1, %ecx
    jmp .end
.m1_2:
    cmpq    $99, %rdi
    ja  .m2
    movl    $1, %ecx
    jmp .end
.m2:
    movl    $2, %ecx
    jmp .end
.m2_3:
    cmpq    $999, %rdi
    ja  .m3
    movl    $2, %ecx
    jmp .end
.m3:
    movl    $3, %ecx
    jmp .end
.m3_4:
    cmpq    $9999, %rdi
    ja  .m4
    movl    $3, %ecx
    jmp .end
.m4:
    movl    $4, %ecx
    jmp .end
.m4_5:
    cmpq    $99999, %rdi
    ja  .m5
    movl    $4, %ecx
    jmp .end
.m5:
    movl    $5, %ecx
    jmp .end
.m5_6:
    cmpq    $999999, %rdi
    ja  .m6
    movl    $5, %ecx
    jmp .end
.m6:
    movl    $6, %ecx
    jmp .end
.m6_7:
    cmpq    $9999999, %rdi
    ja  .m7
    movl    $6, %ecx
    jmp .end
.m7:
    movl    $7, %ecx
    jmp .end
.m7_8:
    cmpq    $99999999, %rdi
    ja  .m8
    movl    $7, %ecx
    jmp .end
.m8:
    movl    $8, %ecx
    jmp .end
.m8_9:
    cmpq    $999999999, %rdi
    ja  .m9
    movl    $8, %ecx
    jmp .end
.m9:
    movl    $9, %ecx
    jmp .end
.m9_10:
    movabsq $9999999999, %rax
    cmpq    %rax, %rdi
    ja  .m10
    movl    $9, %ecx
    jmp .end
.m10:
    movl    $10, %ecx
    jmp .end
.m10_11:
    movabsq $99999999999, %rax
    cmpq    %rax, %rdi
    ja  .m11
    movl    $10, %ecx
    jmp .end
.m11:
    movl    $11, %ecx
    jmp .end
.m11_12:
    movabsq $999999999999, %rax
    cmpq    %rax, %rdi
    ja  .m12
    movl    $11, %ecx
    jmp .end
.m12:
    movl    $12, %ecx
    jmp .end

jumptable:
    .quad   .m0
    .quad   .m0
    .quad   .m0
    .quad   .m0_1
    .quad   .m1
    .quad   .m1
    .quad   .m1_2
    .quad   .m2
    .quad   .m2
    .quad   .m2_3
    .quad   .m3
    .quad   .m3
    .quad   .m3
    .quad   .m3_4
    .quad   .m4
    .quad   .m4
    .quad   .m4_5
    .quad   .m5
    .quad   .m5
    .quad   .m5_6
    .quad   .m6
    .quad   .m6
    .quad   .m6
    .quad   .m6_7
    .quad   .m7
    .quad   .m7
    .quad   .m7_8
    .quad   .m8
    .quad   .m8
    .quad   .m8_9
    .quad   .m9
    .quad   .m9
    .quad   .m9
    .quad   .m9_10
    .quad   .m10
    .quad   .m10
    .quad   .m10_11
    .quad   .m11
    .quad   .m11
    .quad   .m11_12
    .quad   .m12
    .quad   .m12
    .quad   .m12

.end:
/* output is given in %ecx */

Dies wurde hauptsächlich aus der gcc-Assembler-Ausgabe für den von mir geschriebenen Proof-of-Concept-C-Code generiert . Beachten Sie, dass der C-Code ein berechenbares goto verwendet, um die Sprungtabelle zu implementieren. Es verwendet auch die__builtin_clzll() gcc verwendet, das zur bsrAnweisung kompiliert wird (plus ein xor).

Ich habe mehrere Lösungen in Betracht gezogen, bevor ich zu dieser gekommen bin:

  • FYL2X um dann den natürlichen log zu berechnen FMUL durch die notwendige Konstante. Dies würde vermutlich gewinnen, wenn es ein [tag: instruction: golf] -Wettbewerb wäre. FYL2XHat aber so eine Latenz von 90-106 für Ivy Bridge.

  • Hardcodierte binäre Suche. Dies kann tatsächlich wettbewerbsfähig sein - ich überlasse es jemand anderem, dies umzusetzen :).

  • Komplette Nachschlagetabelle der Ergebnisse. Ich bin sicher, dass dies theoretisch am schnellsten ist, würde aber eine 1-TB-Nachschlagetabelle erfordern - noch nicht praktisch -, möglicherweise in ein paar Jahren, wenn Moores Gesetz weiterhin gilt.

Digitales Trauma
quelle
Bei Bedarf kann ich eine durchschnittliche Latenz für alle erlaubten Eingaben berechnen.
Digital Trauma
jmpUnd jcckeine Latenz, nur Durchsatzkosten. Verzweigungsvorhersage und spekulative Ausführung bedeuten, dass Kontrollabhängigkeiten nicht Teil von Datenabhängigkeitsketten sind.
Peter Cordes