Verschiebt Bits schneller als Multiplizieren und Dividieren in Java? .NETZ?

Question

Verschieben von Bits nach links und rechts ist offenbar schneller als Multiplikation und Division Operationen auf den meisten, vielleicht sogar alle CPUs, wenn Sie eine Potenz von 2 jedoch zu verwenden passieren, kann es die Klarheit des Codes für einige Leser und einige Algorithmen zu reduzieren. Ist Bit-Shifting wirklich notwendig für die Performance, oder kann ich erwarten, dass der Compiler oder die VM den Fall bemerkt und ihn optimiert (insbesondere wenn die Potenz von 2 ein Literal ist)? Ich interessiere mich hauptsächlich für das Java- und .NET-Verhalten, begrüße aber auch Einblicke in andere Sprachimplementierungen.

Answer 1

Die meisten Compiler werden heute mehr tun, als Multiplizieren oder Dividieren durch eine Zweierpotenz in Schichtoperationen. Beim Optimieren können viele Compiler eine Multiplikation oder Division mit einer Kompilierzeitkonstante optimieren, auch wenn sie keine Potenz von 2 ist. Oft kann eine Multiplikation oder Division in eine Reihe von Verschiebungen und Additionen zerlegt werden, und wenn diese Reihe von Operationen schneller ist als die Multiplikation oder Division, wird der Compiler es verwenden.

Bei der Division durch eine Konstante kann der Compiler die Operation oft in eine Multiplikation mit einer "magischen Zahl" gefolgt von einer Verschiebung umwandeln. Dies kann ein großer Taktzyklusschoner sein, da die Multiplikation oft viel schneller ist als eine Divisionsoperation.

Henry Warren's book, Hacker's Delight, hat eine Fülle von Informationen zu diesem Thema, die auch ganz gut auf der Begleit-Website abgedeckt:

• http://www.hackersdelight.org/

Siehe auch eine Diskussion (mit einem Link oder zwei) in :

• Reading assembly code

Wie auch immer, all dies läuft darauf hinaus, dass der Compiler sich um die mühsamen Details von Mikrooptimierungen kümmert. Es ist Jahre her, dass die eigenen Schichten den Compiler überlistet haben.

Answer 2

können Sie mit ziemlicher Sicherheit hängen von der wörtlichen-power-of-two Multiplikation Optimierung zu einem Schaltvorgang. Dies ist eine der ersten Optimierungen, die Studenten des Compilerbaus lernen werden. :)

Aber ich glaube nicht, dass es keine Garantie dafür. Ihr Quellcode sollte Ihre Absicht widerspiegeln, anstatt zu versuchen, dem Optimierer zu sagen, was zu tun ist. Wenn du eine größere Menge machst, verwende Multiplikation. Wenn Sie ein Bitfeld von einem Ort zu einem anderen verschieben (denken Sie an die RGB-Farbmanipulation), verwenden Sie eine Verschiebeoperation. In beiden Fällen spiegelt Ihr Quellcode wider, was Sie tatsächlich tun.

Answer 3

Wenn der Compiler (Kompilierzeitkonstante) oder JIT (Laufzeitkonstante) weiß, dass der Divisor oder Multiplikand eine Zweierpotenz ist und Ganzzahlarithmetik ausgeführt wird, wird sie für Sie in eine Verschiebung konvertiert.

Answer 4

ich betäubt bin wie ich gerade diesen Code geschrieben und erkennen, dass tatsächlich langsamer durch eine Verschiebung um 2 als Multiplikation ist!

(EDIT: verändert den Code überquell Vorschlag nach Michael Myers zu stoppen, aber die Ergebnisse sind die gleichen Was ist hier falsch?)

import java.util.Date; 

public class Test { 
    public static void main(String[] args) { 
     Date before = new Date(); 
     for (int j = 1; j < 50000000; j++) { 
      int a = 1 ; 
      for (int i = 0; i< 10; i++){ 
       a *=2; 
      } 
     } 
     Date after = new Date(); 
     System.out.println("Multiplying " + (after.getTime()-before.getTime()) + " milliseconds"); 
     before = new Date(); 
     for (int j = 1; j < 50000000; j++) { 
      int a = 1 ; 
      for (int i = 0; i< 10; i++){ 
       a = a << 1; 
      } 
     } 
     after = new Date(); 
     System.out.println("Shifting " + (after.getTime()-before.getTime()) + " milliseconds"); 
    } 
} 

Die Ergebnisse sind:

Multiplying 639 Millisekunden
Shifting 718 Millisekunden

Answer 5

würde ich fragen: „Was für ein Was machst du da? Entwerfen Sie zuerst Ihren Code für Lesbarkeit und Wartbarkeit. Die Wahrscheinlichkeit, dass Bit-Shifting-Verse im Vergleich zur Standard-Multiplikation durchgeführt werden, macht einen Performance-Unterschied EXTREM klein.

Answer 6

Die meisten Compiler wird sich Multiplikation und Division in Bit-Verschiebungen, wenn angemessen. Dies ist eine der einfachsten Optimierungen. Also sollten Sie tun, was leichter lesbar und für die gegebene Aufgabe geeignet ist.

Answer 7

Fast jede Umgebung wert sein Salz wird dies für Sie optimieren entfernt. Und wenn nicht, hast du größere Fische zum Frittieren. Ernsthaft, verschwende keine Sekunde mehr darüber nachzudenken. Sie werden wissen, wenn Sie Leistungsprobleme haben. Und nachdem Sie einen Profiler ausgeführt haben, wissen Sie, was ihn verursacht, und es sollte ziemlich klar sein, wie Sie ihn beheben können.

Sie werden nie jemanden sagen sagen "meine Anwendung war zu langsam, dann habe ich zufällig x * 2 mit x << 1 ersetzt und alles wurde behoben!" Leistungsprobleme werden im Allgemeinen dadurch gelöst, dass man einen Weg findet, um eine Größenordnung weniger Arbeit zu machen, und nicht, indem man einen Weg findet, um die gleiche Arbeit 1% schneller auszuführen.

Answer 8

Menschen sind in diesen Fällen falsch.

99%, wenn sie versuchen, einen modernen (und alle zukünftigen) Compiler zu raten.
99,9%, wenn sie versuchen, moderne (und alle zukünftigen) JITs gleichzeitig zu schätzen.
99.999%, wenn sie versuchen, moderne (und alle zukünftigen) CPU-Optimierungen zu schätzen.

Programm in einer Weise, die genau beschreibt, was Sie erreichen möchten, nicht wie es geht. Zukünftige Versionen von JIT, VM, Compiler und CPU können alle unabhängig verbessert und optimiert werden. Wenn Sie etwas so kleines und spezifisches angeben, verlieren Sie den Vorteil aller zukünftigen Optimierungen.

Answer 9

Es ist hardwareabhängig. Wenn wir Mikrocontroller oder i386 sprechen, kann das Verschieben zwar schneller sein, aber, wie mehrere Antworten sagen, wird Ihr Compiler normalerweise die Optimierung für Sie vornehmen.

Auf modernen (Pentium Pro und darüber hinaus) Hardware macht das Pipelining dies völlig irrelevant und das Verlassen der ausgetretenen Pfade bedeutet normalerweise, dass Sie viel mehr Optimierungen verlieren, als Sie gewinnen können.

Mikrooptimierungen sind nicht nur eine Verschwendung von Zeit, sie sind auch extrem schwierig, richtig zu arbeiten.

Answer 10

Auf Computern, die ich getestet habe, sind ganzzahlige Unterteilungen 4 bis 10 mal langsamer als andere Operationen.

Wenn Compiler Divisionen durch Vielfache von 2 ersetzen können und Sie keinen Unterschied sehen, sind Divisionen um ein Vielfaches von 2 deutlich langsamer.

Zum Beispiel habe ich ein (Grafik-) Programm mit vielen vielen vielen Unterteilungen von 255. Eigentlich meine Berechnung ist:

r = (((top.R - bottom.R) * alpha + (bottom.R * 255)) * 0x8081) >> 23; 

Ich kann dafür sorgen, dass es viel schneller als meine vorherige Berechnung ist:

r = ((top.R - bottom.R) * alpha + (bottom.R * 255))/255; 

also nein, Compiler können alle Tricks der Optimierung nicht.

Answer 11

Beachten Sie, dass die Verschiebung und Division (in Java, sicherlich) unterschiedliche Ergebnisse für negative, ungerade Zahlen ergeben.

int a = -7; 
System.out.println("Shift: "+(a >> 1)); 
System.out.println("Div: "+(a/2)); 

Drucke:

Shift: -4 
Div: -3 

Da Java hat keine Zahlen ohne Vorzeichen ist es nicht wirklich möglich ist, dies für einen Java-Compiler zu optimieren.

Answer 12

Dies ist eine Analyse des Benchmarks von Savvas Dalkitsis. Obwohl dieser Test überprüft Geschwindigkeit der Multiplikation über Bitverschiebung, verwendet die Werte nicht gleich sind, folgende Code in C# überprüfen, das die Werte anzeigt)

for (int i = 0, j = 1, k = 1; i < 10; i++) 
{ 
    j = j * 2; 
    k <<= 2; 
    Console.WriteLine("{0} {1}", j, k); 
} 

Der entsprechende Code von Savvas Dalkitsis Beispiel mit den in C# angezeigten Werte sein

public static void Main(String[] args) 
    { 
     for (int i = 0, j = 1, k = 1; i < 10; i++) 
     { 
      j = j * 2; k <<= 2; 
      Console.WriteLine("{0} {1}", j, k); 
     } 
     Console.WriteLine("-----------------------------------------------"); 


     DateTime before = DateTime.Now; 
     for (int j = 1; j < 500000000; j++) 
     { 
      int a = 1; 
      for (int i = 0; i < 10; i++) a *= 2; 
     } 
     DateTime after = DateTime.Now; 

     Console.WriteLine("Multiplying " + (after - before).ToString() + " milliseconds"); 

     before = DateTime.Now; 
     for (int j = 1; j < 500000000; j++) 
     { 
      int a = 1; 
      for (int i = 0; i < 10; i++) a = a << 1; 
     } 
     after = DateTime.Now; 
     Console.WriteLine("Shifting " + (after - before).ToString() + " milliseconds"); 
     Console.ReadKey(); 
    } 

Answer 13

nach den Ergebnissen von this microbenchmark, verlagert sich doppelt so schnell wie Dividieren (Oracle Java 1.7.0_72).