Desempenho de bibliotecas matemáticas de matriz Java? [fechadas]

Estamos computando algo cujo tempo de execução é limitado pelas operações da matriz. (Alguns detalhes abaixo, se estiver interessado.) Essa experiência levou à seguinte pergunta:

As pessoas têm experiência com o desempenho de bibliotecas Java para matemática matricial (por exemplo, multiplicar, inversa, etc.)? Por exemplo:

• JAMA
• POTRO
• Apache commons math

Eu procurei e não encontrei nada.

Detalhes da nossa comparação de velocidade:

Estamos usando o Intel FORTRAN (ifort (IFORT) 10.1 20070913). Nós o reimplementamos em Java (1.6) usando operações matemáticas da matriz 1.2 do Apache commons, e ele concorda com todos os seus dígitos de precisão. (Temos razões para querer isso em Java.) (Java dobra, Fortran real * 8). Fortran: 6 minutos, Java 33 minutos, mesma máquina. O perfil do jvisualm mostra muito tempo gasto no RealMatrixImpl. {getEntry, isValidCoordinate} (que parece ter desaparecido no Apache commons math 2.0 não lançado, mas o 2.0 não é mais rápido). O Fortran está usando as rotinas Atlas BLAS (dpotrf, etc.).

Obviamente, isso pode depender do nosso código em cada idioma, mas acreditamos que na maioria das vezes esteja em operações matriciais equivalentes.

Em vários outros cálculos que não envolvem bibliotecas, o Java não foi muito mais lento e, às vezes, muito mais rápido.

Apenas para adicionar meus 2 centavos. Eu comparei algumas dessas bibliotecas. Tentei matricular multiplicar uma matriz de duplas de 3000 por 3000 com ela mesma. Os resultados são os seguintes.

Usando ATLAS multithread com C / C ++, Octave, Python e R, o tempo gasto foi de cerca de 4 segundos.

Usando o Jama com Java, o tempo gasto foi de 50 segundos.

Usando Colt e Parallel Colt com Java, o tempo gasto foi de 150 segundos!

Usando JBLAS com Java, o tempo gasto foi novamente em torno de 4 segundos, pois o JBLAS usa ATLAS multithread.

Então, para mim, ficou claro que as bibliotecas Java não tiveram um desempenho muito bom. No entanto, se alguém precisar codificar em Java, a melhor opção é JBLAS. Jama, Colt e Parallel Colt não são rápidos.

Sou o autor do Java Matrix Benchmark ( JMatBench ) e darei meus pensamentos sobre esta discussão.

Há uma diferença significativa entre as bibliotecas Java e, embora não haja um vencedor claro em toda a gama de operações, existem alguns líderes claros, como pode ser visto nos últimos resultados de desempenho (outubro de 2013).

Se você estiver trabalhando com matrizes "grandes" e puder usar bibliotecas nativas, o vencedor claro (cerca de 3,5x mais rápido) será o MTJ com netlib otimizado para o sistema . Se você precisar de uma solução Java pura, MTJ , OjAlgo , EJML e Parallel Colt são boas escolhas. Para matrizes pequenas, a EJML é a vencedora.

As bibliotecas que não mencionei apresentaram problemas significativos de desempenho ou estavam faltando os principais recursos.

Sou o principal autor do jblas e gostaria de salientar que lancei a versão 1.0 no final de dezembro de 2009. Trabalhei muito na embalagem, o que significa que agora você pode apenas baixar um "frasco de gordura" com as bibliotecas ATLAS e JNI para Windows, Linux, Mac OS X, 32 e 64 bits (exceto Windows). Dessa forma, você obterá o desempenho nativo apenas adicionando o arquivo jar ao seu caminho de classe. Confira em http://jblas.org !

Não posso realmente comentar sobre bibliotecas específicas, mas, em princípio, há poucas razões para essas operações serem mais lentas em Java. O hotspot geralmente faz o tipo de ação que você espera que um compilador faça: compila operações matemáticas básicas em variáveis ​​Java às instruções correspondentes da máquina (usa instruções SSE, mas apenas uma por operação); os acessos aos elementos de uma matriz são compilados para usar instruções MOV "brutas", como seria de esperar; toma decisões sobre como alocar variáveis ​​para registros quando possível; reordena as instruções para aproveitar a arquitetura do processador ... Uma possível exceção é que, como mencionei, o Hotspot executará apenas uma operação por instrução SSE; em princípio, você poderia ter uma biblioteca matricial fantasticamente otimizada que executasse várias operações por instrução, embora eu não não sei se, digamos, sua biblioteca FORTRAN específica o faz ou se essa biblioteca existe. Nesse caso, atualmente não há como o Java (ou pelo menos o Hotspot) competir com isso (embora você possa escrever sua própria biblioteca nativa com essas otimizações para chamar do Java).

Então, o que tudo isso significa? Bem:

• em princípio, vale a pena procurar uma biblioteca com melhor desempenho, embora, infelizmente, eu não possa recomendar uma
• se o desempenho é realmente crítico para você, eu consideraria apenas codificar suas próprias operações de matriz, porque você poderá executar certas otimizações que uma biblioteca geralmente não pode ou que uma biblioteca específica que você está usando não (se você tiver um multiprocessador, descubra se a biblioteca é realmente multithread)

Um obstáculo às operações da matriz geralmente são problemas de localização de dados que surgem quando você precisa percorrer linha por linha e coluna por coluna, por exemplo, na multiplicação de matrizes, já que é necessário armazenar os dados em uma ordem que otimize um ou outro. Mas se você escrever o código manualmente, às vezes poderá combinar operações para otimizar a localidade dos dados (por exemplo, se estiver multiplicando uma matriz por sua transformação, poderá transformar um percurso de coluna em um percurso de linha se escrever uma função dedicada em vez de combinar duas funções da biblioteca). Como de costume na vida, uma biblioteca oferece desempenho não ideal em troca de um desenvolvimento mais rápido; você precisa decidir o quão importante é o desempenho para você.

Acabei de comparar o Apache Commons Math com o jlapack.

Teste: decomposição do valor singular de uma matriz aleatória de 1024x1024.

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

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

tempo de execução dos resultados
-------------------------------------------------- -------
Oitava 36.34 seg

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 seg

Rotinas nativas
Lapack * invocado a partir de C: 37.64 seg
Intel MKL 6,89 seg (!)

Minha conclusão é que o jlapack chamado do JDK 1.7 está muito próximo do desempenho binário nativo do lapack. Eu usei a biblioteca binária de lapack que acompanha a distribuição Linux e invoquei a rotina dgesvd para obter as matrizes U, S e VT também. Todos os testes foram feitos com precisão dupla na mesma matriz a cada execução (exceto Octave).

Isenção de responsabilidade - eu não sou especialista em álgebra linear, não sou afiliado a nenhuma das bibliotecas acima e isso não é uma referência rigorosa. É um teste caseiro, pois eu estava interessado em comparar o aumento de desempenho do JDK 1.7 para 1.6, bem como do SVD matemático comum com o jlapack.

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

• envolve a biblioteca Eigen C ++ http://eigen.tuxfamily.org , que é uma das bibliotecas C ++ gratuitas mais rápidas disponíveis
• sintaxe relativamente concisa, por exemplo, 'mmul', 'sub'
• lida com matrizes densas e esparsas

Um teste rápido, multiplicando duas matrizes densas, ou seja:

importar estático 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 ao jama, tudo é mais rápido :-P
• Comparado aos jblas, o Jeigen não é tão rápido, mas lida com matrizes esparsas.
• Comparado ao ojalgo, o Jeigen leva aproximadamente a mesma quantidade de tempo decorrido, mas usando apenas um núcleo, portanto o Jeigen usa metade da CPU total. Jeigen tem uma sintaxe de terser, ou seja, 'mmul' versus 'multiplyRight'

Há uma referência de vários pacotes de matrizes disponíveis em java em http://code.google.com/p/java-matrix-benchmark/ para algumas configurações de hardware diferentes. Mas não substitui o seu próprio benchmark.

O desempenho varia de acordo com o tipo de hardware que você possui (CPU, núcleos, memória, cache L1-3, velocidade do barramento), o tamanho das matrizes e os algoritmos que você pretende usar. Bibliotecas diferentes têm opiniões diferentes sobre simultaneidade para algoritmos diferentes, portanto, não há uma resposta única. Você também pode achar que a sobrecarga de conversão para o formulário esperado por uma biblioteca nativa nega a vantagem de desempenho para seu caso de uso (algumas das bibliotecas java têm opções mais flexíveis em relação ao armazenamento de matrizes, que podem ser usadas para otimizações de desempenho adicionais).

Geralmente, porém, JAMA, Jampack e COLT estão envelhecendo e não representam o estado do desempenho atual disponível em Java para álgebra linear. Bibliotecas mais modernas fazem uso mais eficaz de vários núcleos e caches de CPU. O JAMA foi uma implementação de referência e praticamente implementa algoritmos de livros didáticos com pouca consideração ao desempenho. COLT e IBM Ninja foram as primeiras bibliotecas java a mostrar que o desempenho era possível em java, mesmo que ficasse 50% atrás das bibliotecas nativas.

Eu sou o autor da biblioteca la4j (Linear Algebra for Java) e aqui está o meu ponto. Trabalho no la4j há 3 anos (a versão mais recente é 0.4.0 [01 jun 2013]) e só agora posso começar a fazer análises e otimizações de desempenho, já que acabei de cobrir o mínimo funcional exigido. Portanto, la4j não é tão rápido quanto eu queria, mas estou gastando muito tempo para alterá-lo.

Atualmente, estou no meio de portar nova versão do la4j para a plataforma JMatBench . Espero que a nova versão mostre melhor desempenho que a anterior, pois houve várias melhorias que fiz no la4j, como formato de matriz interna muito mais rápido, acessadores inseguros e algoritmo de bloqueio rápido para multiplicações de matrizes.

O código Linalg que depende muito dos recursos de computação vetorial dos processadores Pentiums e posteriores (começando com as extensões MMX, como LAPACK e agora Atlas BLAS) não é "fantasticamente otimizado", mas simplesmente padrão do setor. Para replicar esse desempenho em Java, você precisará de bibliotecas nativas. Eu tive o mesmo problema de desempenho que você descreve (principalmente, para poder calcular decomposições de Choleski) e não encontrou nada realmente eficiente: o Jama é um Java puro, pois deveria ser apenas um modelo e um kit de referência para os implementadores seguirem. .. o que nunca aconteceu. Você sabe que o Apache math commons ... Quanto ao COLT, ainda tenho que testá-lo, mas ele parece depender muito das melhorias do Ninja, a maioria das quais foi alcançada com a criação de um compilador Java ad-hoc, por isso duvido que ajude. Nesse ponto, acho que nós "

Usamos o COLT para alguns cálculos financeiros muito sérios e ficamos muito felizes com isso. Em nosso código altamente elaborado, quase nunca tivemos que substituir uma implementação COLT por uma própria.

Em seus próprios testes (obviamente não independentes), acho que eles reivindicam dentro de um fator de 2 das rotinas de montagem otimizadas manualmente da Intel. O truque para usá-lo bem é garantir que você entenda a filosofia de design e evitar alocação de objetos estranhos.

Você já deu uma olhada na Biblioteca Intel Kernel Math ? Alega superar até o ATLAS . O MKL pode ser usado em Java através de wrappers JNI.

Com base na postagem de Varkhan, que o código nativo específico do Pentium faria melhor:

• jBLAS: Um projeto de estágio alfa com wrappers JNI para Atlas: http://www.jblas.org .

  • Postagem do blog do autor: http://mikiobraun.blogspot.com/2008/10/matrices-jni-directbuffers-and-number.html .

• MTJ: Outro projeto desse tipo: http://code.google.com/p/matrix-toolkits-java/

Você pode conferir os jblas projeto . É uma biblioteca Java relativamente nova que usa BLAS, LAPACK e ATLAS para operações de matriz de alto desempenho.

O desenvolvedor publicou alguns benchmarks nos quais o jblas se destaca favoravelmente contra o MTJ e o Colt.

Para aplicativos gráficos 3D, a implementação do vetor lwjgl.util superou os jblas mencionados acima por um fator de cerca de 3.

Eu fiz 1 milhão de multiplicações de matriz de um vec4 com uma matriz 4x4.

lwjgl terminou em cerca de 18ms, jblas exigiu cerca de 60ms.

(Suponho que a abordagem JNI não seja muito adequada para a rápida aplicação sucessiva de multiplicações relativamente pequenas. Como a tradução / mapeamento pode levar mais tempo do que a execução real da multiplicação.)

Descobri que, se você estiver criando muitas matrizes de alta dimensão, poderá tornar o Jama cerca de 20% mais rápido se o alterar para usar uma matriz unidimensional em vez de uma matriz bidimensional. Isso ocorre porque o Java não suporta matrizes multidimensionais com a mesma eficiência. ie ele cria uma matriz de matrizes.

O Colt já faz isso, mas eu achei que é mais complicado e mais poderoso que o Jama, o que pode explicar por que funções simples são mais lentas com o Colt.

A resposta realmente depende do que você está fazendo. Jama não suporta uma fração do que a Colt pode fazer, que faz mais diferença.

Há também UJMP

Existem muitas bibliotecas de álgebra linear java disponíveis gratuitamente. http://www.ujmp.org/java-matrix/benchmark/ Infelizmente, esse benchmark fornece apenas informações sobre multiplicação de matrizes (a transposição do teste não permite que as diferentes bibliotecas explorem seus respectivos recursos de design).

O que você deve observar é o desempenho dessas bibliotecas de álgebra linear quando solicitadas a calcular várias decomposições de matriz. http://ojalgo.org/matrix_compare.html

O Matrix Tookits Java (MTJ) já foi mencionado antes, mas talvez valha a pena mencionar novamente para quem mais se deparar com esse segmento. Para os interessados, parece que também há rumores de que o MTJ substitua a biblioteca linalg no apache commons math 2.0 , embora eu não tenha certeza de como isso está progredindo ultimamente.

Você deve adicionar o Apache Mahout à sua lista de compras.