studio nxn matriz matrices ejemplos bidimensionales arreglos 3x3 java math matrix performance

nxn - ¿Desempeño de las bibliotecas matemáticas de Matriz Java?



matriz 3x3 java (20)

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

Estamos calculando algo cuyo tiempo de ejecución está vinculado por las operaciones de la matriz. (A continuación, algunos detalles si están interesados.) Esta experiencia generó la siguiente pregunta:

¿La gente tiene experiencia con el rendimiento de las bibliotecas Java para las matemáticas matriciales (por ejemplo, multiplicar, invertir, etc.)? Por ejemplo:

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) usando las operaciones de matriz matemática Apache commons math 1.2, y está de acuerdo con todos sus dígitos de precisión. (Tenemos razones para quererlo en Java.) (Java dobles, Fortran real * 8). Fortran: 6 minutos, Java 33 minutos, misma máquina. jvisualm profiling muestra mucho tiempo invertido en RealMatrixImpl. {getEntry, isValidCoordinate} (que parece haber desaparecido en los juegos de 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ía del tiempo está en operaciones de matriz equivalentes.

En muchos otros cómputos que no involucran bibliotecas, Java no ha sido mucho más lento, y algunas veces mucho más rápido.

¿No estás, por casualidad, golpeando en la versión de Java? El hecho de que esté pasando la mayor parte de su tiempo en getEntry () es una pista de que esto está sucediendo.

El otro problema que puedo ver con Commons-Math es que la matriz se administra como una matriz bidimensional. Si bien no espero que la doble desreferencia requerida sea la causa de la desaceleración, sí significa que las filas individuales (suponiendo [rowIdx] [colIdx]) son de hecho objetos separados que serán tratados individualmente por el GC. ¿Estás pasando mucho tiempo en GC?

Acabo de comparar Apache Commons Math con jlapack.

Prueba: descomposición de valor singular de una matriz aleatoria de 1024x1024.

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

Código de octava: 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(!)

Mi conclusión es que jlapack llamado desde JDK 1.7 está muy cerca del rendimiento binario nativo de lapack. Usé la biblioteca binaria lapack que viene con la distribución de Linux e invoqué la rutina dgesvd para obtener las matrices U, S y VT también. Todas las pruebas se realizaron con doble precisión en exactamente 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 me interesaba comparar el aumento del rendimiento de JDK 1.7 a 1.6, así como SVD de matemáticas comunes con jlapack.

Debe agregar Apache Mahout a su lista de compras.

El código de Linalg que depende en gran medida de Pentiums y las capacidades de computación vectorial de los procesadores posteriores (comenzando con las extensiones de 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 descomposiciones de Choleski) y no he encontrado nada realmente eficiente: Jama es pura Java, ya que se supone que es solo una plantilla y un kit de referencia para los implementadores. .. que nunca sucedió Conoces los recursos comunes matemáticos 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 creación de un compilador de Java ad hoc, así que dudo que vaya a ayudar. En ese momento, creo que "solo" necesitamos un esfuerzo colectivo para construir una implementación nativa de Jama ...

Es posible que desee verificar el proyecto jblas . Es una biblioteca Java relativamente nueva que usa BLAS, LAPACK y ATLAS para operaciones de matriz de alto rendimiento.

El desarrollador ha publicado algunos benchmarks de benchmarks en los que jblas sale favorablemente en contra de MTJ y Colt.

Hay muchas bibliotecas de álgebra lineal de Java disponibles libremente. http://www.ujmp.org/java-matrix/benchmark/ Lamentablemente, el punto de referencia solo le brinda información sobre la multiplicación de matrices (con la transposición de la prueba no se 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

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 pretenda utilizar. Diferentes bibliotecas tienen diferentes aspectos de la concurrencia para diferentes algoritmos, por lo que no hay una sola respuesta. También puede encontrar que la sobrecarga de traducir a la forma esperada 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 pueden usarse para optimizaciones de rendimiento adicionales).

Sin embargo, en general, JAMA, Jampack y COLT están envejeciendo y no representan el estado del rendimiento actual disponible en Java para el á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 atenció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 retrasaban 50% de las bibliotecas nativas.

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

Colt ya lo hace, pero he descubierto que es más complicado y más 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 que hacen una gran diferencia.

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

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

Jeigen jeigen

  • envuelve la biblioteca de Eigen C ++ http://eigen.tuxfamily.org , que es una de las bibliotecas de C ++ gratuitas más rápidas disponibles
  • sintaxis relativamente escueta, 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

  • Comparado 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 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'' frente a ''multiplyRight''

Matrix Tookits Java (MTJ) ya se mencionó anteriormente, pero tal vez valga la pena mencionarlo nuevamente para cualquier persona que se tropiece con este hilo. Para los 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.

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

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

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

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

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 los tipos de cosas que uno espera que haga un compilador: compila operaciones matemáticas básicas en variables Java con las instrucciones de la máquina correspondientes (usa instrucciones SSE, pero solo una por operación); los accesos a los elementos de una matriz se compilan para usar instrucciones MOV "en bruto" como cabría esperar; toma decisiones sobre cómo asignar variables a los registros cuando puede; reordena instrucciones para aprovechar la arquitectura del procesador ... Una posible excepción es que, como he mencionado, el Hotspot solo realizará una operación por instrucción SSE; en principio, podría tener una biblioteca de matriz fantásticamente optimizada que realiza múltiples operaciones por instrucción, aunque no sé si, por ejemplo, su biblioteca FORTRAN particular lo hace o si tal biblioteca existe. 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 de mejor rendimiento, aunque desafortunadamente no puedo recomendar uno
  • 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 su biblioteca no usa (si tiene una máquina multiprocesador, averigüe si la biblioteca es en realidad multiprocesador)

Un obstáculo para las operaciones matriciales es a menudo problemas de ubicación de datos que surgen cuando se necesita recorrer fila por fila y 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 manualmente el código, a veces puede combinar operaciones para optimizar la ubicación de los datos (por ejemplo, si está multiplicando una matriz por su transformación, puede convertir un cruce de columnas en un cruce de filas si escribe una función dedicada en lugar de combinar dos funciones de biblioteca). Como es habitual en la vida, una biblioteca le ofrecerá un rendimiento no óptimo a cambio de un desarrollo más rápido; debes decidir qué tan importante es para ti el rendimiento.

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

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

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

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

Al usar JBLAS con Java, el tiempo empleado fue de nuevo de 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 voy a dar mi opinión sobre esta discusión.

Hay una gran diferencia entre las bibliotecas de Java y aunque 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 ganador claro (aproximadamente 3.5 veces más rápido) es MTJ con netlib optimizado para el sistema . Si necesita una solución pura de Java, MTJ , OjAlgo , EJML y Parallel Colt son buenas opciones. Para matrices pequeñas, EJML es el claro ganador.

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

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

Actualmente estoy en el medio de portar la nueva versión de la4j a la plataforma http://code.google.com/p/java-matrix-benchmark/ . 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, accesos inseguros y un algoritmo de bloqueo rápido para las multiplicaciones de matrices.

Soy el autor principal de jblas y quería señalar que publiqué la versión 1.0 a finales de diciembre de 2009. Trabajé mucho en el paquete, lo que significa que ahora puede simplemente descargar un "contenedor de grasa" 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 jblas !