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

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?

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.

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

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;   // 

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.

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.

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 :)

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.

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.

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.

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

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.