Wenn ich den Zeitunterschied zwischen Verschiebung und Multiplikation in C teste, gibt es keinen Unterschied. Warum?

28

Mir wurde beigebracht, dass das Verschieben in binärer Form viel effizienter ist als das Multiplizieren mit 2 ^ k. Ich wollte also experimentieren und habe den folgenden Code verwendet, um dies zu testen:

#include <time.h>
#include <stdio.h>

int main() {
    clock_t launch = clock();
    int test = 0x01;
    int runs;

    //simple loop that oscillates between int 1 and int 2
    for (runs = 0; runs < 100000000; runs++) {


    // I first compiled + ran it a few times with this:
    test *= 2;

    // then I recompiled + ran it a few times with:
    test <<= 1;

    // set back to 1 each time
    test >>= 1;
    }

    clock_t done = clock();
    double diff = (done - launch);
    printf("%f\n",diff);
}

Für beide Versionen betrug der Ausdruck ungefähr 440000, Geben oder Nehmen 10000. Es gab keinen (zumindest optisch) signifikanten Unterschied zwischen den Ausgaben der beiden Versionen. Meine Frage ist also, stimmt etwas mit meiner Methodik nicht? Sollte es überhaupt einen optischen Unterschied geben? Hat dies etwas mit der Architektur meines Computers, des Compilers oder etwas anderem zu tun?

NicholasFolk
quelle
47
Wer hat dir das beigebracht? Dieser Glaube gilt seit den 1970er Jahren nicht mehr für häufig verwendete Compiler auf häufig verwendeten Architekturen. Gut für Sie, um diese Behauptung zu testen. Ich habe diese unsinnige Behauptung über JavaScript gehört, um Himmels willen.
Eric Lippert
21
Der beste Weg, um solche Fragen zu beantworten, besteht darin, den Assembler-Code zu betrachten, den der Compiler erstellt. Compiler haben normalerweise die Möglichkeit, eine Kopie der Assemblersprache zu erstellen, die sie generieren. Für die GNU GCC-Compiler ist dies '-S'.
Charles E. Grant
8
Man sollte darauf hinweisen, dass nach dem Betrachten mit gcc -S, der Code für test *= 2tatsächlich kompiliert wird. shll $1, %eax Beim Aufruf mit gcc -O3 -Sgibt es nicht einmal eine Schleife. Die beiden callq _clock movq %rax, %rbx callq _clock
6
"Mir wurde beigebracht, dass das Verschieben in der Binärzahl viel effizienter ist als das Multiplizieren mit 2 ^ k"; Wir bekommen eine Menge Dinge beigebracht, die sich als falsch (oder zumindest veraltet) herausstellen. Ein schlauer Compiler verwendet für beide den gleichen Shift-Vorgang.
John Bode
9
Überprüfen Sie immer den generierten Assemblycode, wenn Sie an dieser Art von Optimierung arbeiten, um sicherzustellen, dass Sie das messen, was Sie zu messen glauben. Eine große Anzahl von "Warum sehe ich diese Zeiten?" - Fragen zu SO laufen darauf hinaus, dass der Compiler Operationen vollständig eliminiert, da die Ergebnisse nicht verwendet werden.
Russell Borogove

Antworten:

44

Wie in der anderen Antwort erwähnt, optimieren die meisten Compiler automatisch Multiplikationen, die mit Bitverschiebungen durchgeführt werden.

Dies ist eine sehr allgemeine Regel bei der Optimierung: Die meisten 'Optimierungen' führen die Kompilierung in Bezug auf das, was Sie wirklich meinen, tatsächlich fehl und können sogar die Leistung beeinträchtigen.

Optimieren Sie erst, wenn Sie ein Leistungsproblem festgestellt und das Problem gemessen haben. (und der meiste Code, den wir schreiben, wird nicht so oft ausgeführt, sodass wir uns nicht darum kümmern müssen)

Der große Nachteil bei der Optimierung ist, dass der 'optimierte' Code oft viel weniger lesbar ist. Gehen Sie in Ihrem Fall immer zur Multiplikation, wenn Sie multiplizieren möchten. Und gehen Sie zum Verschieben von Bits, wenn Sie Bits verschieben möchten.

Thirler
quelle
20
Verwenden Sie immer die semantisch korrekte Operation. Wenn Sie Bitmasken manipulieren oder kleine Ganzzahlen innerhalb größerer Ganzzahlen positionieren, ist Shift die geeignete Operation.
Ddyer
2
Wäre es jemals (praktisch) notwendig, eine Multiplikation mit einem Schichtbetreiber in einer hochrangigen Softwareanwendung zu optimieren? Da der Compiler bereits optimiert, ist es anscheinend nur sinnvoll, über dieses Wissen zu verfügen, wenn Sie auf einer sehr niedrigen Ebene programmieren (zumindest unterhalb des Compilers).
NicholasFolk
11
@NicholasFolk nein. Tun Sie, was am einfachsten zu verstehen ist. Wenn Sie Assembly direkt geschrieben haben, kann dies hilfreich sein ... oder wenn Sie einen optimierenden Compiler geschrieben haben, kann dies ebenfalls hilfreich sein. Aber abgesehen von diesen beiden Fällen ist es ein Trick, der Ihre Handlungen verdunkelt und den nächsten Programmierer (der ein Axtmord ist und weiß, wo Sie leben ) dazu bringt, Ihren Namen zu verfluchen und ein Hobby aufzunehmen.
2
@NicholasFolk: Optimierungen auf dieser Ebene werden von der CPU-Architektur sowieso fast immer verdeckt oder in Frage gestellt. Wen kümmert es, wenn Sie 50 Zyklen einsparen, wenn Sie nur die Argumente aus dem Speicher abrufen und zurückschreiben, was über 100 kostet? Mikrooptimierungen wie diese machten Sinn, als der Speicher mit der Geschwindigkeit der CPU lief (oder sich dieser annäherte), aber heute nicht mehr so ​​sehr.
TMN
2
Weil ich es leid bin, diese 10% dieses Zitats zu sehen, und weil es hier den Nagel auf den Kopf trifft: "Es besteht kein Zweifel, dass der Gral der Effizienz zu Missbrauch führt. Programmierer verschwenden enorm viel Zeit damit, darüber nachzudenken oder sich Sorgen zu machen Die Geschwindigkeit unkritischer Teile ihrer Programme und diese Effizienzversuche wirken sich bei Debugging und Wartung sogar stark negativ aus. Wir sollten kleine Effizienzvorteile vergessen, etwa 97% der Fälle: Vorzeitige Optimierung ist die Wurzel von alles böse ...
cHao
25

Der Compiler erkennt Konstanten und wandelt Multiplikationen gegebenenfalls in Verschiebungen um.

ddyer
quelle
Der Compiler erkennt Konstanten mit Zweierpotenzen und konvertiert sie in Verschiebungen. Nicht alle Konstanten können in Schichten geändert werden.
quick_now
4
@quickly_now: Sie können in Kombinationen von Verschiebungen und Additionen / Subtraktionen umgewandelt werden.
Mehrdad
2
Ein klassischer Fehler im Compiler-Optimierer besteht darin, Divisionen in Rechtsverschiebungen umzuwandeln. Dies funktioniert für positive Dividenden, ist jedoch für negative um 1 niedriger.
Ddyer
1
@quickly_now Ich glaube, der Begriff "wo angemessen" deckt die Idee ab, dass einige Konstanten nicht als Verschiebungen umgeschrieben werden können.
Pharap
21

Ob das Schalten schneller ist als das Multiplizieren, hängt von der Architektur Ihrer CPU ab. In den Tagen des Pentium und früher war das Verschieben oft schneller als das Multiplizieren, abhängig von der Anzahl von 1 Bits in Ihrem Multiplikanden. Wenn Ihr Multiplikand beispielsweise 320 war, sind das 101000000, zwei Bits.

a *= 320;               // Slower
a = (a<<7) + (a<<9);    // Faster

Aber wenn du mehr als zwei Bits hättest ...

a *= 324;                        // About same speed
a = (a<<2) + (a<<7) + (a<<9);    // About same speed

a *= 340;                                 // Faster
a = (a<<2) + (a<<4) + (a<<7) + (a<<9);    // Slower

Auf einem kleinen Mikrocontroller wie einem PIC18 mit Single-Cycle-Multiplikation, aber ohne Barrel-Shifter , ist die Multiplikation schneller, wenn Sie um mehr als 1 Bit verschieben.

a  *= 2;   // Exactly the same speed
a <<= 1;   // Exactly the same speed

a  *= 4;   // Faster
a <<= 2;   // Slower

Beachten Sie, dass dies das Gegenteil von dem ist, was bei älteren Intel-CPUs der Fall war.

So einfach ist das aber noch nicht. Wenn ich mich recht erinnere, konnte ein Pentium aufgrund seiner superskalaren Architektur entweder einen Multiplikationsbefehl oder zwei Schichtbefehle gleichzeitig verarbeiten (solange sie nicht voneinander abhängig waren). Wenn Sie also zwei Variablen mit einer Potenz von 2 multiplizieren möchten, ist die Verschiebung möglicherweise besser.

a  *= 4;   // 
b  *= 4;   // 

a <<= 2;   // Both lines execute in a single cycle
b <<= 2;   // 
Raketenmagnet
quelle
5
+1 "Ob das Schalten schneller ist als das Multiplizieren, hängt von der Architektur Ihrer CPU ab." Vielen Dank, dass Sie sich ein wenig mit der Geschichte befasst haben und gezeigt haben, dass die meisten Computer-Mythen tatsächlich eine logische Grundlage haben.
Pharap
11

Sie haben mehrere Probleme mit Ihrem Testprogramm.

Erstens verwenden Sie nicht den Wert von test. Innerhalb des C-Standards gibt es keine Möglichkeit, dass der Wert von Bedeutung ist test. Dem Optimierer steht dies völlig frei, um es zu entfernen. Sobald es entfernt ist, ist Ihre Schleife tatsächlich leer. Der einzige sichtbare Effekt wäre das Setzen runs = 100000000, wird aber runsauch nicht genutzt. Der Optimierer kann (und sollte!) Also die gesamte Schleife entfernen. Einfache Lösung: Drucken Sie auch den berechneten Wert aus. Beachten Sie, dass ein ausreichend entschlossener Optimierer die Schleife immer noch optimieren kann (er stützt sich vollständig auf Konstanten, die zur Kompilierungszeit bekannt sind).

Zweitens führen Sie zwei Vorgänge aus, die sich gegenseitig aufheben. Der Optimierer darf dies bemerken und aufheben . Wieder eine leere Schleife verlassen und entfernt. Dieser ist ausgesprochen schwer zu beheben. Sie können zu einem wechseln unsigned int(Überlauf ist also kein undefiniertes Verhalten), aber das führt natürlich nur zu 0. Und einfache Dinge (wie zum Beispiel test += 1) sind für den Optimierer einfach genug, um es herauszufinden, und das tut es auch.

Schließlich nehmen Sie an, dass test *= 2tatsächlich eine Multiplikation kompiliert wird. Das ist eine sehr einfache Optimierung. Wenn die Bitverschiebung schneller ist, wird sie stattdessen vom Optimierer verwendet. Um dies zu umgehen, müssten Sie so etwas wie eine implementierungsspezifische Inline-Assembly verwenden.

Oder überprüfen Sie einfach Ihr Mikroprozessordatenblatt, um festzustellen, welches schneller ist.

Als ich die Assembly-Ausgabe beim Kompilieren Ihres Programms mit gcc -S -O3Version 4.9 überprüft habe , hat der Optimierer tatsächlich alle oben genannten einfachen Variationen und einige weitere durchgesehen. In allen Fällen wurde die Schleife entfernt (und eine Konstante testzugewiesen). Es blieben nur die Aufrufe von clock(), das Konvertieren / Subtrahieren und das printf.

derobert
quelle
1
Beachten Sie auch, dass der Optimierer Operationen für Konstanten (auch in einer Schleife) optimieren kann (und wird), wie in sqrt c # und sqrt c ++ gezeigt, in denen der Optimierer eine Schleife ersetzen konnte, die einen Wert durch die tatsächliche Summe summiert. Um diese Optimierung zu umgehen, müssen Sie etwas verwenden, das zur Laufzeit festgelegt wurde (z. B. ein Befehlszeilenargument).
@MichaelT Ja. Das ist, was ich mit "Beachten Sie, dass ein ausreichend entschlossener Optimierer die Schleife immer noch optimieren kann (er stützt sich vollständig auf Konstanten, die zur Kompilierungszeit bekannt sind)."
Derobert
Ich verstehe, was Sie sagen, aber ich glaube nicht, dass der Compiler die gesamte Schleife entfernt. Sie können diese Theorie einfach testen, indem Sie die Anzahl der Iterationen erhöhen. Sie werden feststellen, dass das Programm länger dauert, wenn Sie die Iterationen erhöhen. Wenn die Schleife vollständig entfernt worden wäre, wäre dies nicht der Fall.
DollarAkshay
@AkshayLAradhya Ich kann nicht sagen, was Ihr Compiler tut, aber ich habe erneut bestätigt, dass gcc -O3(jetzt mit 7.3) die Schleife immer noch vollständig entfernt wird. (Stellen Sie sicher, dass Sie bei Bedarf auf long anstelle von int umschalten, andernfalls wird es aufgrund eines Überlaufs zu einer Endlosschleife optimiert).
Derobert
8

Ich denke, es wäre hilfreicher, wenn der Fragesteller eine differenziertere Antwort hätte, da ich in den Fragen und in einigen Antworten oder Kommentaren mehrere ungeprüfte Annahmen sehe.

Die sich ergebende relative Laufzeit von Verschiebung und Multiplikation hat nichts mit C zu tun. Wenn ich C sage, meine ich nicht die Instanz einer bestimmten Implementierung, wie der oder jener Version von GCC, sondern die Sprache. Ich möchte das nicht absurd nehmen, sondern ein extremes Beispiel zur Veranschaulichung verwenden: Sie könnten einen vollständig standardkonformen C-Compiler implementieren und die Multiplikation eine Stunde dauern lassen, während das Verschieben Millisekunden dauert - oder umgekehrt. Mir sind solche Leistungseinschränkungen in C oder C ++ nicht bekannt.

Sie interessieren sich möglicherweise nicht für diese Technik in der Argumentation. Ihre Absicht war es wahrscheinlich, nur die relative Leistung von Shifts im Vergleich zu Multiplikationen zu testen, und Sie haben C gewählt, da es im Allgemeinen als Programmiersprache auf niedriger Ebene wahrgenommen wird, sodass man erwarten kann, dass der Quellcode direkter in entsprechende Anweisungen übersetzt wird. Solche Fragen sind sehr häufig und ich denke, eine gute Antwort sollte darauf hinweisen, dass selbst in C Ihr Quellcode nicht so direkt in Anweisungen übersetzt wird, wie Sie es in einem bestimmten Fall vielleicht denken. Ich habe Ihnen nachfolgend einige mögliche Kompilierungsergebnisse gegeben.

Hier kommen Kommentare ins Spiel, die die Nützlichkeit der Substitution dieser Äquivalenz in realer Software in Frage stellen. Sie können einige in den Kommentaren zu Ihrer Frage sehen, wie zum Beispiel den von Eric Lippert. Dies entspricht der Reaktion, die erfahrene Ingenieure auf solche Optimierungen im Allgemeinen erhalten. Wenn Sie im Produktionscode binäre Verschiebungen als umfassendes Mittel zum Multiplizieren und Dividieren verwenden, werden die Leute höchstwahrscheinlich an Ihrem Code zusammenzucken und eine gewisse emotionale Reaktion haben ("Ich habe gehört, dass diese unsinnige Behauptung über JavaScript um Himmels willen") Es mag für unerfahrene Programmierer keinen Sinn ergeben, wenn sie die Gründe für diese Reaktionen nicht besser verstehen.

Diese Gründe sind in erster Linie eine Kombination aus verminderter Lesbarkeit und Sinnlosigkeit einer solchen Optimierung, wie Sie vielleicht bereits beim Vergleich der relativen Leistung herausgefunden haben. Ich glaube jedoch nicht, dass die Menschen so stark reagieren würden, wenn die Substitution der Verschiebung durch die Multiplikation das einzige Beispiel für solche Optimierungen wäre. Fragen wie Ihre tauchen häufig in verschiedenen Formen und Zusammenhängen auf. Ich denke, dass mehr leitende Ingenieure tatsächlich so stark reagieren, zumindest manchmal, dass das Potenzial für ein viel breiteres Schadensspektrum besteht, wenn Menschen solche Mikrooptimierungen großzügig in der gesamten Codebasis einsetzen. Wenn Sie in einem Unternehmen wie Microsoft auf einer großen Codebasis arbeiten, verbringen Sie viel Zeit damit, den Quellcode anderer Ingenieure zu lesen, oder versuchen, bestimmten Code darin zu finden. Es kann sogar Ihr eigener Code sein, den Sie in ein paar Jahren zu verstehen versuchen, insbesondere zu einigen der ungünstigsten Zeiten, wenn Sie beispielsweise nach einem Anruf auf dem Pager einen Produktionsausfall beheben müssen Dienst am Freitagabend, um eine Nacht voller Spaß mit Freunden zu verbringen ... Wenn Sie so viel Zeit mit dem Lesen von Code verbringen, werden Sie es zu schätzen wissen, dass er so gut wie möglich lesbar ist. Stellen Sie sich vor, Sie lesen Ihren Lieblingsroman, aber der Verlag hat beschlossen, eine neue Ausgabe zu veröffentlichen, in der abbrv verwendet wird. alles über die plc bcs dein thnk es svs spc. Das ist vergleichbar mit den Reaktionen, die andere Ingenieure auf Ihren Code haben, wenn Sie sie mit solchen Optimierungen bestreuen. Wie andere Antworten gezeigt haben, ist es besser, klar zu sagen, was Sie meinen,

Selbst in diesen Umgebungen werden Sie möglicherweise eine Interviewfrage lösen, bei der Sie diese oder eine andere Entsprechung kennen müssen. Es ist nicht schlecht, sie zu kennen, und ein guter Ingenieur wäre sich des arithmetischen Effekts der binären Verschiebung bewusst. Beachten Sie, dass ich nicht gesagt habe, dass dies ein guter Ingenieur ist, aber dass ein guter Ingenieur es meiner Meinung nach wissen würde. Insbesondere finden Sie möglicherweise noch einen Manager, in der Regel gegen Ende Ihrer Interviewschleife, der Sie breit angrinst, um Ihnen diesen cleveren technischen "Trick" in einer Codierungsfrage zu enthüllen und zu beweisen, dass er / sie es ist Auch war oder ist er einer der versierten Ingenieure und nicht "nur" ein Manager. Versuchen Sie in solchen Situationen, beeindruckt auszusehen, und danken Sie ihm für das aufschlussreiche Interview.

Warum haben Sie in C keinen Geschwindigkeitsunterschied festgestellt? Die wahrscheinlichste Antwort ist, dass beide den gleichen Assembler-Code ergeben haben:

int shift(int i) { return i << 2; }
int multiply(int i) { return i * 2; }

Kann beides zusammenstellen in

shift(int):
    lea eax, [0+rdi*4]
    ret

Auf GCC ohne Optimierungen, dh unter Verwendung des Flags "-O0", erhalten Sie möglicherweise Folgendes:

shift(int):
    push    rbp
    mov rbp, rsp
    mov DWORD PTR [rbp-4], edi
    mov eax, DWORD PTR [rbp-4]
    sal eax, 2
    pop rbp
    ret
multiply(int):
    push    rbp
    mov rbp, rsp
    mov DWORD PTR [rbp-4], edi
    mov eax, DWORD PTR [rbp-4]
    add eax, eax
    pop rbp
    ret

Wie Sie sehen können, bedeutet die Übergabe von "-O0" an GCC nicht, dass es nicht klug ist, welche Art von Code erzeugt wird. Beachten Sie insbesondere, dass der Compiler auch in diesem Fall die Verwendung eines Multiplikationsbefehls vermieden hat. Sie können das gleiche Experiment mit Verschiebungen durch andere Zahlen und sogar Multiplikationen durch Zahlen, die keine Zweierpotenzen sind, wiederholen. Wahrscheinlich sehen Sie auf Ihrer Plattform eine Kombination aus Verschiebungen und Hinzufügungen, jedoch keine Multiplikationen. Es scheint ein Zufall zu sein, dass der Compiler in all diesen Fällen anscheinend die Verwendung von Multiplikationen vermeidet, wenn Multiplikationen und Verschiebungen tatsächlich die gleichen Kosten verursachen, nicht wahr? Aber ich will keine Vermutung als Beweis liefern, also lasst uns weitermachen.

Sie könnten Ihren Test mit dem obigen Code wiederholen und sehen, ob Sie jetzt einen Geschwindigkeitsunterschied bemerken. Selbst dann testen Sie nicht Shift versus Multiplikation, wie Sie an der fehlenden Multiplikation erkennen können, sondern den Code, der von GCC mit einer bestimmten Menge von Flags für die C-Operationen Shift und Multiplikation in einer bestimmten Instanz generiert wurde . In einem anderen Test können Sie also den Assembly-Code manuell bearbeiten und stattdessen eine "imul" -Anweisung im Code für die "multiplizieren" -Methode verwenden.

Wenn Sie einige dieser intelligenten Elemente des Compilers beseitigen möchten, können Sie eine allgemeinere Verschiebungs- und Multiplikationsmethode definieren, die am Ende ungefähr so ​​aussieht:

int shift(int i, int j) { return i << j; }
int multiply(int i, int j) { return i * j; }

Welche möglicherweise den folgenden Assemblycode ergeben:

shift(int, int):
    mov eax, edi
    mov ecx, esi
    sal eax, cl
    ret
multiply(int, int):
    mov eax, edi
    imul    eax, esi
    ret

Hier haben wir endlich, selbst auf der höchsten Optimierungsstufe von GCC 4.9, den Ausdruck in Montageanweisungen, den Sie erwartet haben, als Sie anfänglich mit Ihrem Test begannen. Ich denke, dass an sich eine wichtige Lektion bei der Leistungsoptimierung sein kann. Wir können den Unterschied sehen, den es gemacht hat, um Variablen für konkrete Konstanten in unserem Code zu ersetzen, in Bezug auf die Intelligenz, die der Compiler anwenden kann. Mikrooptimierungen wie die Umschalt-Multiplikations-Ersetzung sind einige sehr einfache Optimierungen, die ein Compiler normalerweise leicht selbst durchführen kann. Andere Optimierungen, die sich wesentlich stärker auf die Leistung auswirken, erfordern ein Verständnis der Absicht des CodesDas ist für den Compiler oft nicht zugänglich oder kann nur von einer Heuristik erraten werden. Hier kommen Sie als Softwareentwickler ins Spiel, und in der Regel müssen Multiplikationen nicht durch Verschiebungen ersetzt werden. Dabei geht es um Faktoren wie die Vermeidung eines redundanten Aufrufs eines Dienstes, der E / A erzeugt und einen Prozess blockieren kann. Wenn Sie zu Ihrer Festplatte gehen oder, Gott bewahre, zu einer entfernten Datenbank, um zusätzliche Daten zu erhalten, die Sie möglicherweise aus dem bereits vorhandenen Speicher erhalten haben, überwiegt die Zeit, die Sie für das Warten aufwenden, die Ausführung von einer Million Anweisungen. Nun, ich denke, wir sind ein bisschen weit von Ihrer ursprünglichen Frage entfernt, aber ich denke, wir weisen einen Fragesteller darauf hin, insbesondere wenn wir annehmen, dass jemand gerade erst anfängt, die Übersetzung und Ausführung von Code zu verstehen.

Also, welcher wird schneller sein? Ich denke, es ist ein guter Ansatz, den Sie gewählt haben, um den Leistungsunterschied tatsächlich zu testen. Im Allgemeinen ist es leicht, von der Laufzeitleistung einiger Codeänderungen überrascht zu werden. Es gibt viele Techniken, die moderne Prozessoren anwenden, und die Interaktion zwischen Software kann auch komplex sein. Selbst wenn Sie für eine bestimmte Änderung in einer Situation vorteilhafte Leistungsergebnisse erzielen sollten, ist es meines Erachtens gefährlich zu folgern, dass diese Art der Änderung immer zu Leistungsvorteilen führt. Ich halte es für gefährlich, solche Tests einmal durchzuführen und sage: "Okay, jetzt weiß ich, welcher schneller ist!" und wenden Sie dann wahllos dieselbe Optimierung auf den Produktionscode an, ohne Ihre Messungen zu wiederholen.

Was ist, wenn die Verschiebung schneller ist als die Multiplikation? Es gibt sicherlich Hinweise, warum dies zutreffen würde. Wie Sie oben sehen können, scheint GCC (auch ohne Optimierung) der Meinung zu sein, dass die Vermeidung einer direkten Multiplikation zugunsten anderer Anweisungen eine gute Idee ist. Das Referenzhandbuch zur Optimierung der Intel 64- und IA-32-Architekturen gibt Ihnen einen Überblick über die relativen Kosten von CPU-Anweisungen. Eine weitere Ressource, die sich mehr auf die Anweisungswartezeit und den Durchsatz konzentriert, ist http://www.agner.org/optimize/instruction_tables.pdf. Beachten Sie, dass sie kein guter Indikator für die absolute Laufzeit sind, sondern für die relative Ausführung von Anweisungen. In einer engen Schleife sollte, während Ihr Test simuliert, die Metrik des "Durchsatzes" am relevantesten sein. Dies ist die Anzahl der Zyklen, für die eine Ausführungseinheit normalerweise gebunden ist, wenn ein bestimmter Befehl ausgeführt wird.

Was ist, wenn die Verschiebung NICHT schneller ist als die Multiplikation? Wie bereits erwähnt, können moderne Architekturen sehr komplex sein, und Dinge wie Verzweigungsvorhersage, Caching, Pipelining und parallele Ausführungseinheiten können es schwierig machen, die relative Leistung von zwei logisch äquivalenten Codeteilen zuweilen vorherzusagen. Ich möchte das wirklich betonen, denn hier bin ich mit den meisten Antworten auf solche Fragen nicht zufrieden, und das Lager der Leute sagt geradezu, dass es (nicht mehr) einfach nicht wahr ist, dass das Schalten schneller ist als das Multiplizieren.

Nein, soweit mir bekannt ist, haben wir in den 1970er Jahren keine geheime Technik-Sauce erfunden oder wann immer die Kostenunterschiede zwischen einer Multiplikationseinheit und einem Bit-Shifter plötzlich aufgehoben werden sollten. Eine allgemeine Multiplikation in Bezug auf logische Gatter und sicherlich in Bezug auf logische Operationen ist in vielen Szenarien und auf vielen Architekturen immer noch komplexer als eine Verschiebung mit einem Barrel-Shifter. Wie sich dies in der Gesamtlaufzeit auf einem Desktop-Computer niederschlägt, ist möglicherweise etwas undurchsichtig. Ich weiß nicht genau, wie sie in bestimmten Prozessoren implementiert sind, aber hier ist eine Erklärung für eine Multiplikation: Ist die ganzzahlige Multiplikation wirklich die gleiche Geschwindigkeit wie die Addition auf einer modernen CPU?

Während hier eine Erklärung eines Barrel Shifter . Die Dokumente, auf die ich im vorigen Absatz verwiesen habe, geben einen anderen Überblick über die relativen Betriebskosten nach Proxy-Anweisungen der CPU. Die Ingenieure bei Intel scheinen häufig ähnliche Fragen zu haben: Intel Developer Zone Foren Taktzyklen für die ganzzahlige Multiplikation und Addition in Core-2-Duo-Prozessor

Ja, in den meisten realen Szenarien und mit ziemlicher Sicherheit in JavaScript ist der Versuch, diese Äquivalenz aus Gründen der Leistung auszunutzen, wahrscheinlich ein vergebliches Unterfangen. Auch wenn wir die Verwendung von Multiplikationsanweisungen erzwungen haben und dann keinen Laufzeitunterschied festgestellt haben, liegt dies eher an der Art der von uns verwendeten Kostenmetrik, genauer gesagt, und nicht daran, dass es keinen Kostenunterschied gibt. End-to-End-Laufzeit ist eine Metrik und wenn es die einzige ist, die uns interessiert, ist alles in Ordnung. Das heißt aber nicht, dass alle Kostenunterschiede zwischen Multiplikation und Verschiebung einfach verschwunden sind. Und ich denke, es ist sicherlich keine gute Idee, diese Idee implizit oder auf andere Weise einem Fragesteller zu übermitteln, der offensichtlich gerade erst anfängt, eine Vorstellung von den Faktoren zu bekommen, die mit der Laufzeit und den Kosten des modernen Codes zusammenhängen. Beim Engineering geht es immer um Kompromisse. Die Untersuchung und Erklärung, welche Kompromisse moderne Prozessoren gemacht haben, um die Ausführungszeit zu zeigen, die wir als Benutzer am Ende sehen, kann eine differenziertere Antwort liefern. Und ich denke, eine differenziertere Antwort als "das ist einfach nicht mehr wahr" ist gerechtfertigt, wenn weniger Ingenieure die Lesbarkeit von mikrooptimiertem Code auslöschen wollen, weil ein allgemeineres Verständnis der Art solcher "Optimierungen" erforderlich ist Finden Sie die verschiedenen, unterschiedlichen Inkarnationen, als sich lediglich auf bestimmte veraltete Instanzen zu beziehen.

user2880576
quelle
6

Was Sie sehen, ist die Wirkung des Optimierers.

Die Aufgabe des Optimierers ist es, den resultierenden kompilierten Code entweder kleiner oder schneller zu machen (aber selten beides gleichzeitig ... aber wie viele Dinge ... ES HÄNGT davon ab, was der Code ist).

In PRINCIPLE ist jeder Aufruf einer Multiplikationsbibliothek oder häufig sogar die Verwendung eines Hardware-Multiplikators langsamer als nur eine bitweise Verschiebung.

Also ... wenn der naive Compiler einen Aufruf an eine Bibliothek für die Operation * 2 generieren würde, würde diese natürlich langsamer als eine bitweise Verschiebung * ablaufen.

Optimierer sind jedoch dazu da, Muster zu erkennen und herauszufinden, wie der Code kleiner / schneller / was auch immer gemacht werden kann. Und was Sie gesehen haben, ist der Compiler, der feststellt, dass * 2 dasselbe ist wie eine Verschiebung.

Nur aus Interesse habe ich mir heute den generierten Assembler für einige Operationen wie * 5 ... angesehen, aber nicht für andere Dinge. Dabei ist mir aufgefallen, dass der Compiler aus * 5 Folgendes gemacht hat:

  • Verschiebung
  • Verschiebung
  • fügen Sie die ursprüngliche Nummer hinzu

Der Optimierer meines Compilers war also intelligent genug (zumindest für bestimmte kleine Konstanten), um Inline-Verschiebungen zu generieren und einer universellen Multiplikationsbibliothek statt Aufrufe hinzuzufügen.

Die Kunst der Compiler-Optimierer ist ein ganz eigenes Thema, voller Magie und wird von ungefähr 6 Menschen auf dem ganzen Planeten wirklich richtig verstanden :)

schnell_nun
quelle
3

Versuchen Sie es mit Timing:

for (runs = 0; runs < 100000000; runs++) {
      ;
}

Der Compiler sollte erkennen, dass der Wert von test nach jeder Iteration der Schleife unverändert bleibt und der Endwert von testnicht verwendet wird, und die Schleife vollständig entfernen.

Russell Borogove
quelle
2

Die Multiplikation ist eine Kombination aus Verschiebungen und Additionen.

In dem Fall, den Sie erwähnt haben, glaube ich nicht, dass es wichtig ist, ob der Compiler ihn optimiert oder nicht - "multiplizieren Sie x mit zwei" kann wie folgt implementiert werden:

  • Bits von verschieben x eine Stelle nach links.
  • Hinzufügen xzu x.

Dies sind jeweils grundlegende atomare Operationen; einer ist nicht schneller als der andere.

Ändern Sie es in "Multiplizieren xmit vier" (oder 2^k, k>1eine andere) und es ist ein wenig anders:

  • Bits von verschieben x zwei Stellen nach links.
  • In xan xund nennen Sie es y, fügen Sie yzu y.

Auf einer Basisarchitektur ist es einfach zu erkennen, dass die Verschiebung effizienter ist - es werden ein oder zwei Operationen ausgeführt, da wir nichts hinzufügen können y, ybis wir wissen, was yist.

Probieren Sie Letzteres (oder eines davon 2^k, k>1) mit geeigneten Optionen aus, um zu verhindern, dass Sie die Optimierung so durchführen, dass sie bei der Implementierung identisch ist. Sie sollten feststellen, dass die Verschiebung schneller ist, O(1)verglichen mit der wiederholten Hinzufügung von O(k).

Wenn der Multiplikand keine Zweierpotenz ist, ist offensichtlich eine Kombination von Verschiebungen und Additionen (eine, bei der die Anzahl von beiden nicht Null ist) erforderlich.

OJFord
quelle
1
Was ist eine "grundlegende atomare Operation"? Könnte man nicht argumentieren, dass in einer Verschiebung die Operation auf jedes Bit parallel angewendet werden kann, während in einer Addition die Bits ganz links von den anderen Bits abhängen?
Bergi
2
@Bergi: Ich vermute, er bedeutet, dass sowohl shift als auch add einzelne Maschinenbefehle sind. Sie müssten sich die Dokumentation des Anweisungssatzes ansehen, um die Anzahl der Zyklen für jeden Befehl zu ermitteln. Ja, eine Addition ist häufig eine Operation mit mehreren Zyklen, wohingegen eine Schicht normalerweise in einem einzigen Zyklus ausgeführt wird.
TMN
Ja, das könnte der Fall sein, aber Multiplikation ist auch eine einzelne Maschinenanweisung (obwohl es natürlich mehr Zyklen
erfordern
@Bergi, auch das ist bogenabhängig. Welcher Bogen verschiebt sich Ihrer Meinung nach in weniger Zyklen als die 32-Bit-Addition (oder, falls zutreffend, das x-Bit)?
OJFord
Ich kenne keine bestimmten Architekturen, nein (und meine Computerkurse sind verblasst), wahrscheinlich dauern beide Anweisungen weniger als einen Zyklus. Ich dachte wahrscheinlich an Mikrocode oder sogar Logikgatter, wo eine Verschiebung wahrscheinlich billiger wäre.
Bergi
1

Die Multiplikation von vorzeichenbehafteten oder vorzeichenlosen Werten mit Zweierpotenzen entspricht einer Linksverschiebung, und die meisten Compiler werden diese ersetzen. Division von vorzeichenlosen Werten oder vorzeichenbehafteten Werten, die der Compiler nachweisen kann, ist niemals negativ . Dies entspricht einer Verschiebung nach rechts, und die meisten Compiler führen diese Substitution durch (obwohl einige nicht ausreichend ausgefeilt sind, um zu beweisen, dass vorzeichenbehaftete Werte nicht negativ sein können). .

Es ist jedoch zu beachten, dass die Aufteilung der potenziell negativ vorzeichenbehafteten Werte nicht der Verschiebung nach rechts entspricht. Ein Ausdruck wie (x+8)>>4ist nicht gleichbedeutend mit (x+8)/16. Ersterer ordnet in 99% der Compiler Werte von -24 bis -9 bis -1, -8 bis +7 bis 0 und +8 bis +23 bis 1 zu [rundet die Zahlen nahezu symmetrisch um Null]. Letzteres wird -39 bis -24 bis -1, -23 bis +7 bis 0 und +8 bis +23 bis +1 abbilden [grob asymmetrisch und wahrscheinlich nicht das, was beabsichtigt war]. Beachten Sie, dass die Verwendung von >>4wahrscheinlich auch dann schnelleren Code liefert , wenn nicht erwartet wird, dass die Werte negativ sind, als /16wenn der Compiler nachweisen kann, dass die Werte nicht negativ sein können.

Superkatze
quelle
0

Einige weitere Infos habe ich gerade ausgecheckt.

Auf x86_64 hat der MUL-Opcode eine Latenzzeit von 10 Zyklen und einen Durchsatz von 1/2 Zyklus. MOV, ADD und SHL haben eine Latenz von 1 Zyklus mit einem Durchsatz von 2,5, 2,5 und 1,7 Zyklen.

Eine Multiplikation mit 15 würde mindestens 3 SHL- und 3 ADD-Operationen und wahrscheinlich ein paar MOVs erfordern.

https://gmplib.org/~tege/x86-timing.pdf

Rich Remer
quelle
0

Ihre Methodik ist fehlerhaft. Die Überprüfung des Schleifenzuwachses und des Zustands selbst nimmt so viel Zeit in Anspruch.

  • Führen Sie eine leere Schleife aus und messen Sie die Zeit (nennen Sie es base).
  • Fügen Sie nun 1 Schicht hinzu und messen Sie die Zeit (nennen Sie es s1).
  • Fügen Sie als nächstes 10 Schichtoperationen hinzu und messen Sie die Zeit (call it s2)

Wenn alles richtig läuft base-s2sollte das 10 mal mehr sein als base-s1. Ansonsten kommt hier etwas anderes ins Spiel.

Jetzt habe ich es selbst versucht und herausgefunden, wenn Schleifen ein Problem verursachen, warum sie nicht vollständig entfernen. Also ging ich voran und tat dies:

int main(){

    int test = 2;
    clock_t launch = clock();

    test << 6;
    test << 6;
    test << 6;
    test << 6;
    //.... 1 million times
    test << 6;

    clock_t done = clock();
    printf("Time taken : %d\n", done - launch);
    return 0;
}

Und da haben Sie Ihr Ergebnis

1 Million Schichtoperationen in weniger als 1 Millisekunde?.

Ich habe das gleiche für die Multiplikation mit 64 gemacht und das gleiche Ergebnis erzielt. Wahrscheinlich ignoriert der Compiler die Operation vollständig, da andere erwähnt haben, dass der Wert von test niemals geändert wird.

Ergebnis des Operators "Shiftwise"

DollarAkshay
quelle