Java: Mehrdimensionales Array vs. eindimensional

Lesezeit: 6 Minuten

Java Mehrdimensionales Array vs eindimensional
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?

  • Siehe auch: stackoverflow.com/questions/2368761/…

    – Polygenschmierstoffe

    25. März ’10 um 1:50

1641585087 919 Java Mehrdimensionales Array vs eindimensional
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

  • Größe: 100×100 (10000)
    • Multi: 5.786591
    • Single: 6.131748
  • Größe: 200×200 (40000)
    • Multi: 1.216366
    • Einzeln: 0.782041
  • Größe: 500×500 (250000)
    • Multi: 7.177029
    • Einzeln: 3.667017
  • Größe: 1000×1000 (1000000)
    • Multi: 30.508131
    • Single: 18.064592
  • Größe: 2000×2000 (4000000)
    • Multi: 185,3548
    • Einzeln: 155.590313
  • Größe: 5000×5000 (25000000)
    • Multi: 955.5299
    • Einzeln: 923.264417
  • Größe: 10000×10000 (100000000)
    • Multi: 4084.798753
    • Einzeln: 4015.448829

Lineares Lesen

  • Größe: 100×100 (10000)
    • Multi: 5.241338
    • Einzeln: 5.135957
  • Größe: 200×200 (40000)
    • Multi: 0.080209
    • Einzeln: 0.044371
  • Größe: 500×500 (250000)
    • Multi: 0,088742
    • Einzeln: 0,084476
  • Größe: 1000×1000 (1000000)
    • Multi: 0,232095
    • Einzeln: 0,167671
  • Größe: 2000×2000 (4000000)
    • Multi: 0.481683
    • Einzeln: 0,33321
  • Größe: 5000×5000 (25000000)
    • Multi: 1.222339
    • Einzeln: 0.828118
  • Größe: 10000×10000 (100000000)
    • Multi: 2.496302
    • Einzeln: 1.650691

Zufälliges Lesen

  • Größe: 100×100 (10000)
    • Multi: 22.317393
    • Einzeln: 8.546134
  • Größe: 200×200 (40000)
    • Multi: 32.287669
    • Single: 11.022383
  • Größe: 500×500 (250000)
    • Multi: 189.542751
    • Single: 68.181343
  • Größe: 1000×1000 (1000000)
    • Multi: 1124.78609
    • Einzeln: 272.235584
  • Größe: 2000×2000 (4000000)
    • Multi: 6814.477101
    • Einzeln: 1091.998395
  • Größe: 5000×5000 (25000000)
    • Multi: 50051.306239
    • Einzeln: 7028.422262

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)

  • 3

    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

  • 5

    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

  • 1

    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

  • 1

    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

  • 7

    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


Java Mehrdimensionales Array vs eindimensional
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.

.

178920cookie-checkJava: Mehrdimensionales Array vs. eindimensional

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy