Performances des bibliothèques mathématiques matricielles Java? [fermé]

Nous calculons quelque chose dont le runtime est lié par des opérations matricielles. (Quelques détails ci-dessous si vous êtes intéressé.) Cette expérience a soulevé la question suivante:

Les gens ont-ils une expérience des performances des bibliothèques Java pour les mathématiques matricielles (par exemple, multiplier, inverser, etc.)? Par exemple:

• JAMA
• POULAIN
• Mathématiques Apache commons

J'ai cherché et je n'ai rien trouvé.

Détails de notre comparaison de vitesse:

Nous utilisons Intel FORTRAN (ifort (IFORT) 10.1 20070913). Nous l'avons réimplémenté en Java (1.6) en utilisant les opérations matricielles Apache commons math 1.2, et il accepte tous ses chiffres de précision. (Nous avons des raisons de le vouloir en Java.) (Java double, Fortran real * 8). Fortran: 6 minutes, Java 33 minutes, même machine. Le profilage jvisualm montre beaucoup de temps passé dans RealMatrixImpl. {getEntry, isValidCoordinate} (qui semblent avoir disparu dans Apache commons math 2.0, mais 2.0 n'est pas plus rapide). Fortran utilise les routines Atlas BLAS (dpotrf, etc.).

Évidemment, cela pourrait dépendre de notre code dans chaque langage, mais nous pensons que la plupart du temps est en opérations matricielles équivalentes.

Dans plusieurs autres calculs qui n'impliquent pas de bibliothèques, Java n'a pas été beaucoup plus lent, et parfois beaucoup plus rapide.

Juste pour ajouter mes 2 cents. J'ai comparé certaines de ces bibliothèques. J'ai essayé de multiplier par matrice une matrice de 3000 par 3000 de doubles avec elle-même. Les résultats sont les suivants.

En utilisant ATLAS multithread avec C / C ++, Octave, Python et R, le temps pris était d'environ 4 secondes.

En utilisant Jama avec Java, le temps nécessaire était de 50 secondes.

En utilisant Colt et Parallel Colt avec Java, le temps pris était de 150 secondes!

En utilisant JBLAS avec Java, le temps pris était à nouveau d'environ 4 secondes car JBLAS utilise ATLAS multithread.

Donc, pour moi, il était clair que les bibliothèques Java ne fonctionnaient pas très bien. Cependant, si quelqu'un doit coder en Java, la meilleure option est JBLAS. Jama, Colt et Parallel Colt ne sont pas rapides.

Je suis l'auteur de Java Matrix Benchmark ( JMatBench ) et je vais donner mon avis sur cette discussion.

Il existe des différences significatives entre les bibliothèques Java et, bien qu'il n'y ait pas de gagnant clair sur l'ensemble de la gamme des opérations, il existe quelques leaders clairs, comme le montrent les derniers résultats de performance (octobre 2013).

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

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

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

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 en instructions machine correspondantes (il utilise des instructions SSE, mais une seule par opération); les accès aux éléments d'un tableau sont compilés pour utiliser des instructions MOV "brutes" comme vous vous en doutez; il prend des décisions sur la façon d'allouer des variables aux registres 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 de matrices fantastiquement optimisée qui effectue plusieurs opérations par instruction, même si je ne le fais pas. t savoir si, par exemple, 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 du moins, Hotspot) de rivaliser avec cela (bien que vous puissiez bien sûr écrire votre propre bibliothèque native avec ces optimisations à appeler depuis Java).

Donc qu'est-ce que tout cela veut dire? Bien:

• en principe, cela vaut la peine de chercher une bibliothèque plus performante, même si malheureusement je ne peux pas en recommander une
• si les performances sont vraiment essentielles pour vous, j'envisagerais simplement de coder vos propres opérations matricielles, car vous pourrez peut-être alors effectuer certaines optimisations qu'une bibliothèque ne peut généralement pas, ou qu'une bibliothèque particulière que vous utilisez ne fait pas (si vous avez un 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 des données qui surviennent lorsque vous devez parcourir à la fois ligne par ligne et colonne par colonne, par exemple dans la multiplication de matrice, car vous devez stocker les données dans un ordre qui optimise l'une ou l'autre. Mais si vous écrivez manuellement le code, vous pouvez parfois combiner des opérations pour optimiser la localisation des données (par exemple, si vous multipliez une matrice par sa transformation, vous pouvez transformer un parcours de colonne en un parcours 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 offrira des performances non optimales en échange d'un développement plus rapide; vous devez décider à quel point la performance est importante pour vous.

Je viens de comparer Apache Commons Math avec jlapack.

Test: décomposition en valeurs singulières d'une matrice aléatoire de 1024x1024.

Machine: Processeur Intel (R) Core (TM) 2 Duo E6750 à 2,66 GHz, Linux x64

Code d'octave: A = rand (1024); tic; [U, S, V] = svd (A); toc

temps d'exécution des résultats
-------------------------------------------------- -------
Octave 36,34 sec

JDK 1.7u2 64 bits
    dgesvd jlapack 37,78 sec
    apache commons math SVD 42,24 sec


JDK 1.6u30 64 bits
    dgesvd jlapack 48,68 sec
    apache commons math SVD 50,59 sec

Routines natives
Lapack * invoqué depuis C: 37,64 s
Intel MKL 6,89 s (!)

Ma conclusion est que jlapack appelé depuis JDK 1.7 est très proche des performances binaires natives de lapack. J'ai utilisé la bibliothèque binaire lapack fournie avec la distribution linux et j'ai appelé la routine dgesvd pour obtenir également les matrices U, S et VT. Tous les tests ont été effectués en double précision sur exactement la même matrice à chaque exécution (sauf Octave).

Avertissement - Je ne suis pas un expert en algèbre linéaire, je ne suis affilié à aucune des bibliothèques ci-dessus et ce n'est pas une référence rigoureuse. C'est un test «fait maison», car j'étais intéressé par la comparaison de l'augmentation des performances de JDK 1.7 à 1.6 ainsi que des mathématiques communes SVD à jlapack.

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

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

Un test rapide, en multipliant deux matrices denses, soit:

import statique jeigen.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

• Comparé à jama, tout est plus rapide :-P
• Comparé à jblas, Jeigen n'est pas aussi rapide, mais il gère des matrices clairsemées.
• Comparé à ojalgo, Jeigen prend à peu près le même temps écoulé, mais n'utilise qu'un seul cœur, donc Jeigen utilise la moitié du processeur total. Jeigen a une syntaxe terser, c'est-à-dire 'mmul' versus 'multiplyRight'

Il existe un benchmark de divers packages de matrice disponibles en java sur http://code.google.com/p/java-matrix-benchmark/ pour quelques configurations matérielles différentes. Mais ce n'est pas un substitut pour faire votre propre benchmark.

Les performances vont varier selon le type de matériel dont vous disposez (processeur, cœurs, mémoire, cache L1-3, vitesse du bus), la taille des matrices et les algorithmes que vous comptez utiliser. Différentes bibliothèques ont des points de vue différents sur la concurrence pour différents algorithmes, il n'y a donc pas de réponse unique. Vous pouvez également constater que la surcharge de la traduction vers la forme attendue par une bibliothèque native annule l'avantage de performances pour votre cas d'utilisation (certaines des bibliothèques java ont des options plus flexibles concernant le stockage matriciel, qui peuvent être utilisées pour d'autres optimisations des performances).

Cependant, 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. Les bibliothèques plus 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 avec peu de considération 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 suis l'auteur de la bibliothèque la4j (Linear Algebra for Java) et voici mon point. Je travaille sur la4j depuis 3 ans (la dernière version est la 0.4.0 [01 juin 2013]) et ce n'est que maintenant que je peux commencer à faire des analyses de performances et des optimisations puisque je viens de couvrir la fonctionnalité minimale requise. Donc, la4j n'est pas aussi rapide que je le souhaitais mais je passe beaucoup de temps à le changer.

Je suis actuellement en train de porter une nouvelle version de la4j sur la plate- forme JMatBench . J'espère que la nouvelle version affichera de meilleures performances que la précédente car il y a plusieurs améliorations que j'ai apportées à la4j, telles qu'un format de matrice interne beaucoup plus rapide, des accesseurs dangereux et un algorithme de blocage rapide pour les multiplications de matrice.

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

Nous avons utilisé COLT pour de gros calculs financiers sérieux et nous en avons été très satisfaits. 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 Intel optimisées à la main. L'astuce pour bien l'utiliser est de s'assurer que vous comprenez leur philosophie de conception et d'éviter l'allocation d'objets superflus.

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

S'appuyant sur le post de Varkhan selon lequel le code natif spécifique à Pentium ferait mieux:

• jBLAS: Un projet en phase alpha 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 voudrez peut-être consulter le projet jblas . Il s'agit d'une bibliothèque Java relativement nouvelle qui utilise BLAS, LAPACK et ATLAS pour des opérations matricielles hautes performances.

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

Pour les applications graphiques 3D, l'implémentation du vecteur lwjgl.util a surpassé les jblas mentionnés ci-dessus d'un facteur d'environ 3.

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

lwjgl a terminé en environ 18 ms, jblas a nécessité environ 60 ms.

(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 la multiplication.)

J'ai trouvé que si vous créez beaucoup de matrices de haute dimension, 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. En effet, Java ne prend pas en charge les tableaux multidimensionnels aussi efficacement. c'est à dire. 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.

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

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 (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 décompositions matricielles. http://ojalgo.org/matrix_compare.html

Matrix Tookits Java (MTJ) a déjà été mentionné auparavant, mais cela vaut peut-être la peine de le mentionner à nouveau pour quiconque tombe 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 , même si je ne suis pas sûr de la façon dont cela progresse ces derniers temps.

Vous devez ajouter Apache Mahout à votre liste de courses.