Wie funktioniert die GCC-Implementierung der modulo ( % ) - Arbeit, und warum tut Sie es nicht verwenden die div-Anweisung?

War ich versucht, herauszufinden, wie die Berechnung mit modulo 10 mit Montage-so habe ich kompiliert den folgenden c-code in gcc zu sehen, was es kam mit.

unsigned int i=999;
unsigned int j=i%10;

Zu meiner überraschung bekam ich

movl    -4(%ebp), %ecx
movl    $-858993459, %edx
movl    %ecx, %eax
mull    %edx
shrl    $3, %edx
movl    %edx, %eax
sall    $2, %eax
addl    %edx, %eax
addl    %eax, %eax
movl    %ecx, %edx
subl    %eax, %edx
movl    %edx, %eax
movl    %eax, -12(%ebp)

Wo -4(%ebp) oder "ich" ist der Eingang und -12(%ebp) oder "j" ist die Antwort. Ich habe diese getestet und es funktioniert, egal was Zahl, die Sie machen, -4(%ebp).

Meine Frage ist, wie dieser code funktioniert, und wie ist es besser als mit den div operand.

InformationsquelleAutor St0ner | 2010-12-05
  1. 23

    Zweite Frage zuerst: div ist ein sehr langsamer Befehl (mehr als 20 Taktzyklen). Die Reihenfolge oben besteht aus mehr Hinweise, aber Sie sind alle relativ schnell, so dass es ein Netto-Gewinn in Bezug auf die Geschwindigkeit.

    Den ersten fünf Anweisungen (bis zu und einschließlich der shrl) berechnen Sie i/10 (ich werde erklären, wie man in einer minute).

    Den nächsten Anweisungen, multiplizieren Sie das Ergebnis durch 10 wieder, aber das vermeiden der mul/imul Anweisungen (egal, ob Sie gewinnen oder nicht hängt von der genauen Prozessor-Sie sind targeting - neuere x86s sehr schnell Multiplikatoren, aber ältere nicht).

    movl    %edx, %eax   ; eax=i/10
sall    $2, %eax     ; eax=(i/10)*4
addl    %edx, %eax   ; eax=(i/10)*4 + (i/10) = (i/10)*5
addl    %eax, %eax   ; eax=(i/10)*5*2 = (i/10)*10

    Diese wird dann subtrahiert von i wieder um i - (i/10)*10 die i % 10 (für vorzeichenlose zahlen).

    Schließlich auf der Berechnung von i/10: Die grundlegende Idee ist, ersetzen Sie die division durch 10 Multiplikation mit 1/10. Der compiler hat eine fixed-point-approximation dieser durch Multiplikation mit (2**35 /10 + 1) - das ist der Magische Wert geladen edx, obwohl es für die Ausgabe als vorzeichenbehaftete Wert, obwohl es wirklich nicht signierte - und rechts-Verschiebung das Ergebnis von 35. Dieser schaltet ab, um das richtige Ergebnis für alle 32-bit-Ganzzahlen.

    Gibt es algorithmen, um zu bestimmen, diese Art der Annäherung, die garantieren, dass der Fehler kleiner als 1 ist (für die ganzen zahlen bedeutet, es ist der richtige Wert) und GCC offensichtlich verwendet man 🙂

    Letzte Bemerkung: Wenn Sie wollen, um tatsächlich zu sehen, GCC berechnen einer modulo, stellen Sie den divisor-variable (z.B. ein function-parameter), so kann es nicht diese Art von Optimierung. Jedenfalls, auf x86, Sie berechnen modulo mit div. div erwartet, dass die 64-bit-Dividende in edx:eax (high 32 bits in edx, low 32-bits in eax - klare edx auf null, wenn Sie arbeiten mit einem 32-bit-Zahl) und teilt diese durch was auch immer operand geben Sie (z.B. div ebx teilt edx:eax durch ebx). Es gibt den quotient in eax und den Rest in die edx. idiv tut das gleiche für vorzeichenbehaftete Werte.

    InformationsquelleAutor Fabian Giesen
  2. 3

    Den ersten Teil, bis zu shrl $3, %edx implementiert eine schnelle integer-division durch 10. Es gibt ein paar verschiedene algorithmen, die funktionieren, wenn die Zahl durch die Sie dividieren im Voraus bekannt ist. Beachten Sie, dass 858993459 ist "0.2 * 2^32". Der Grund, dies zu tun ist, weil, obwohl es eine integer-division Unterricht div/idiv im instruction set, es ist in der Regel sehr langsam, mehrmals langsamer als die Multiplikation.

    Den zweiten Teil berechnet den Rest durch Multiplikation das Ergebnis der division durch 10 (in einem indirekten Weg, über Verschiebungen und ergänzt; vermutlich ist der compiler denkt, dass es schneller Weg) und dann subtrahieren, dass von der ursprünglichen Anzahl.

    InformationsquelleAutor Eugene Smith
Schreibe einen Kommentar