Beispielsweise:
-
ein)
int [x][y][z]
vs
-
B)
int[x*y*z]
Dachte zunächst, ich würde der Einfachheit halber mit a) gehen.
Ich weiß, dass Java Arrays nicht wie C linear im Speicher speichert, aber welche Auswirkungen hat dies auf mein Programm?
Mikolan
Beispielsweise:
ein) int [x][y][z]
vs
B) int[x*y*z]
Dachte zunächst, ich würde der Einfachheit halber mit a) gehen.
Ich weiß, dass Java Arrays nicht wie C linear im Speicher speichert, aber welche Auswirkungen hat dies auf mein Programm?
Jack
Normalerweise ist es am besten, wenn Sie Antworten auf solche Fragen suchen, um zu sehen, wie die Auswahlmöglichkeiten in JVM-Bytecode kompiliert werden:
multi = new int[50][50];
single = new int[2500];
Dies wird übersetzt in:
BIPUSH 50
BIPUSH 50
MULTIANEWARRAY int[][] 2
ASTORE 1
SIPUSH 2500
NEWARRAY T_INT
ASTORE 2
Wie Sie sehen, weiß die JVM bereits, dass es sich um ein mehrdimensionales Array handelt.
Weiter so:
for (int i = 0; i < 50; ++i)
for (int j = 0; j < 50; ++j)
{
multi[i][j] = 20;
single[i*50+j] = 20;
}
Dies wird übersetzt (Überspringen der Zyklen) in:
ALOAD 1: multi
ILOAD 3: i
AALOAD
ILOAD 4: j
BIPUSH 20
IASTORE
ALOAD 2: single
ILOAD 3: i
BIPUSH 50
IMUL
ILOAD 4: j
IADD
BIPUSH 20
IASTORE
Wie Sie sehen, wird das mehrdimensionale Array intern in der VM behandelt, es entsteht kein Overhead durch nutzlose Anweisungen, während die Verwendung eines einzelnen mehr Anweisungen verwendet, da der Offset von Hand berechnet wird.
Ich glaube nicht, dass die Leistung so ein Problem sein wird.
BEARBEITEN:
Ich habe einige einfache Benchmarks durchgeführt, um zu sehen, was hier passiert. Ich entschied mich, verschiedene Beispiele auszuprobieren: lineares Lesen, lineares Schreiben und wahlfreier Zugriff. Zeiten werden in Millisekunden ausgedrückt (und berechnet mit System.nanoTime()
. Hier sind die Ergebnisse:
Lineares Schreiben
Lineares Lesen
Zufälliges Lesen
Die Zufallszahl ist ein wenig irreführend, da sie 2 Zufallszahlen für mehrdimensionale Arrays generiert, während nur eine für eindimensionale (und PNRGs können etwas CPU verbrauchen).
Beachten Sie, dass ich versucht habe, JIT durch Benchmarking erst nach dem 20. Durchlauf derselben Schleife funktionieren zu lassen. Der Vollständigkeit halber ist meine Java-VM die folgende:
Java-Version “1.6.0_17” Java(TM) SE Laufzeitumgebung (Build 1.6.0_17-b04) Java HotSpot(TM) 64-Bit Server VM (Build 14.3-b01, gemischter Modus)
Es ist immer schön zu sehen, dass jemand die Realität unter der Haube betrachtet, anstatt nur Vermutungen anzustellen. Ich würde dir +100 geben, wenn ich könnte.
– NUR MEINE richtige MEINUNG
25. März ’10 bei 3:38
Zum Zeitpunkt des Jitting des Codes ist die Anzahl der JVM-Befehle irrelevant. Wichtig ist, wie viel tatsächliche Zeit der Code für die Ausführung benötigt, die von Dingen wie Lokalität, Dereferenzierung und Speichernutzung abhängt.
– Gabe
25. März ’10 bei 3:47
Bitte aktualisieren Sie den Zufallslese-Benchmark, sodass er für beide Versionen 2 Zufallszahlen generiert. Wahrscheinlich wird die Single-Array-Version sogar dann schneller sein, weil weniger Speichersuchvorgänge erforderlich sind (zufälliges Lesen führt zu den meisten Cache-Fehlversuchen), aber Sie können nie sicher sein, bevor Sie es messen.
– Esko Luontola
25. März ’10 um 15:52
Im ersten Teil Ihrer Nachricht kommen Sie zu dem Schluss, dass die Bytecodes ähnlich sind und es keinen Leistungsunterschied geben wird, aber dann beweisen die Benchmarks im letzten Teil Ihrer Nachricht, dass Ihre ursprüngliche Annahme falsch ist. Das bestärkt die Idee, dass “vorzeitige Optimierung die Wurzel allen Übels ist”, denn der Versuch, die Leistung zu erraten, funktioniert selten. 🙂 Ich habe meiner Antwort Benchmarks für dreidimensionale Arrays hinzugefügt und auch den Aufwand für die Generierung von Zufallszahlen berücksichtigt.
– Esko Luontola
25. März ’10 um 17:50
Tatsächlich ist aus den von Ihnen gezeigten Bytecodes ersichtlich, dass das mehrdimensionale Array langsamer sein kann: Es erfordert 2 Heap-Zugriffe (AALOAD und IASTORE), während die eindimensionale Version nur 1 Heap-Zugriff (IASTORE) erfordert. Alle anderen Befehle arbeiten mit den Werten auf dem Stack (die sich im Cache oder in den Registern befinden) oder führen Arithmetik durch, sind also sehr schnell.
– Esko Luontola
25. März ’10 um 17:58
Esko Luontola
Auf aktuellen CPUs ist der nicht zwischengespeicherte Speicherzugriff hundertmal langsamer als die Arithmetik (siehe diese Präsentation und lese Was jeder Programmierer über Speicher wissen sollte). Die Option a) führt zu etwa 3 Speichersuchvorgängen, während die Option b) zu etwa 1 Speichersuchvorgängen führt. Auch die Prefetching-Algorithmen der CPU funktionieren möglicherweise nicht so gut. Daher kann die Option b) in einigen Situationen schneller sein (es ist ein Hotspot und das Array passt nicht in den Cache der CPU). Wie viel schneller? – das hängt von der Anwendung ab.
Persönlich würde ich zuerst die Option a) verwenden, da sie zu einfacherem Code führt. Wenn ein Profiler zeigt, dass der Array-Zugriff ein Engpass ist, dann würde ich ihn in die Option b) konvertieren, sodass es ein Paar Hilfsmethoden zum Lesen und Schreiben von Array-Werten gibt (auf diese Weise wird der unordentliche Code auf diese beiden beschränkt Methoden).
Ich habe einen Benchmark zum Vergleich von dreidimensionalen int-Arrays (Spalte “Multi”) mit den entsprechenden eindimensionalen int-Arrays (Spalte “Single”) erstellt. Der Code ist Hier und testet Hier. Ich habe es auf 64-Bit jdk1.6.0_18, Windows 7 x64, Core 2 Quad Q6600 @ 3,0 GHz, 4 GB DDR2 mit den JVM-Optionen ausgeführt -server -Xmx3G -verbose:gc -XX:+PrintCompilation
(Ich habe die Debug-Ausgabe aus den folgenden Ergebnissen entfernt). Die Ergebnisse waren:
Out of 20 repeats, the minimum time in milliseconds is reported.
Array dimensions: 100x100x100 (1000000)
Multi Single
Seq Write 1 1
Seq Read 1 1
Random Read 99 90 (of which generating random numbers 59 ms)
Array dimensions: 200x200x200 (8000000)
Multi Single
Seq Write 14 13
Seq Read 11 8
Random Read 1482 1239 (of which generating random numbers 474 ms)
Array dimensions: 300x300x300 (27000000)
Multi Single
Seq Write 53 46
Seq Read 34 24
Random Read 5915 4418 (of which generating random numbers 1557 ms)
Array dimensions: 400x400x400 (64000000)
Multi Single
Seq Write 123 111
Seq Read 71 55
Random Read 16326 11144 (of which generating random numbers 3693 ms)
Dies zeigt, dass das 1-dimensionale Array schneller ist. Obwohl die Unterschiede so gering sind, dass sie bei 99% der Anwendungen nicht auffallen.
Ich habe auch einige Messungen durchgeführt, um den Aufwand für die Generierung der Zufallszahlen im Random Read-Benchmark durch Ersetzen von . abzuschätzen preventOptimizingAway += array.get(x, y, z);
mit preventOptimizingAway += x * y * z;
und fügte die Messwerte von Hand in die obige Ergebnistabelle ein. Das Generieren der Zufallszahlen dauert 1/3 oder weniger der Gesamtzeit des Random Read-Benchmarks, sodass der Speicherzugriff wie erwartet den Benchmark dominiert. Es wäre interessant, diesen Benchmark mit Arrays von 4 und mehr Dimensionen zu wiederholen. Wahrscheinlich würde es den Geschwindigkeitsunterschied größer machen, da die obersten Ebenen des mehrdimensionalen Arrays in den Cache der CPU passen und nur die anderen Ebenen eine Speichersuche erfordern.
Verwenden Sie die erste Variante (3-dimensional), da sie leichter zu verstehen ist und die Wahrscheinlichkeit eines logischen Fehlers geringer ist (insbesondere, wenn Sie sie zum Modellieren des dreidimensionalen Raums verwenden).
Wenn Sie die letztere Route wählen, müssen Sie für jeden einzelnen Array-Zugriff eine Arithmetik ausführen. Das wird mühsam und fehleranfällig (es sei denn, Sie packen es in eine Klasse ein, die diese Funktionalität bietet).
Ich glaube nicht, dass es eine (signifikante) Optimierung bei der Auswahl Ihres flachen Arrays gibt (insbesondere angesichts der Arithmetik, die zum Indexieren verwendet wird). Wie immer bei Optimierungen müssen Sie einige Messungen durchführen und feststellen, ob es sich wirklich lohnt.
.
Siehe auch: stackoverflow.com/questions/2368761/…
– Polygenschmierstoffe
25. März ’10 um 1:50