Warum ist die Leistung dieser Matrixmultiplikationen so unterschiedlich?

Question

Ich schrieb zwei Matrixklassen in Java, nur um die Leistung ihrer Matrixmultiplikationen zu vergleichen. Eine Klasse (Mat1) speichert ein double[][] A Mitglied, wobei die Zeile i der Matrix A[i] ist. Die andere Klasse (Mat2) speichert A und T, wobei T die Transponierte A ist.

Nehmen wir an, wir haben eine quadratische Matrix M und wir wollen das Produkt von M.mult(M). Rufen Sie das Produkt P.

Wenn M ein Mat1 Beispiel verwendet der Algorithmus die einfach war:

P[i][j] += M.A[i][k] * M.A[k][j] 
    for k in range(0, M.A.length) 

In dem Fall, wo M ein Mat2 I verwendet:

P[i][j] += M.A[i][k] * M.T[j][k] 

, die der gleiche Algorithmus ist, weil T[j][k]==A[k][j] . Bei 1000x1000 Matrizen dauert der zweite Algorithmus ungefähr 1,2 Sekunden auf meinem Rechner, während der erste mindestens 25 Sekunden dauert. Ich hatte erwartet, dass der zweite schneller sein würde, aber nicht so sehr. Die Frage ist, warum ist es so viel schneller?

Meine einzige Vermutung ist, dass die zweite die CPU-Caches besser ausnutzt, da Daten in Chunks größer als 1 Wort in die Caches gezogen werden, und der zweite Algorithmus profitiert davon, indem er nur Zeilen durchläuft, während der erste ignoriert Die Daten werden in die Caches gezogen, indem sie sofort in die darunter liegende Zeile gehen (was ~ 1000 Wörter im Speicher ist, da Arrays in der Reihenfolge der Zeilen gespeichert sind), wobei keines der Daten zwischengespeichert wird.

Ich fragte jemanden und er dachte, es sei wegen der freundlicheren Speicherzugriffsmuster (d. H. Dass die zweite Version in weniger weichen TLB-Fehlern resultieren würde). Ich habe überhaupt nicht daran gedacht, aber ich kann sehen, wie es zu weniger TLB-Fehlern kommt.

Also, was ist das? Oder gibt es einen anderen Grund für den Leistungsunterschied?

Answer 1

Dies aufgrund der Lokalität Ihrer Daten.

In RAM eine Matrix, obwohl aus Ihrer Sicht zweidimensional, wird es natürlich als zusammenhängendes Array von Bytes gespeichert. Der einzige Unterschied zu einem 1D-Array besteht darin, dass der Offset durch Interpolation der beiden von Ihnen verwendeten Indizes berechnet wird.

Das heißt, wenn Sie auf Element an Position x,y zugreifen, berechnet es x*row_length + y und dies ist der Offset, der verwendet wird, um auf das Element an der angegebenen Position zu verweisen.

Was passiert ist, dass eine große Matrix nicht in nur einer Seite des Speichers gespeichert wird (so verwaltet Ihr OS den RAM, indem Sie es in Blöcke aufteilen), so muss es die richtige Seite in den Cache laden versuche auf ein Element zuzugreifen, das noch nicht vorhanden ist.

Solange Sie fortfahren, Ihre Multiplikation zu machen, schaffen Sie keine Probleme, da Sie hauptsächlich alle Koeffizienten einer Seite verwenden und dann zur nächsten wechseln, aber wenn Sie Indizes invertieren, geschieht das jedes einzelne Element in einer anderen Speicherseite enthalten sein, so dass es jedes Mal, wenn es eine andere Seite RAM anfordern muss, dies fast für jede einzelne Multiplikation tut, deshalb ist der Unterschied so ordentlich.

(I vereinfacht vielmehr die ganze explaination, es ist nur Sie die grundlegende Idee, um dieses Problem zu geben) ich dies allein durch JVM verursacht nicht denken

In jedem Fall ist. Es hängt vielleicht damit zusammen, wie Ihr Betriebssystem den Speicher des Java-Prozesses verwaltet.

Answer 2

Die Cache- und TLB-Hypothesen sind beide vernünftig, aber ich würde gerne den vollständigen Code Ihres Benchmarks sehen ... nicht nur Pseudocode-Snippets.

Eine andere Möglichkeit ist, dass der Leistungsunterschied das Ergebnis einer Anwendung ist, die 50% mehr Speicher für die Datenfelder in der Version mit der Transponierung verwendet. Wenn die Heap-Größe Ihrer JVM klein ist, kann dies dazu führen, dass der GC zu oft ausgeführt wird. Dies könnte ein Ergebnis der Verwendung der Standard-Heap-Größe sein. (Drei Chargen von 1000 x 1000 x 8 Bytes ist ~ 24 MB)

Versuchen Sie, die anfänglichen und maximalen Heap-Größen auf (sagen wir) die doppelte maximale Größe zu setzen. Wenn das keinen Unterschied macht, handelt es sich nicht um ein einfaches Heap-Size-Problem.

Answer 3

Es ist leicht zu erraten, dass das Problem Lokalität sein könnte, und vielleicht ist es das, aber das ist immer noch eine Vermutung.

Es ist nicht notwendig zu erraten. Zwei Techniken könnten Ihnen die Antwort geben - Einzelschritt und zufällige Pause.

Wenn Sie den langsamen Code in einem Schritt ausführen, können Sie herausfinden, dass er viele Dinge erledigt, von denen Sie nie geträumt haben. Wie fragen Sie? Probieren Sie es aus und finden Sie es heraus. Was Sie sollten sehen es tun, auf der Maschinensprache Ebene, ist effizient durch die innere Schleife ohne Verschwendung Bewegung.

Wenn es tatsächlich durch die innere Schleife ohne Verschwendung Bewegung tritt, wird zufällige Pause Ihnen Informationen geben. Da das Langsame 20 Mal länger dauert als das Schnelle, bedeutet das, dass es in 95% der Fälle etwas tut, was es nicht muss. Also sieh was es ist. Jedes Mal, wenn Sie es anhalten, beträgt die Chance 95%, dass Sie sehen werden, was das ist und warum.

Wenn im langsamen Fall die Anweisungen, die ausgeführt werden, genauso effizient sind wie der schnelle Fall, dann ist die Cache-Lokalität eine vernünftige Schätzung, warum sie langsam ist. Ich bin mir sicher, sobald Sie irgendeine andere Dummheit beseitigt haben, die weitergeht, wird diese Cache-Lokalität wird dominieren.

Answer 4

Sie könnten versuchen, den Vergleich der Leistung zwischen JDK6 und OpenJDK7, da diese set of results ...