Rendimiento de las bibliotecas matemáticas de matriz de Java? [cerrado]

Estamos calculando algo cuyo tiempo de ejecución está sujeto a operaciones matriciales. (Algunos detalles a continuación si está interesado). Esta experiencia provocó la siguiente pregunta:

¿Las personas tienen experiencia con el rendimiento de las bibliotecas Java para las matemáticas de matriz (por ejemplo, multiplicar, inversa, etc.)? Por ejemplo:

• Jamaica
• POTRO
• Matemáticas comunes de Apache

Busqué y no encontré nada.

Detalles de nuestra comparación de velocidad:

Estamos utilizando Intel FORTRAN (ifort (IFORT) 10.1 20070913). Lo hemos reimplementado en Java (1.6) utilizando operaciones de matriz de Mache 1.2 de Apache commons, y acepta todos sus dígitos de precisión. (Tenemos razones para quererlo en Java). (Java duplica, Fortran real * 8). Fortran: 6 minutos, Java 33 minutos, misma máquina. La creación de perfiles de jvisualm muestra mucho tiempo invertido en RealMatrixImpl. {getEntry, isValidCoordinate} (que parece haber desaparecido en Apache commons math 2.0, pero 2.0 no es más rápido). Fortran está utilizando rutinas Atlas BLAS (dpotrf, etc.).

Obviamente, esto podría depender de nuestro código en cada idioma, pero creemos que la mayor parte del tiempo está en operaciones de matriz equivalentes.

En varios otros cálculos que no involucran bibliotecas, Java no ha sido mucho más lento y, a veces, mucho más rápido.

Solo para agregar mis 2 centavos. He comparado algunas de estas bibliotecas. Intenté matricular una matriz de 3000 por 3000 de dobles consigo misma. Los resultados son los siguientes.

Utilizando ATLAS multiproceso con C / C ++, Octave, Python y R, el tiempo necesario fue de alrededor de 4 segundos.

Usando Jama con Java, el tiempo necesario fue de 50 segundos.

Usando Colt y Parallel Colt con Java, ¡el tiempo necesario fue de 150 segundos!

Usando JBLAS con Java, el tiempo que tomó fue nuevamente alrededor de 4 segundos ya que JBLAS usa ATLAS multiproceso.

Entonces, para mí estaba claro que las bibliotecas de Java no funcionaban demasiado bien. Sin embargo, si alguien tiene que codificar en Java, entonces la mejor opción es JBLAS. Jama, Colt y Parallel Colt no son rápidos.

Soy el autor de Java Matrix Benchmark ( JMatBench ) y reflexionaré sobre esta discusión.

Hay una diferencia significativa entre las bibliotecas de Java y, si bien no hay un ganador claro en toda la gama de operaciones, hay algunos líderes claros como se puede ver en los últimos resultados de rendimiento (octubre de 2013).

Si está trabajando con matrices "grandes" y puede usar bibliotecas nativas, entonces el claro ganador (aproximadamente 3.5 veces más rápido) es MTJ con netlib optimizado del sistema . Si necesita una solución Java pura , MTJ , OjAlgo , EJML y Parallel Colt son buenas opciones. Para matrices pequeñas, EJML es el claro ganador.

Las bibliotecas que no mencioné mostraron problemas de rendimiento significativos o faltaban características clave.

Soy el autor principal de jblas y quería señalar que lancé la versión 1.0 a fines de diciembre de 2009. Trabajé mucho en el empaque, lo que significa que ahora puede descargar un "tarro gordo" con las bibliotecas ATLAS y JNI. para Windows, Linux, Mac OS X, 32 y 64 bits (excepto para Windows). De esta forma obtendrá el rendimiento nativo simplemente agregando el archivo jar a su classpath. ¡Compruébalo en http://jblas.org !

Realmente no puedo comentar sobre bibliotecas específicas, pero en principio hay pocas razones para que tales operaciones sean más lentas en Java. Hotspot generalmente hace el tipo de cosas que esperaría que hiciera un compilador: compila operaciones matemáticas básicas sobre variables Java a las instrucciones correspondientes de la máquina (usa instrucciones SSE, pero solo una por operación); los accesos a elementos de una matriz se compilan para usar instrucciones MOV "en bruto" como era de esperar; toma decisiones sobre cómo asignar variables a los registros cuando puede; reordena las instrucciones para aprovechar la arquitectura del procesador ... Una posible excepción es que, como mencioné, Hotspot solo realizará una operación por instrucción SSE; en principio, podría tener una biblioteca matricial fantásticamente optimizada que realizara múltiples operaciones por instrucción, aunque yo no ' No sé si, por ejemplo, su biblioteca FORTRAN en particular lo hace o si existe tal biblioteca. Si lo hace, actualmente no hay forma de que Java (o al menos, Hotspot) compita con eso (aunque, por supuesto, podría escribir su propia biblioteca nativa con esas optimizaciones para llamar desde Java).

Entonces, ¿qué significa todo esto? Bien:

• en principio, vale la pena buscar una biblioteca con mejor rendimiento, aunque desafortunadamente no puedo recomendar una.
• si el rendimiento es realmente crítico para usted, consideraría simplemente codificar sus propias operaciones matriciales, porque entonces puede realizar ciertas optimizaciones que una biblioteca generalmente no puede, o que una biblioteca particular que está usando no lo hace (si tiene un máquina multiprocesador, averigüe si la biblioteca es realmente multiproceso)

Un obstáculo para las operaciones de matriz a menudo son los problemas de localidad de datos que surgen cuando necesita atravesar tanto fila por fila como columna por columna, por ejemplo, en la multiplicación de matrices, ya que debe almacenar los datos en un orden que optimice uno u otro. Pero si escribe el código a mano, a veces puede combinar operaciones para optimizar la localidad de los datos (por ejemplo, si está multiplicando una matriz por su transformación, puede convertir un recorrido de columna en un recorrido de fila si escribe una función dedicada en lugar de combinar dos funciones de biblioteca). Como es habitual en la vida, una biblioteca le dará un rendimiento no óptimo a cambio de un desarrollo más rápido; debe decidir cuán importante es el rendimiento para usted.

Acabo de comparar Apache Commons Math con jlapack.

Prueba: descomposición de valores singulares de una matriz aleatoria de 1024x1024.

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

Código de octava: A = rand (1024); tic; [U, S, V] = svd (A); toc

tiempo de ejecución de resultados
-------------------------------------------------- -------
Octava 36.34 segundos

JDK 1.7u2 64bit
    jlapack dgesvd 37.78 sec
    apache commons matemática SVD 42.24 sec


JDK 1.6u30 64bit
    jlapack dgesvd 48.68 sec
    apache commons matemática SVD 50.59 sec

Rutinas nativas
Lapack * invocado desde C: 37.64 sec
Intel MKL 6.89 segundos (!)

Mi conclusión es que jlapack llamado desde JDK 1.7 está muy cerca del rendimiento binario nativo de lapack. Utilicé la biblioteca binaria lapack que viene con Linux distro e invoqué la rutina dgesvd para obtener también las matrices U, S y VT. Todas las pruebas se realizaron con doble precisión exactamente en la misma matriz en cada ejecución (excepto Octave).

Descargo de responsabilidad: no soy un experto en álgebra lineal, no estoy afiliado a ninguna de las bibliotecas anteriores y este no es un punto de referencia riguroso. Es una prueba 'hecha en casa', ya que estaba interesado en comparar el aumento de rendimiento de JDK 1.7 a 1.6, así como el SVD matemático de commons a jlapack.

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

• envuelve la biblioteca Eigen C ++ http://eigen.tuxfamily.org , que es una de las bibliotecas C ++ gratuitas más rápidas disponibles
• sintaxis relativamente breve, por ejemplo, 'mmul', 'sub'
• maneja matrices densas y dispersas

Una prueba rápida, multiplicando dos matrices densas, es decir:

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

Resultados:

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

• En comparación con jama, todo es más rápido :-P
• En comparación con jblas, Jeigen no es tan rápido, pero maneja matrices dispersas.
• En comparación con el ojalgo, Jeigen tarda aproximadamente la misma cantidad de tiempo transcurrido, pero solo usa un núcleo, por lo que Jeigen usa la mitad de la CPU total. Jeigen tiene una sintaxis terser, es decir, 'mmul' versus 'multiplyRight'

Hay un punto de referencia de varios paquetes de matriz disponibles en Java en http://code.google.com/p/java-matrix-benchmark/ para algunas configuraciones de hardware diferentes. Pero no es un sustituto para hacer su propio punto de referencia.

El rendimiento variará según el tipo de hardware que tenga (CPU, núcleos, memoria, caché L1-3, velocidad del bus), el tamaño de las matrices y los algoritmos que pretende utilizar. Las diferentes bibliotecas tienen diferentes tomas de concurrencia para diferentes algoritmos, por lo que no hay una respuesta única. También puede encontrar que la sobrecarga de traducir al formulario esperado por una biblioteca nativa niega la ventaja de rendimiento para su caso de uso (algunas de las bibliotecas de Java tienen opciones más flexibles con respecto al almacenamiento matricial, que se pueden utilizar para optimizar el rendimiento)

Sin embargo, en general, JAMA, Jampack y COLT se están volviendo viejos y no representan el estado del rendimiento actual disponible en Java para álgebra lineal. Las bibliotecas más modernas hacen un uso más efectivo de múltiples núcleos y cachés de CPU. JAMA fue una implementación de referencia, y prácticamente implementa algoritmos de libros de texto con poca consideración al rendimiento. COLT e IBM Ninja fueron las primeras bibliotecas de Java en mostrar que el rendimiento era posible en Java, incluso si se quedaban un 50% por detrás de las bibliotecas nativas.

Soy el autor de la biblioteca la4j (Linear Algebra for Java) y aquí está mi punto. He estado trabajando en la4j durante 3 años (la última versión es 0.4.0 [01 de junio de 2013]) y solo ahora puedo comenzar a hacer análisis de rendimiento y optimizaciones ya que acabo de cubrir el mínimo funcional requerido. Entonces, la4j no es tan rápido como quería, pero estoy gastando mucho tiempo para cambiarlo.

Actualmente estoy en el medio de portar una nueva versión de la4j a la plataforma JMatBench . Espero que la nueva versión muestre un mejor rendimiento que la anterior, ya que hay varias mejoras que hice en la4j, como un formato de matriz interna mucho más rápido, accesores inseguros y un algoritmo de bloqueo rápido para multiplicaciones de matriz.

El código Linalg que se basa en gran medida en las capacidades de computación vectorial de los procesadores Pentium y posteriores (comenzando con las extensiones MMX, como LAPACK y ahora Atlas BLAS) no está "fantásticamente optimizado", sino simplemente estándar de la industria. Para replicar ese rendimiento en Java, necesitará bibliotecas nativas. He tenido el mismo problema de rendimiento que usted describe (principalmente, para poder calcular las descomposiciones de Choleski) y no he encontrado nada realmente eficiente: Jama es Java puro, ya que se supone que es solo una plantilla y un kit de referencia para que los implementadores lo sigan. .. lo que nunca sucedió. Ya sabes los comunes de matemáticas de Apache ... En cuanto a COLT, todavía tengo que probarlo, pero parece depender en gran medida de las mejoras de Ninja, la mayoría de las cuales se lograron mediante la construcción de un compilador ad-hoc de Java, por lo que dudo que sea útil. En ese punto, creo que "

Hemos utilizado COLT para algunos cálculos financieros serios bastante grandes y estamos muy contentos con él. En nuestro código altamente perfilado casi nunca hemos tenido que reemplazar una implementación COLT con una propia.

En sus propias pruebas (obviamente no independientes), creo que afirman dentro de un factor de 2 de las rutinas de ensamblador optimizadas a mano de Intel. El truco para usarlo bien es asegurarse de que comprende su filosofía de diseño y evitar la asignación de objetos extraños.

¿Has echado un vistazo a la Intel Math Kernel Library ? Afirma superar incluso a ATLAS . MKL se puede usar en Java a través de contenedores JNI.

Sobre la base de la publicación de Varkhan, que el código nativo específico de Pentium sería mejor:

• jBLAS: un proyecto de etapa alfa con contenedores JNI para Atlas: http://www.jblas.org .

  • Publicación en el blog del autor: http://mikiobraun.blogspot.com/2008/10/matrices-jni-directbuffers-and-number.html .

• MTJ: Otro proyecto similar : http://code.google.com/p/matrix-toolkits-java/

Es posible que desee consultar el proyecto jblas . Es una biblioteca Java relativamente nueva que utiliza BLAS, LAPACK y ATLAS para operaciones matriciales de alto rendimiento.

El desarrollador ha publicado algunos puntos de referencia en los que jblas se presenta favorablemente contra MTJ y Colt.

Para las aplicaciones de gráficos en 3D, la implementación del vector lwjgl.util superó a las jblas mencionadas anteriormente en un factor de aproximadamente 3.

He hecho 1 millón de multiplicaciones matriciales de un vec4 con una matriz 4x4.

lwjgl terminó en unos 18 ms, jblas requirió unos 60 ms.

(Supongo que el enfoque JNI no es muy adecuado para la aplicación rápida y sucesiva de multiplicaciones relativamente pequeñas. Dado que la traducción / mapeo puede llevar más tiempo que la ejecución real de la multiplicación).

He descubierto que si está creando muchas matrices de alta dimensión, puede hacer que Jama sea un 20% más rápido si lo cambia para usar una matriz unidimensional en lugar de una matriz bidimensional. Esto se debe a que Java no admite matrices multidimensionales de manera tan eficiente. es decir. crea una matriz de matrices.

Colt ya hace esto, pero he descubierto que es más complicado y poderoso que Jama, lo que puede explicar por qué las funciones simples son más lentas con Colt.

La respuesta realmente depende de lo que estés haciendo. Jama no admite una fracción de las cosas que Colt puede hacer, lo que hace una gran diferencia.

También hay UJMP

Hay muchas bibliotecas de álgebra lineal de Java disponibles de forma gratuita. http://www.ujmp.org/java-matrix/benchmark/ Lamentablemente, ese punto de referencia solo le brinda información sobre la multiplicación de matrices (con la transposición de la prueba no permite que las diferentes bibliotecas exploten sus respectivas características de diseño).

Lo que debe observar es cómo funcionan estas bibliotecas de álgebra lineal cuando se le pide que calcule varias descomposiciones de matriz. http://ojalgo.org/matrix_compare.html

Matrix Tookits Java (MTJ) ya se mencionó anteriormente, pero quizás valga la pena mencionar nuevamente para cualquier otra persona que se encuentre con este hilo. Para aquellos interesados, parece que también se habla de que MTJ reemplace la biblioteca linalg en apache commons math 2.0 , aunque no estoy seguro de cómo está progresando últimamente.

Debe agregar Apache Mahout a su lista de compras.