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

151

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:

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.

dfrankow
la source
Les opérations mathématiques matricielles délicates sont au moins O (n ^ 3) ... le pire s'aggrave, je suppose que vous pourriez chronométrer et tester ...
Calyth
2
Pourquoi avez-vous besoin d'inverses? Pour presque toutes les applications, vous n'avez pas besoin de l'inverse réel. Calculer l'inverse est une mauvaise idée en raison de problèmes de stabilité.
Ying Xiao
1
@Calyth: Oui, nous pourrions chronométrer. Je me demandais si d'autres l'avaient déjà fait. @Ying Xiao: Oui, les inversions sont à éviter. Cependant, ce calcul semble le plus simple à utiliser. Voir en.wikipedia.org/wiki/… .
dfrankow
2
@Calyth C'est faux, il existe des méthodes plus efficaces que O (n ^ 3) utilisant une approche de division et de conquête.
starblue
1
Les performances natives les plus rapides proviennent de JCublas. Si vous avez besoin d'une algèbre linéaire rapide, vous avez besoin de GPU. JOCL avec clMath pourrait également fonctionner et être portable sur les processeurs (et même multi-plateforme sans recompilation), mais je ne l'ai pas testé.
Aleksandr Dubinsky

Réponses:

98

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.

Hamaad Shah
la source
3
Je suppose que vous utilisiez une machine multicœur, donc ces résultats sont fortement affectés par le fait que la bibliothèque utilise ou non le multicœur? Dans certains cas, par exemple quand on parallélisation à l' aide ou mpi Hadoop etc, le temps important est en fait la monoconducteurs fois, depuis la mise en œuvre mpi / Hadoop prend soin des choses parallélisation. (Au moins, pour moi, jblas était environ 2,5 plus rapide que jama, pas 10 fois plus rapide que jama comme vous l'avez.)
Hugh Perkins
17
Je viens de publier la v1.0 de netlib-java ... les performances sont à la hauteur (et dépassent parfois) le code Fortran, et il peut utiliser des natifs optimisés pour la machine sans aucune modification du code utilisateur. Veuillez en tenir compte lorsque vous recherchez des bibliothèques d'algèbre linéaire de bas niveau. Je maintiens également MTJ , qui utilise netlib-java. Dans Scala, utilisez Breeze (également alimenté par netlib-java)
fommil le
4
En utilisant ND4j et java - mon ordinateur portable relativement ancien complète la multiplication suggérée en 219 millis. Alors que python + numpy le complète en 349 millisecondes
bennyl
2
Et juste pour ajouter mon dernier commentaire sur l'utilisation de nd4j, j'ai utilisé la plate-forme native comme backend, si j'utilise la plate-forme cuda, cela prend environ 1 milliseconde
bennyl
Avez-vous publié votre code pour les benchmarks quelque part?
bruziuz
108

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.

Peter Abélès
la source
6
Je pensais juste que je mentionnerais que votre indice de référence est vraiment pratique! Merci d'y consacrer votre temps.
hohonuuli
1
JBLAS semble prendre en charge SVD à partir de septembre '13: mikiobraun.github.io/jblas/javadoc/org/jblas
...
travail merveilleux, merci beaucoup.
webpat
Y a-t-il une liste quelque part des bibliothèques que vous avez évaluées mais pour lesquelles vous n'avez pas publié de résultats, et les raisons de chacune?
Kevin Krumwiede le
1
MTJ semble abandonné: le référentiel est archivé et le dernier commit date de 2016.
Danila Piatov
51

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 !

Mikio Braun
la source
2
inspiré par votre travail, j'ai fait une chose similaire dans netlib-java ;-)
fommil
2
Haha, moi aussi, pour jeigen :-)
Hugh Perkins
JogAmp fait de même, voir jogamp-fat.jar. Bonne idée :)
gouessej
8

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.

Neil Coffey
la source
8

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.

isti_spl
la source
8

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'
Hugh Perkins
la source
Jeigen a l'air génial! J'ai récemment implémenté Eigen en Java en utilisant JNI et une DLL pour résoudre de très grandes matrices clairsemées. Ma version avec la DLL est plus de 20 plus rapide que le colt parallèle pour mes tests (plus de 8000x8000 matrices). J'aurais aimé connaître Jeigen!
Z boson
6

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.

culana
la source
4

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.

Vladimir Kostyukov
la source
1
Non - la4j n'est vraiment pas compétitif. Voir code.google.com/p/java-matrix-benchmark
Christopher Manning
Cela a beaucoup changé. J'ai publié deux versions de la bibliothèque depuis votre réponse. La version actuelle est la 0.4.0. Et ça vole juste.
Vladimir Kostyukov
3

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 "

Varkhan
la source
Bon point! Un projet en phase alpha avec des wrappers JNI pour Atlas: jblas.org . Article
dfrankow
3

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.

Nick Fortescue
la source
3

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.

Zach Scrivena
la source
2
Nous avons cela. a) Sa licence est plus restrictive qu'Atlas (nous ne pouvons donc pas utiliser tous nos ordinateurs); b) ce n'est pas Java (et comme je l'ai dit, nous avons des raisons de vouloir être en Java).
dfrankow
c'est-à-dire que ce n'est pas une réponse à ma question sur les bibliothèques Java (mais je n'ai pas la réputation de voter contre).
dfrankow
@dfrankow: J'ai mis à jour ma réponse pour répondre à votre inquiétude quant à son utilisation en Java.
Zach Scrivena
1
+1, si c'est la vitesse que vous recherchez, cela semble être la voie à suivre
Gab Royer
2
Le dernier lien est rompu.
gouessej
2

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.

Mark Reid
la source
2

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.)

Necrowizzard
la source
1

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.

Peter Lawrey
la source
1

Il y a aussi UJMP

Chad Okere
la source
0

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

Anders Peterson
la source
0

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.

Steve Lianoglou
la source
0

Vous devez ajouter Apache Mahout à votre liste de courses.

bmargulies
la source