Was ist schneller: x << 1 oder x << 10?

83

Ich möchte nichts optimieren, ich schwöre, ich möchte diese Frage nur aus Neugier stellen. Ich weiß , dass auf den meist Hardware gibt es einen Montag Befehl von Bit-Verschiebung (zB shl, shr), die ein einziger Befehl ist. Aber spielt es eine Rolle (in Bezug auf Nanosekunden oder CPU-Takt), wie viele Bits Sie verschieben? Mit anderen Worten, ist eine der folgenden Funktionen auf einer CPU schneller?

x << 1;

und

x << 10;

Und bitte hasse mich nicht für diese Frage. :) :)

c++ c performance cpu low-level Armen Tsirunyan
quelle
17
Omg, ich warf einen Blick auf den Code und mein erster Gedanke war "Stream Printing Operators". Ich brauche eine Pause.
Kos
4
Ich glaube, ich höre jemanden in ihren Gedanken schwach "vorzeitige Optimierung" sagen, oder vielleicht nur meine Vorstellungskraft.
Tia
5
@tia er sagte, er würde nichts optimieren :)
1
@Grigory ja und deshalb sehen wir hier niemanden, der die Frage mit diesem Satz überspringt. : D
tia
1
Als Randnotiz: Ich habe kürzlich erkannt, dass das Verschieben nach links und nach rechts nicht unbedingt dieselbe CPU-Zeit verbraucht. In meinem Fall war das Verschieben nach rechts viel langsamer. Zuerst war ich überrascht, aber ich denke, die Antwort ist, dass das Verschieben nach links logisch und das Verschieben nach rechts vielleicht arithmetisch bedeutet: stackoverflow.com/questions/141525/…
Christian Ammer

Antworten:

84

Hängt möglicherweise von der CPU ab.

Alle modernen CPUs (x86, ARM) verwenden jedoch einen "Barrel Shifter" - ein Hardwaremodul, das speziell für beliebige Verschiebungen in konstanter Zeit entwickelt wurde.

Das Endergebnis ist also ... nein. Kein Unterschied.

Nimrodm
quelle
21
Großartig, jetzt habe ich ein Bild davon, wie ich meiner CPU sage, dass sie eine in meinem Kopf steckende Fassrolle machen soll ...
Ignacio Vazquez-Abrams
11
Errr - SEHR VIEL hängt vom Prozessor ab. Bei einigen Prozessoren ist dies eine konstante Zeit. Bei anderen kann es sich um einen Zyklus pro Schicht handeln (ich habe einmal eine Schicht um etwa 60.000 Stellen verwendet, um die Prozessortaktrate s / w zu messen). Auf anderen Prozessoren gibt es möglicherweise nur Anweisungen für Einzelbitverschiebungen. In diesem Fall wird eine Mehrbitverschiebung an eine Bibliotheksroutine delegiert, die sich in einer Schleife befindet, die weg iteriert.
schnell_now
4
@quickly_now: Das ist sicher eine schlechte Methode, um die Taktrate zu messen. Kein Prozessor ist dumm genug, um tatsächlich 60.000 Schichten zu machen. das wird einfach konvertiert 60000 mod register_size. Beispielsweise verwendet ein 32-Bit-Prozessor nur die 5 niedrigstwertigen Bits der Verschiebungsanzahl.
Casablanca
4
Der Inmos-Transputer hatte einen Shift-Operator, der die Anzahl der Shifts als 32-Bit-Operanden verwendete. Sie könnten 4 Milliarden Schichten machen, wenn Sie wollten, zu je 1 Uhr. "Kein Prozessor ist dumm genug". Tut mir leid, falsch. Dieser tat es. Sie mussten diesen Teil jedoch im Assembler codieren. Die Compiler haben eine sinnvolle Änderung / Optimierung vorgenommen (setzen Sie das Ergebnis einfach auf 0, tun Sie nichts).
schnell_now
5
Pentium 4 verlor leider den Barrel Shifter, was zu seiner insgesamt schlechten Befehlsrate pro Takt beitrug. Ich gehe davon aus, dass die Core Blah-Architektur es zurückbekommen hat.
Russell Borogove
64

Einige eingebettete Prozessoren haben nur eine "Shift-by-One" -Anweisung. Auf solchen Prozessoren, würde der Compiler ändert x << 3in ((x << 1) << 1) << 1.

Ich denke, das Motorola MC68HCxx war eine der beliebtesten Familien mit dieser Einschränkung. Glücklicherweise sind solche Architekturen mittlerweile recht selten, die meisten enthalten jetzt einen Barrel Shifter mit variabler Schaltgröße.

Der Intel 8051, der über viele moderne Derivate verfügt, kann auch keine beliebige Anzahl von Bits verschieben.

Ben Voigt
quelle
12
Bei eingebetteten Mikrocontrollern immer noch üblich.
Ben Jackson
4
Was meinst du mit "selten"? Entsprechend der Statistik ist die Anzahl der verkauften 8-Bit-Mikrocontroller größer als die Anzahl aller anderen MPU-Typen.
Vovanium
8-Bit-Mikrocontroller werden nicht viel für Neuentwicklungen verwendet, wenn Sie 16-Bit für den gleichen Preis pro Einheit (z. B. MSP430 von TI) mit mehr Programm-ROM, mehr Arbeitsspeicher und mehr Funktionen erhalten können. Und sogar einige 8-Bit-Mikrocontroller haben Barrel Shifter.
Ben Voigt
1
Die Wortgröße eines Mikrocontrollers hat nichts damit zu tun, ob er einen Barrel Shifter hat. Die von mir erwähnte MC68HCxx-Familie verfügt ebenfalls über 16-Bit-Prozessoren, die alle nur eine Bitposition auf einmal verschieben.
Ben Voigt
Tatsache, dass die meisten 8-Bit-MCUs keinen Barrel Shifter haben, obwohl Sie Recht haben, dass es solche gibt, für die dies nicht der Fall ist, und es keine 8-Bit-MCUs ohne Barrel Shifter gibt. Bitness erhielt als zuverlässige Annäherung für Maschinen mit [out] Barrel Shifter. Auch die Tatsache, dass der CPU-Kern für die MCU häufig keine Wahl für das Modell trifft, aber On-Chip-Peripheriegeräte. Und 8-Bit werden oft für reichhaltigere Peripheriegeräte zum gleichen Preis gewählt.
Vovanium
29

Es gibt viele Fälle dazu.

  1. Viele Hochgeschwindigkeits-MPUs verfügen über eine Multiplexer-ähnliche elektronische Schaltung mit Barrel Shifter, die jede Verschiebung in konstanter Zeit ausführt.

  2. Wenn MPU nur eine 1-Bit-Verschiebung haben, ist x << 10dies normalerweise langsamer, da dies meistens durch 10 Verschiebungen oder Byte-Kopieren mit 2 Verschiebungen erfolgt.

  3. Es ist jedoch ein häufiger Fall bekannt, bei dem x << 10noch schneller als x << 1. Wenn x 16 Bit ist, sind nur die unteren 6 Bit davon betroffen (alle anderen werden herausgeschoben), sodass die MPU nur ein niedrigeres Byte laden muss, um nur einen einzelnen Zugriffszyklus auf den 8-Bit-Speicher durchzuführen, während x << 10zwei Zugriffszyklen erforderlich sind. Wenn der Zugriffszyklus langsamer als die Verschiebung ist (und das untere Byte löscht),x << 10 ist er schneller. Dies kann für Mikrocontroller mit schnellem Programm-ROM gelten, die auf langsamen externen Daten-RAM zugreifen.

  4. Zusätzlich zu Fall 3 kann sich der Compiler um die Anzahl der signifikanten Bits kümmern x << 10und weitere Operationen auf solche mit geringerer Breite optimieren, z. B. das Ersetzen der 16x16-Multiplikation durch die 16x8-Eins (da das untere Byte immer Null ist).

Beachten Sie, dass einige Mikrocontroller überhaupt keine Anweisung zum Verschieben nach links haben, sondern add x,xstattdessen verwenden.

Vovanium
quelle
Ich verstehe nicht, warum x << 10 schneller ist als x << 8, wo in x << 8 Sie eine Last aus dem unteren Byte von 16 Bit machen müssen und nicht laden und zwei Verschiebungen. Ich verstehe es nicht.
keine
3
@none: Ich habe nicht angegeben, dass x << 10 schneller als x << 8 ist.
Vovanium
9

Auf ARM kann dies als Nebeneffekt einer anderen Anweisung erfolgen. Daher gibt es für beide möglicherweise überhaupt keine Latenz.

eine Masse
quelle
1
Werden die Anweisungen in der gleichen Anzahl von Zyklen ausgeführt? Bei einigen Architekturen wird derselbe Befehl basierend auf den Operanden in einige verschiedene Operationscodes übersetzt und dauert zwischen 1 und 5 Zyklen.
Nick T
@Nick Ein ARM-Befehl dauert im Allgemeinen zwischen 1 und 2 Zyklen. Ich bin mir bei den neueren Architekturen nicht sicher.
Onemasse
2
@ Nick T: Er spricht über ARM, die sich nicht als dedizierte Anweisung, sondern als "Merkmal" vieler Datenverarbeitungsanweisungen verschieben. Dh ADD R0, R1, R2 ASL #3addiert R1 und R2 um 3 Bits nach links verschoben.
Vovanium
9

Hier ist meine Lieblings-CPU , die x<<2doppelt so lange dauert wie x<<1:)

Mike Dunlavey
quelle
Leider gibt es keine Nibble-Swap-Anweisung wie 8051, PIC oder AVR, daher kann der Optimierungstrick nicht angewendet werden
phuclv
7

Das hängt sowohl von der CPU als auch vom Compiler ab. Selbst wenn die zugrunde liegende CPU eine willkürliche Bitverschiebung mit einem Barrel Shifter aufweist, geschieht dies nur, wenn der Compiler diese Ressource nutzt.

Beachten Sie, dass das Verschieben von Daten außerhalb der Breite in Datenbits in C und C ++ "undefiniertes Verhalten" ist. Die Rechtsverschiebung signierter Daten wird ebenfalls als "Implementierung definiert" bezeichnet. Anstatt sich über die Geschwindigkeit Gedanken zu machen, sollten Sie sich Sorgen machen, dass Sie bei verschiedenen Implementierungen dieselbe Antwort erhalten.

Zitat aus ANSI C Abschnitt 3.3.7:

3.3.7 Bitweise Verschiebungsoperatoren

Syntax

      shift-expression:
              additive-expression
              shift-expression <<  additive-expression
              shift-expression >>  additive-expression

Einschränkungen

Jeder der Operanden muss einen integralen Typ haben.

Semantik

Die integralen Promotions werden für jeden der Operanden durchgeführt. Der Typ des Ergebnisses ist der des heraufgestuften linken Operanden. Wenn der Wert des rechten Operanden negativ ist oder größer oder gleich der Breite in Bits des heraufgestuften linken Operanden ist, ist das Verhalten undefiniert.

Das Ergebnis von E1 << E2 sind E1 linksverschobene E2-Bitpositionen; Leerzeichen werden mit Nullen gefüllt. Wenn E1 einen vorzeichenlosen Typ hat, wird der Wert des Ergebnisses E1 multipliziert mit der Menge, 2 erhöht auf die Potenz E2, reduziert modulo ULONG_MAX + 1, wenn E1 einen vorzeichenlosen Typ hat, andernfalls UINT_MAX + 1. (Die Konstanten ULONG_MAX und UINT_MAX sind im Header definiert.)

Das Ergebnis von E1 >> E2 sind E1 rechtsverschobene E2-Bitpositionen. Wenn E1 einen vorzeichenlosen Typ hat oder wenn E1 einen vorzeichenbehafteten Typ und einen nichtnegativen Wert hat, ist der Wert des Ergebnisses der integrale Teil des Quotienten von E1 geteilt durch die Menge 2, die zur Potenz E2 erhöht wird. Wenn E1 einen vorzeichenbehafteten Typ und einen negativen Wert hat, ist der resultierende Wert implementierungsdefiniert.

So:

x = y << z;

"<<": y × 2 z ( undefiniert, wenn ein Überlauf auftritt);

x = y >> z;

">>": implementierungsdefiniert für signiert (meistens das Ergebnis der arithmetischen Verschiebung: y / 2 z ).

der Wolf
quelle
Ich glaube nicht, dass 1u << 100es UB ist. Es ist nur 0.
Armen Tsirunyan
@Armen Tsirunyan: Eine Bitverschiebung 1u << 100als Bitverschiebung kann ein Überlauf sein. 1u << 100als arithmetische Verschiebung ist 0. Unter ANSI C <<ist eine Bitverschiebung. en.wikipedia.org/wiki/Arithmetic_shift
der Wolf
2
@Armen Tsirunyan: Siehe ANSI-Abschnitt 3.3.7 - Wenn der Wert des rechten Operanden negativ ist oder größer oder gleich der Breite in Bits des heraufgestuften linken Operanden ist, ist das Verhalten undefiniert. Ihr Beispiel ist also UB auf jedem ANSI C-System, es sei denn, es gibt einen 101+ Bit-Typ.
Der Wolf
@ Karotten-Topf: OK, Sie haben mich überzeugt :)
Armen Tsirunyan
Verwandte Themen: x << (y & 31)Kann weiterhin ohne UND-Befehl zu einem einzelnen Shift-Befehl kompiliert werden, wenn der Compiler weiß, dass der Shift-Befehl der Zielarchitektur die Anzahl maskiert (wie bei x86). (Codieren Sie die Maske vorzugsweise nicht fest, sondern holen Sie sie ab CHAR_BIT * sizeof(x) - 1oder so.) Dies ist nützlich, um eine Rotationssprache zu schreiben, die unabhängig von den Eingaben zu einem einzelnen Befehl ohne C UB kompiliert wird. ( stackoverflow.com/questions/776508/… ).
Peter Cordes
7

Es ist denkbar, dass auf einem 8-Bit-Prozessor x<<1tatsächlich viel langsamer sein könnte alsx<<10 bei einem 16-Bit-Wert.

Zum Beispiel kann eine vernünftige Übersetzung von x<<1sein:

byte1 = (byte1 << 1) | (byte2 >> 7)
byte2 = (byte2 << 1)

wohingegen x<<10einfacher wäre:

byte1 = (byte2 << 2)
byte2 = 0

Beachten Sie, wie x<<1sich häufiger und sogar weiter verschiebt als x<<10. Darüber hinaus x<<10hängt das Ergebnis von nicht vom Inhalt von byte1 ab. Dies könnte den Betrieb zusätzlich beschleunigen.

Robert
quelle
5

Bei einigen Generationen von Intel-CPUs (P2 oder P3? Nicht AMD, wenn ich mich recht erinnere) sind die Bitshift-Operationen lächerlich langsam. Bitshift um 1 Bit sollte jedoch immer schnell sein, da nur Addition verwendet werden kann. Eine weitere zu berücksichtigende Frage ist, ob Bitverschiebungen um eine konstante Anzahl von Bits schneller sind als Verschiebungen mit variabler Länge. Selbst wenn die Opcodes die gleiche Geschwindigkeit haben, muss auf x86 der nicht konstante rechte Operand einer Bitverschiebung das CL-Register belegen, was der Registerzuweisung zusätzliche Einschränkungen auferlegt und das Programm möglicherweise auch auf diese Weise verlangsamt.

R .. GitHub HÖREN SIE AUF, EIS ZU HELFEN
quelle
1
Das ist Pentium 4. Von PPro abgeleitete CPUs (wie P2 und P3) haben schnelle Verschiebungen. Und ja, Verschiebungen mit variabler Anzahl auf x86 sind langsamer als sie sein könnten, es sei denn, Sie können BMI2 shlx/ shrx/ verwenden sarx(Haswell und höher und Ryzen). Die CISC-Semantik (Flags unverändert, wenn count = 0) hat hier x86 verletzt. shl r32, clist 3 Uops in der Sandybridge-Familie (obwohl Intel behauptet, dass es eines der Uops abbrechen kann, wenn das Flag-Ergebnis nicht verwendet wird). AMD hat Single-Uop shl r32, cl(aber langsame Doppelschaltung für erweiterte Präzision shld r32, r32, cl)
Peter Cordes
1
Schichten (sogar mit variabler Anzahl) sind nur ein einziges Uop in der P6-Familie, aber das Lesen des Flag-Ergebnisses von shl r32, cloder mit einer anderen als 1 blockiert das Front-End, bis die Schicht in den Ruhestand geht! ( stackoverflow.com/questions/36510095/… ). Compiler wissen dies und verwenden einen separaten testBefehl, anstatt das Flag-Ergebnis einer Verschiebung zu verwenden. (Aber dies verschwendet Anweisungen auf CPUs, wo es kein Problem ist, siehe stackoverflow.com/questions/40354978/… )
Peter Cordes
3

Wie immer hängt es vom umgebenden Codekontext ab : Verwenden Sie z. x<<1B. einen Array-Index? Oder es zu etwas anderem hinzufügen? In beiden Fällen kleine Verschiebung Zählungen (1 oder 2) kann oft optimize sogar mehr , als wenn die Compiler Enden bis zu mit nur verschieben muss. Ganz zu schweigen vom Kompromiss zwischen Durchsatz und Latenz und Front-End-Engpässen. Die Leistung eines winzigen Fragments ist nicht eindimensional.

Eine Hardware-Shift-Anweisung ist nicht die einzige Option eines Compilers zum Kompilieren x<<1, aber die anderen Antworten gehen meistens davon aus.

x << 1 ist genau gleichbedeutend mit x+x für vorzeichenlose und für 2-Komplement-vorzeichenbehaftete Ganzzahlen. Compiler wissen beim Kompilieren immer, auf welche Hardware sie abzielen, damit sie solche Tricks nutzen können.

Auf Intel Haswell , addverfügt über 4 pro Takt Durchsatz, aber shlmit einer sofortigen Zählung hat nur 2 pro Takt Durchsatz. (Sehen Anweisungen und andere Links finden http://agner.org/optimize/x86Tag Wiki). SIMD-Vektorverschiebungen betragen 1 pro Takt (2 in Skylake), aber SIMD-Vektor-Integer-Additionen betragen 2 pro Takt (3 in Skylake). Die Latenz ist jedoch dieselbe: 1 Zyklus.

Es gibt auch eine spezielle Shift-by-One-Codierung, bei der angegeben wird, shlwo die Anzahl im Opcode enthalten ist. 8086 hatte keine Schichten mit sofortiger Zählung, nur nacheinander und nach clRegister. Dies ist hauptsächlich für Rechtsverschiebungen relevant, da Sie nur für Linksverschiebungen hinzufügen können, es sei denn, Sie verschieben einen Speicheroperanden. Wenn der Wert jedoch später benötigt wird, ist es besser, zuerst in ein Register zu laden. Aber trotzdem shl eax,1oder add eax,eaxist ein Byte kürzer als shl eax,10, und die Codegröße kann direkt (Decodierungs- / Front-End-Engpässe) oder indirekt (L1I-Code-Cache-Fehler) die Leistung beeinträchtigen.

Im Allgemeinen können kleine Verschiebungszahlen manchmal in einem Adressierungsmodus auf x86 in einen skalierten Index optimiert werden. Die meisten anderen heutzutage gebräuchlichen Architekturen sind RISC-Architekturen und verfügen nicht über Adressierungsmodi für skalierte Indizes. X86 ist jedoch eine Architektur, die häufig genug ist, um dies zu erwähnen. (Ei, wenn Sie ein Array von 4-Byte-Elementen indizieren, können Sie den Skalierungsfaktor um 1 erhöhen int arr[]; arr[x<<1]).

Das Kopieren + Verschieben ist in Situationen üblich, in denen der ursprüngliche Wert von xnoch benötigt wird. Die meisten x86-Integer-Anweisungen werden jedoch direkt ausgeführt. (Das Ziel ist eine der Quellen für Anweisungen wie addoder shl.) Die x86-64-System V-Aufrufkonvention übergibt Argumente in Registern mit dem ersten Argument in ediund dem Rückgabewert in eax, sodass x<<10der Compiler bei einer zurückgegebenen Funktion auch copy + shift ausgibt Code.

Mit der LEAAnweisung können Sie verschieben und hinzufügen (mit einer Verschiebungsanzahl von 0 bis 3, da die Maschinencodierung im Adressierungsmodus verwendet wird). Das Ergebnis wird in einem separaten Register abgelegt.

gcc und clang optimieren diese Funktionen auf dieselbe Weise, wie Sie im Godbolt-Compiler-Explorer sehen können :

int shl1(int x) { return x<<1; }
    lea     eax, [rdi+rdi]   # 1 cycle latency, 1 uop
    ret

int shl2(int x) { return x<<2; }
    lea     eax, [4*rdi]    # longer encoding: needs a disp32 of 0 because there's no base register, only scaled-index.
    ret

int times5(int x) { return x * 5; }
    lea     eax, [rdi + 4*rdi]
    ret

int shl10(int x) { return x<<10; }
    mov     eax, edi         # 1 uop, 0 or 1 cycle latency
    shl     eax, 10          # 1 uop, 1 cycle latency
    ret

LEA mit 2 Komponenten hat eine Latenz von 1 Zyklus und einen Durchsatz von 2 pro Takt auf neueren Intel- und AMD-CPUs. (Sandybridge-Familie und Bulldozer / Ryzen). Unter Intel ist es nur 1 Durchsatz pro Takt mit 3c Latenz für lea eax, [rdi + rsi + 123]. (Siehe auch : Warum ist der C ++ Code schneller als meine handschriftliche Versammlung für die Vermutung Collatz testen? Geht in dieser im Detail.)

Auf jeden Fall benötigt Kopieren + Verschieben um 10 eine separate movAnweisung. Bei vielen neueren CPUs ist die Latenz möglicherweise null, es werden jedoch immer noch Front-End-Bandbreite und Codegröße benötigt. ( Kann der MOV von x86 wirklich "kostenlos" sein? Warum kann ich das überhaupt nicht reproduzieren? )

Ebenfalls verwandt: Wie multipliziere ich ein Register mit 37 mit nur 2 aufeinanderfolgenden Leal-Anweisungen in x86? .

Dem Compiler steht es auch frei, den umgebenden Code so zu transformieren, dass keine tatsächliche Verschiebung erfolgt oder er mit anderen Operationen kombiniert wird .

Zum Beispiel if(x<<1) { }könnte ein verwendet werden and, um alle Bits außer dem hohen Bit zu überprüfen. Auf x86 würden Sie eine testAnweisung wie test eax, 0x7fffffff/ jz .falseanstelle von verwenden shl eax,1 / jz. Diese Optimierung funktioniert für jede Schichtanzahl und auch für Maschinen, bei denen große Schichten langsam (wie Pentium 4) oder nicht vorhanden (einige Mikrocontroller) sind.

Viele ISAs verfügen über Anweisungen zur Bitmanipulation, die über das reine Verschieben hinausgehen. zB PowerPC hat viele Anweisungen zum Extrahieren / Einfügen von Bitfeldern. Oder ARM hat Verschiebungen von Quelloperanden als Teil eines anderen Befehls. (Verschiebungs- / Drehanweisungen sind also nur eine spezielle Form der moveVerwendung einer verschobenen Quelle.)

Denken Sie daran, C ist keine Assemblersprache . Achten Sie immer auf die optimierte Compilerausgabe, wenn Sie Ihren Quellcode so optimieren , dass er effizient kompiliert.

Peter Cordes
quelle