Performance des bibliothèques mathématiques Java matrix? [fermé]

Je suis l'auteur de Java Matrix Benchmark ( JMatBench ) et je vais donner mes réflexions sur cette discussion.

Il y a une différence significative entre les bibliothèques Java et bien qu'il n'y ait pas de gagnant clair dans toute la gamme des opérations, il y a quelques leaders clairs comme on peut le voir dans les derniers résultats de performance (octobre 2013).

Si vous travaillez avec des matrices" volumineuses " et que vous pouvez utiliser des bibliothèques natives, le gagnant clair (environ 3,5 fois plus rapide) est MTJ avec optimisé netlib. Si vous avez besoin d'un pur Java solution, alors MTJ, OjAlgo, EJML et Parallèle Colt sont de bons choix. Pour les petites matrices, EJML est le gagnant.

Les bibliothèques que je n'ai pas mentionnées présentaient des problèmes de performance importants ou manquaient de fonctionnalités clés.

Je suis l'auteur principal de jblas et je voulais souligner que j'ai publié la Version 1.0 fin décembre 2009. J'ai beaucoup travaillé sur l'Emballage, ce qui signifie que vous pouvez maintenant télécharger un "fat jar" avec les bibliothèques ATLAS et JNI pour Windows, Linux, Mac OS X, 32 et 64 bits (sauf pour Windows). De cette façon, vous obtiendrez les performances natives simplement en ajoutant le fichier jar à votre classpath. Vérifiez-le à http://jblas.org !

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

• enveloppe la bibliothèque C++ Propre http://eigen.tuxfamily.org , qui est l'une des bibliothèques C++ gratuites les plus rapides disponibles
• syntaxe relativement laconique, par exemple 'mmul','sub'
• gère à la fois les matrices denses et clairsemées

Un test rapide, en multipliant deux matrices denses, c'est-à-dire:

Importer des jeigen statiques.MatrixUtil.*;

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();

Résultats:

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

• par rapport à jama, tout est plus rapide: P
• comparé à jblas, Jeigen n'est pas aussi rapide, mais il gère des matrices clairsemées.
• par rapport à ojalgo, Jeigen prend à peu près la même quantité de temps écoulé, mais en utilisant seulement un noyau, donc jeigen utilise la moitié du cpu total. Jeigen a une syntaxe plus laconique, c'est-à-dire 'mmul' par rapport à 'multiplyRight'

Je viens de comparer Apache Commons Math avec jlapack.

Test: décomposition de la valeur singulière d'une matrice aléatoire 1024x1024.

Machine: Intel (R) Core (TM)2 Duo CPU E6750 @ 2.66 GHz, linux x64

Code D'Octave: A = rand (1024); tic; [U, S, V] = svd(a); toc

results                                execution time
---------------------------------------------------------
Octave                                 36.34 sec

JDK 1.7u2 64bit
    jlapack dgesvd                     37.78 sec
    apache commons math SVD            42.24 sec


JDK 1.6u30 64bit
    jlapack dgesvd                     48.68 sec
    apache commons math SVD            50.59 sec

Native routines
Lapack* invoked from C:                37.64 sec
Intel MKL                               6.89 sec(!)

Ma conclusion est que jlapack appelé à partir de JDK 1.7 est très proche du natif performance binaire de lapack. J'ai utilisé la bibliothèque binaire lapack fournie avec la distribution linux et invoqué la routine dgesvd pour obtenir le U, S et VT matrices ainsi. Tous les tests ont été effectués en utilisant une double précision sur exactement la même matrice à chaque exécution (sauf Octave).

Disclaimer-Je ne suis pas un expert en algèbre linéaire, pas affilié à l'une des bibliothèques ci-dessus et ce n'est pas un benchmark rigoureux. C'est un test "fait maison", car j'étais intéressé à comparer L'augmentation des performances de JDK 1.7 à 1.6 ainsi que commons math SVD à jlapack.

Il y a un benchmark de divers paquets matriciels disponibles en java sur http://code.google.com/p/java-matrix-benchmark/ pour quelques configurations matérielles différentes. Mais cela ne remplace pas votre propre benchmark.

Les performances vont varier en fonction du type de matériel que vous avez (cpu, cœurs, mémoire, cache L1-3, Vitesse du bus), de la taille des matrices et des algorithmes que vous avez l'intention d'utiliser. Différentes bibliothèques ont des prises différentes sur la concurrence pour différentes algorithmes, donc il n'y a pas de réponse unique. Vous pouvez également constater que la surcharge de la traduction vers le formulaire attendu par une bibliothèque native annule l'avantage de performance pour votre cas d'utilisation (certaines bibliothèques java ont des options plus flexibles concernant le stockage matriciel, qui peuvent être utilisées pour d'autres optimisations de performances).

En général, JAMA, Jampack et COLT vieillissent et ne représentent pas l'état des performances actuelles disponibles en Java pour l'algèbre linéaire. Plus les bibliothèques modernes utilisent plus efficacement plusieurs cœurs et caches cpu. JAMA était une implémentation de référence, et implémente à peu près des algorithmes de manuels scolaires avec peu de respect pour les performances. COLT et IBM Ninja ont été les premières bibliothèques java à montrer que les performances étaient possibles en java, même si elles accusaient un retard de 50% par rapport aux bibliothèques natives.

Je ne peux pas vraiment commenter des bibliothèques spécifiques, mais en principe, il y a peu de raisons pour que de telles opérations soient plus lentes en Java. Hotspot fait généralement le genre de choses que vous attendez d'un compilateur: il compile les opérations mathématiques de base sur les variables Java aux instructions Machine correspondantes (il utilise des instructions SSE, mais seulement une par opération); les accès aux éléments d'un tableau sont compilés pour utiliser des instructions MOV "brutes" comme vous le souhaitez; il prend des décisions sur la façon enregistre quand il le peut; il réorganise les instructions pour tirer parti de l'architecture du processeur... Une exception possible est que, comme je l'ai mentionné, Hotspot n'effectuera qu'une seule opération par instruction SSE; en principe, vous pourriez avoir une bibliothèque matricielle fantastiquement optimisée qui effectue plusieurs opérations par instruction, bien que je ne sache pas si, disons, votre bibliothèque Fortran particulière le fait ou si une telle bibliothèque existe même. Si c'est le cas, il n'y a actuellement aucun moyen pour Java (ou au moins, Hotspot) pour rivaliser avec cela (bien que vous puissiez bien sûr écrire votre propre bibliothèque native avec ces optimisations à appeler à partir de Java).

Alors qu'est-ce que tout cela signifie? Eh bien:

• en principe, il vaut la peine de chercher une bibliothèque plus performante, même si malheureusement je ne peux pas en recommander une
• si la performance est vraiment critique pour vous, je considérerais simplement coder vos propres opérations matricielles, car vous pourrez alors effectuer certaines optimisations qu'une bibliothèque en général impossible, ou qu'une bibliothèque particulière que vous utilisez ne le fait pas (si vous avez une machine multiprocesseur, découvrez si la Bibliothèque est réellement multithread)

Un obstacle aux opérations matricielles est souvent des problèmes de localisation de données qui surviennent lorsque vous devez parcourir à la fois Ligne par ligne et colonne par colonne, par exemple dans la multiplication matricielle, puisque vous devez stocker les données dans un ordre qui optimise l'un ou l'autre. Mais si vous écrivez le code à la main, vous pouvez parfois combiner des opérations pour optimiser localité de données (par exemple, si vous multipliez une matrice par sa transformation, vous pouvez transformer une traversée de colonne en une traversée de ligne si vous écrivez une fonction dédiée au lieu de combiner deux fonctions de bibliothèque). Comme d'habitude dans la vie, une bibliothèque vous donnera des performances non optimales en échange d'un développement plus rapide; vous devez décider à quel point la performance est importante pour vous.

Nous avons utilisé COLT pour des calculs financiers sérieux assez grands et ont été très heureux avec elle. Dans notre code fortement profilé, nous n'avons presque jamais eu à remplacer une implémentation COLT par l'une des nôtres.

Dans leurs propres tests (évidemment pas indépendants), je pense qu'ils prétendent dans un facteur de 2 des routines d'assembleur optimisées à la main Intel. L'astuce pour bien l'utiliser est de s'assurer que vous comprenez leur philosophie de conception et évitez les objets étrangers allocation.

Je suis l'auteur de la4j (algèbre linéaire pour Java) bibliothèque et voici mon point. Je travaille sur la4j depuis 3 ans (la dernière version est 0.4.0 [01 juin 2013]) et seulement maintenant je peux commencer à faire des analyses et des optimisations performace depuis que je viens de couvrir le minimum fonctionnel requis. Donc, la4j n'est pas aussi rapide que je le voulais, mais je passe beaucoup de temps à le changer.

Je suis actuellement au milieu du portage de la nouvelle version de la4j vers la plate-forme JMatBench. J'espère la nouvelle version montrera de meilleures performances que la précédente, car il y a plusieurs améliorations que j'ai apportées à la4j, telles que le format matriciel interne beaucoup plus rapide, les accesseurs dangereux et l'algorithme de blocage rapide pour les multiplications matricielles.

Avez-vous jeté un coup d'œil à la Bibliothèque du noyau Intel Math? Il prétend surpasser même ATLAS . MKL peut être utilisé en Java via des wrappers JNI.

Le code Linalg qui repose fortement sur les Pentiums et les capacités de calcul vectoriel des processeurs ultérieurs (en commençant par les extensions MMX, comme LAPACK et maintenant Atlas BLAS) n'est pas "fantastiquement optimisé", mais simplement standard de l'industrie. Pour répliquer cette performance en Java, vous aurez besoin de bibliothèques natives. J'ai eu le même problème de performance que vous décrivez (principalement, pour pouvoir calculer les décompositions de Choleski) et n'ai rien trouvé de vraiment efficace: Jama est pur Java, puisqu'il est censé être juste un modèle et un kit de référence pour les implémenteurs à suivre... qui n'est jamais arrivé. Vous savez Apache mathématiques communes... Quant à COLT, je dois encore le tester mais il semble compter fortement sur les améliorations Ninja, dont la plupart ont été atteintes en construisant un compilateur Java ad-hoc, donc je doute que cela va aider. À ce stade, je pense que nous avons "juste" besoin d'un effort collectif pour construire une implémentation Jama native...

Construire sur le post de Varkhan que le code natif spécifique à Pentium ferait mieux:

• JBLAS: un projet alpha-stage avec des wrappers JNI pour Atlas: http://www.jblas.org .

  • article de blog de L'auteur: http://mikiobraun.blogspot.com/2008/10/matrices-jni-directbuffers-and-number.html .

• MTJ: un Autre projet de ce type: http://code.google.com/p/matrix-toolkits-java/

Vous pouvez consulter le projet jblas. C'est une bibliothèque Java relativement nouvelle qui utilise BLAS, LAPACK et ATLAS pour des opérations matricielles hautes performances.

Le développeur a posté quelques benchmarks dans lesquels jblas se démarque favorablement contre MTJ et Colt.

Pour les applications graphiques 3d le lwjgl.util vecteur de mise en œuvre réalisé mentionnés ci-dessus jblas par un facteur d'environ 3.

J'ai fait 1 million de multiplications matricielles d'un vec4 avec une matrice 4x4.

LWJGL terminé dans environ 18ms, jblas requis environ 60ms.

(Je suppose que l'approche JNI n'est pas très appropriée pour une application successive rapide de multiplications relativement petites. Puisque la traduction / mappage peut prendre plus de temps que l'exécution réelle de multiplication.)

Il y a aussi UJMP

Il existe de nombreuses bibliothèques d'algèbre linéaire java disponibles gratuitement. http://www.ujmp.org/java-matrix/benchmark/ Malheureusement, ce benchmark ne vous donne que des informations sur la multiplication matricielle (avec la transposition du test ne permet pas aux différentes bibliothèques d'exploiter leurs caractéristiques de conception respectives).

Ce que vous devriez regarder, c'est comment ces bibliothèques d'algèbre linéaire fonctionnent lorsqu'on leur demande de calculer diverses matrices décomposition. http://ojalgo.org/matrix_compare.html

J'ai trouvé que si vous créez beaucoup de matrices dimensionnelles élevées, Vous pouvez rendre Jama environ 20% plus rapide si vous le Modifiez pour utiliser un tableau à une seule dimension au lieu d'un tableau à deux dimensions. C'est parce que Java ne prend pas en charge les tableaux multidimensionnels aussi efficacement. IE. il crée un tableau de tableaux.

Colt le fait déjà, mais j'ai trouvé que C'est plus compliqué et plus puissant que Jama, ce qui peut expliquer pourquoi les fonctions simples sont plus lentes avec Colt.

Le réponse dépend vraiment de ce que vous faites. Jama ne supporte pas une fraction des choses que Colt peut faire qui font plus de différence.

Matrix Tookits Java (MTJ) a déjà été mentionné auparavant, mais peut-être vaut-il la peine de le mentionner à nouveau pour quelqu'un d'autre qui trébuche sur ce fil. Pour ceux qui sont intéressés, il semble qu'il soit également question que MTJ remplace la bibliothèque linalg dans apache commons math 2.0 , bien que je ne sache pas comment cela progresse ces derniers temps.

Vous devez ajouter Apache Mahout à votre liste de courses.