Leistung von Java-Matrix-Mathematikbibliotheken? [geschlossen]

Wir berechnen etwas, dessen Laufzeit durch Matrixoperationen gebunden ist. (Einige Details unten, falls interessiert.) Diese Erfahrung warf die folgende Frage auf:

Haben die Leute Erfahrung mit der Leistung von Java-Bibliotheken für die Matrixmathematik (z. B. Multiplizieren, Inversieren usw.)? Beispielsweise:

• JAMA
• FOHLEN
• Apache Commons Mathe

Ich habe gesucht und nichts gefunden.

Details unseres Geschwindigkeitsvergleichs:

Wir verwenden Intel FORTRAN (ifort (IFORT) 10.1 20070913). Wir haben es in Java (1.6) mit Apache Commons Math 1.2 Matrix Ops neu implementiert und es stimmt mit allen Ziffern der Genauigkeit überein. (Wir haben Gründe, es in Java zu wollen.) (Java verdoppelt sich, Fortran real * 8). Fortran: 6 Minuten, Java 33 Minuten, dieselbe Maschine. Die jvisualm-Profilerstellung zeigt viel Zeit in RealMatrixImpl. {getEntry, isValidCoordinate} (die in unveröffentlichtem Apache Commons Math 2.0 verschwunden zu sein scheint, aber 2.0 ist nicht schneller). Fortran verwendet Atlas BLAS-Routinen (dpotrf usw.).

Natürlich könnte dies von unserem Code in jeder Sprache abhängen, aber wir glauben, dass die meiste Zeit in äquivalenten Matrixoperationen liegt.

Bei mehreren anderen Berechnungen, an denen keine Bibliotheken beteiligt sind, war Java nicht viel langsamer und manchmal auch viel schneller.

Nur um meine 2 Cent hinzuzufügen. Ich habe einige dieser Bibliotheken verglichen. Ich habe versucht, eine 3000 x 3000 Doppelmatrix mit sich selbst zu multiplizieren. Die Ergebnisse sind wie folgt.

Bei Verwendung von Multithread-ATLAS mit C / C ++, Octave, Python und R betrug die benötigte Zeit ca. 4 Sekunden.

Bei Verwendung von Jama mit Java dauerte die Zeit 50 Sekunden.

Bei Verwendung von Colt und Parallel Colt mit Java wurden 150 Sekunden benötigt!

Bei Verwendung von JBLAS mit Java betrug die benötigte Zeit erneut etwa 4 Sekunden, da JBLAS Multithread-ATLAS verwendet.

Für mich war klar, dass die Java-Bibliotheken nicht besonders gut abschnitten. Wenn jedoch jemand in Java codieren muss, ist JBLAS die beste Option. Jama, Colt und Parallel Colt sind nicht schnell.

Ich bin der Autor von Java Matrix Benchmark ( JMatBench ) und werde meine Gedanken zu dieser Diskussion äußern .

Es gibt signifikante Unterschiede zwischen Java-Bibliotheken, und obwohl es keinen eindeutigen Gewinner für die gesamte Palette von Vorgängen gibt, gibt es einige klare Vorreiter, wie aus den neuesten Leistungsergebnissen (Oktober 2013) hervorgeht.

Wenn Sie mit "großen" Matrizen arbeiten und native Bibliotheken verwenden können, ist MTJ mit systemoptimierter Netlib der klare Gewinner (ca. 3,5-mal schneller) . Wenn Sie eine reine Java-Lösung benötigen , sind MTJ , OjAlgo , EJML und Parallel Colt eine gute Wahl. Für kleine Matrizen ist EJML der klare Gewinner.

Die Bibliotheken, die ich nicht erwähnte, zeigten signifikante Leistungsprobleme oder es fehlten wichtige Funktionen.

Ich bin der Hauptautor von jblas und wollte darauf hinweisen, dass ich Ende Dezember 2009 Version 1.0 veröffentlicht habe. Ich habe viel an der Verpackung gearbeitet, was bedeutet, dass Sie jetzt einfach ein "Fat Jar" mit ATLAS- und JNI-Bibliotheken herunterladen können für Windows, Linux, Mac OS X, 32 und 64 Bit (außer Windows). Auf diese Weise erhalten Sie die native Leistung, indem Sie die JAR-Datei einfach zu Ihrem Klassenpfad hinzufügen. Schau es dir unter http://jblas.org an !

Ich kann bestimmte Bibliotheken nicht wirklich kommentieren, aber im Prinzip gibt es wenig Grund dafür, dass solche Operationen in Java langsamer sind. Hotspot erledigt im Allgemeinen die Dinge, die Sie von einem Compiler erwarten würden: Es kompiliert grundlegende mathematische Operationen für Java-Variablen zu entsprechenden Maschinenanweisungen (es verwendet SSE-Anweisungen, aber nur eine pro Operation); Zugriffe auf Elemente eines Arrays werden so kompiliert, dass erwartungsgemäß "rohe" MOV-Anweisungen verwendet werden. Es trifft Entscheidungen darüber, wie Variablen Registern zugewiesen werden sollen, wenn dies möglich ist. Es ordnet Anweisungen neu an, um die Prozessorarchitektur zu nutzen ... Eine mögliche Ausnahme ist, dass Hotspot, wie bereits erwähnt, nur eine Operation pro SSE-Anweisung ausführt. Im Prinzip könnten Sie eine fantastisch optimierte Matrixbibliothek haben, die mehrere Operationen pro Anweisung ausführt, obwohl ich es nicht tue. Ich weiß nicht, ob dies beispielsweise in Ihrer FORTRAN-Bibliothek der Fall ist oder ob eine solche Bibliothek überhaupt existiert. Wenn dies der Fall ist, gibt es derzeit keine Möglichkeit für Java (oder zumindest Hotspot), damit zu konkurrieren (obwohl Sie natürlich Ihre eigene native Bibliothek mit diesen Optimierungen schreiben könnten, um von Java aus aufzurufen).

Was bedeutet das alles? Gut:

• Im Prinzip lohnt es sich, nach einer leistungsstärkeren Bibliothek zu suchen, obwohl ich leider keine empfehlen kann
• Wenn die Leistung für Sie wirklich kritisch ist, würde ich in Betracht ziehen, nur Ihre eigenen Matrixoperationen zu codieren, da Sie dann möglicherweise bestimmte Optimierungen durchführen können, die eine Bibliothek im Allgemeinen nicht kann oder die eine bestimmte Bibliothek, die Sie verwenden, nicht kann (wenn Sie eine haben) Multiprozessor-Maschine, finden Sie heraus, ob die Bibliothek tatsächlich Multithread-fähig ist)

Ein Hindernis für Matrixoperationen sind häufig Probleme mit der Datenlokalität, die auftreten, wenn Sie zeilenweise und spaltenweise durchlaufen müssen, z. B. bei der Matrixmultiplikation, da Sie die Daten in einer Reihenfolge speichern müssen, die die eine oder andere optimiert. Wenn Sie den Code jedoch von Hand schreiben, können Sie manchmal Operationen kombinieren, um die Datenlokalität zu optimieren (z. B. wenn Sie eine Matrix mit ihrer Transformation multiplizieren, können Sie eine Spaltenüberquerung in eine Zeilenüberquerung umwandeln, wenn Sie eine dedizierte Funktion schreiben, anstatt sie zu kombinieren zwei Bibliotheksfunktionen). Wie im Leben üblich, bietet eine Bibliothek eine nicht optimale Leistung im Austausch für eine schnellere Entwicklung. Sie müssen entscheiden, wie wichtig Leistung für Sie ist.

Ich habe gerade Apache Commons Math mit jlapack verglichen.

Test: Singularwertzerlegung einer zufälligen 1024x1024-Matrix.

Maschine: Intel (R) Core (TM) 2 Duo-CPU E6750 bei 2,66 GHz, Linux x64

Oktavcode: A = Rand (1024); tic; [U, S, V] = svd (A); toc

Ausführungszeit der Ergebnisse
-------------------------------------------------- -------
Oktave 36,34 Sek

JDK 1.7u2 64bit
    jlapack dgesvd 37,78 sek
    Apache Commons Mathe SVD 42,24 Sek


JDK 1.6u30 64bit
    jlapack dgesvd 48,68 sek
    Apache Commons Mathe SVD 50,59 Sek

Native Routinen
Lapack * von C aufgerufen: 37,64 Sek
Intel MKL 6,89 Sek. (!)

Mein Fazit ist, dass jlapack, das von JDK 1.7 aufgerufen wird, der nativen binären Leistung von Lapack sehr nahe kommt. Ich habe die mit der Linux-Distribution gelieferte Lapack-Binärbibliothek verwendet und die Routine dgesvd aufgerufen, um auch die U-, S- und VT-Matrizen abzurufen. Alle Tests wurden mit doppelter Genauigkeit auf genau derselben Matrix bei jedem Lauf (außer Octave) durchgeführt.

Haftungsausschluss - Ich bin kein Experte für lineare Algebra und keiner der oben genannten Bibliotheken zugeordnet. Dies ist kein strenger Maßstab. Es ist ein "hausgemachter" Test, da ich daran interessiert war, die Leistungssteigerung von JDK 1,7 auf 1,6 sowie die gemeinsame mathematische SVD mit jlapack zu vergleichen.

Jeigen https://github.com/hughperkins/jeigen

• Wraps Eigen C ++ - Bibliothek http://eigen.tuxfamily.org , eine der schnellsten kostenlosen C ++ - Bibliotheken auf dem Markt
• relativ knappe Syntax, zB 'mmul', 'sub'
• behandelt sowohl dichte als auch spärliche Matrizen

Ein schneller Test durch Multiplikation zweier dichter Matrizen, dh:

statisches jeigen.MatrixUtil importieren. *;

int K = 100;
int N = 100000;
DenseMatrix A = rand(N, K);
DenseMatrix B = rand(K, N);
Timer timer = new Timer();
DenseMatrix C = B.mmul(A);
timer.printTimeCheckMilliseconds();

Ergebnisse:

Jama: 4090 ms
Jblas: 1594 ms
Ojalgo: 2381 ms (using two threads)
Jeigen: 2514 ms

• Im Vergleich zu Jama ist alles schneller :-P
• Im Vergleich zu jblas ist Jeigen nicht ganz so schnell, aber es verarbeitet spärliche Matrizen.
• Im Vergleich zu Ojalgo benötigt Jeigen ungefähr die gleiche Zeit, jedoch nur einen Kern, sodass Jeigen die Hälfte der gesamten CPU verwendet. Jeigen hat eine Terser-Syntax, dh 'mmul' versus 'multiplyRight'

Unter http://code.google.com/p/java-matrix-benchmark/ finden Sie in Java einen Benchmark für verschiedene Matrixpakete für einige verschiedene Hardwarekonfigurationen. Aber es ist kein Ersatz für Ihren eigenen Benchmark.

Die Leistung hängt von der Art der Hardware ab (CPU, Kerne, Speicher, L1-3-Cache, Busgeschwindigkeit), der Größe der Matrizen und den Algorithmen, die Sie verwenden möchten. Verschiedene Bibliotheken haben unterschiedliche Einstellungen für die Parallelität für verschiedene Algorithmen, daher gibt es keine einzige Antwort. Möglicherweise stellen Sie auch fest, dass der Aufwand für die Übersetzung in das von einer nativen Bibliothek erwartete Formular den Leistungsvorteil für Ihren Anwendungsfall zunichte macht (einige der Java-Bibliotheken bieten flexiblere Optionen für den Matrixspeicher, die für weitere Leistungsoptimierungen verwendet werden können).

Im Allgemeinen werden JAMA, Jampack und COLT jedoch alt und geben nicht den Status der aktuellen Leistung wieder, die in Java für die lineare Algebra verfügbar ist. Moderne Bibliotheken nutzen mehrere Kerne und CPU-Caches effektiver. JAMA war eine Referenzimplementierung und implementiert Lehrbuchalgorithmen mit wenig Rücksicht auf die Leistung. COLT und IBM Ninja waren die ersten Java-Bibliotheken, die zeigten, dass Leistung in Java möglich war, auch wenn sie 50% hinter den nativen Bibliotheken zurückblieben.

Ich bin der Autor der Bibliothek la4j (Lineare Algebra für Java) und hier ist mein Punkt. Ich arbeite seit 3 ​​Jahren an la4j (die neueste Version ist 0.4.0 [01. Juni 2013]) und erst jetzt kann ich mit der Analyse und Optimierung der Leistung beginnen, da ich gerade die minimal erforderlichen Funktionen behandelt habe. La4j ist also nicht so schnell wie ich wollte, aber ich verbringe viel Zeit damit, es zu ändern.

Ich bin gerade dabei, eine neue Version von la4j auf die JMatBench- Plattform zu portieren . Ich hoffe, dass die neue Version eine bessere Leistung als die vorherige zeigt, da ich in la4j einige Verbesserungen vorgenommen habe, wie z. B. ein viel schnelleres internes Matrixformat, unsichere Zugriffsmethoden und einen schnellen Blockierungsalgorithmus für Matrixmultiplikationen.

Linalg-Code, der stark von den Vektor-Computing-Funktionen von Pentiums und späteren Prozessoren abhängt (beginnend mit den MMX-Erweiterungen wie LAPACK und jetzt Atlas BLAS), ist nicht "fantastisch optimiert", sondern einfach branchenüblich. Um diese Leistung in Java zu replizieren, benötigen Sie native Bibliotheken. Ich hatte das gleiche Leistungsproblem wie Sie beschrieben (hauptsächlich, um Choleski-Zerlegungen berechnen zu können) und habe nichts wirklich Effizientes gefunden: Jama ist reines Java, da es nur eine Vorlage und ein Referenzkit für Implementierer sein soll. .. was nie passiert ist. Sie kennen Apache Math Commons ... Was COLT betrifft, muss ich es noch testen, aber es scheint stark von Ninja-Verbesserungen abhängig zu sein, von denen die meisten durch die Erstellung eines Ad-hoc-Java-Compilers erreicht wurden. Ich bezweifle, dass dies helfen wird. An diesem Punkt denke ich, dass wir "

Wir haben COLT für einige ziemlich große ernsthafte finanzielle Berechnungen verwendet und waren sehr zufrieden damit. In unserem stark profilierten Code mussten wir fast nie eine COLT-Implementierung durch eine eigene ersetzen.

In ihren eigenen Tests (offensichtlich nicht unabhängig) behaupten sie, dass sie innerhalb eines Faktors von 2 der handoptimierten Assembler-Routinen von Intel behaupten. Der Trick, um es gut zu verwenden, besteht darin, sicherzustellen, dass Sie die Designphilosophie verstehen und eine unnötige Objektzuweisung vermeiden.

Haben Sie sich die Intel Math Kernel Library angesehen ? Es behauptet, sogar ATLAS zu übertreffen . MKL kann in Java über JNI-Wrapper verwendet werden.

Aufbauend auf Varkhans Beitrag, dass Pentium-spezifischer nativer Code besser funktionieren würde:

• jBLAS: Ein Alpha-Stage-Projekt mit JNI-Wrappern für Atlas: http://www.jblas.org .

  • Blogbeitrag des Autors: http://mikiobraun.blogspot.com/2008/10/matrices-jni-directbuffers-and-number.html .

• MTJ: Ein weiteres solches Projekt: http://code.google.com/p/matrix-toolkits-java/

Vielleicht möchten Sie sich das jblas- Projekt ansehen . Es ist eine relativ neue Java-Bibliothek, die BLAS, LAPACK und ATLAS für leistungsstarke Matrixoperationen verwendet.

Der Entwickler hat einige Benchmarks veröffentlicht, bei denen sich jblas gegenüber MTJ und Colt positiv entwickelt.

Für 3D-Grafikanwendungen übertraf die Vektorimplementierung von lwjgl.util die oben genannten jblas um den Faktor 3.

Ich habe 1 Million Matrixmultiplikationen eines vec4 mit einer 4x4-Matrix durchgeführt.

lwjgl fertig in ca. 18ms, jblas benötigt ca. 60ms.

(Ich gehe davon aus, dass der JNI-Ansatz für die schnelle sukzessive Anwendung relativ kleiner Multiplikationen nicht sehr geeignet ist. Da die Übersetzung / Abbildung mehr Zeit in Anspruch nehmen kann als die tatsächliche Ausführung der Multiplikation.)

Ich habe festgestellt, dass Sie Jama etwa 20% schneller machen können, wenn Sie viele hochdimensionale Matrizen erstellen, wenn Sie es so ändern, dass ein eindimensionales Array anstelle eines zweidimensionalen Arrays verwendet wird. Dies liegt daran, dass Java mehrdimensionale Arrays nicht so effizient unterstützt. dh. Es wird ein Array von Arrays erstellt.

Colt tut dies bereits, aber ich habe festgestellt, dass es komplizierter und leistungsfähiger als Jama ist, was möglicherweise erklärt, warum einfache Funktionen bei Colt langsamer sind.

Die Antwort hängt wirklich davon ab, was Sie tun. Jama unterstützt nicht einen Bruchteil der Dinge, die Colt tun kann, um mehr zu bewirken.

Es gibt auch UJMP

Es gibt viele verschiedene frei verfügbare Java-Bibliotheken für lineare Algebra. http://www.ujmp.org/java-matrix/benchmark/ Leider gibt Ihnen dieser Benchmark nur Informationen zur Matrixmultiplikation (bei der Umsetzung des Tests können die verschiedenen Bibliotheken ihre jeweiligen Designmerkmale nicht ausnutzen).

Was Sie sich ansehen sollten, ist die Leistung dieser linearen Algebra-Bibliotheken, wenn Sie aufgefordert werden, verschiedene Matrixzerlegungen zu berechnen. http://ojalgo.org/matrix_compare.html

Matrix Tookits Java (MTJ) wurde bereits erwähnt, aber vielleicht ist es noch einmal erwähnenswert, wenn jemand anderes auf diesen Thread stößt. Für Interessierte scheint es auch die Rede zu sein, dass MTJ die Linalg-Bibliothek in Apache Commons Math 2.0 ersetzen soll , obwohl ich nicht sicher bin, wie sich das in letzter Zeit entwickelt.

Sie sollten Apache Mahout zu Ihrer Einkaufsliste hinzufügen.