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

151

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:

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.

dfrankow
fonte
Os ops matemática matriz complicado pelo menos O (n ^ 3) ... pior vem a pior, eu suponho que você poderia tempo para testes e ...
Calyth
2
Por que você precisa de inversos? Para quase todas as aplicações, você não precisa do inverso real. Computar o inverso é uma má ideia devido a problemas de estabilidade.
Ying Xiao
1
@Calyth: Sim, poderíamos cronometrar. Fiquei me perguntando se outros já tinham. @ Ying Xiao: Sim, os inversos devem ser evitados. No entanto, esse cálculo parece mais direto usando-o. Veja en.wikipedia.org/wiki/… .
9119 dfrankow
2
@Calyth Isso está errado, existem métodos mais eficientes que O (n ^ 3) usando uma abordagem de dividir e conquistar.
9119 starblue
1
O desempenho nativo mais rápido é do JCublas. Se você precisar de álgebra linear rápida, precisará de GPUs. O JOCL com clMath também pode funcionar e ser portátil para as CPUs (e até para várias plataformas sem recompilar), mas não testei.
Aleksandr Dubinsky

Respostas:

98

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.

Hamaad Shah
fonte
3
Eu acho que você estava usando uma máquina multicore, então esses resultados são fortemente afetados pelo fato de a biblioteca usar multicore ou não? Para alguns propósitos, por exemplo, quando alguém está paralelizando usando mpi ou hadoop, etc, o tempo importante é realmente o tempo de singlecore , já que a implementação do mpi / hadoop cuida de coisas paralelizadas. (Pelo menos, para mim jblas foi cerca de 2,5 mais rápido do JAMA, não 10 vezes mais rápido que jama como você tem.)
Hugh Perkins
17
Acabei de lançar a v1.0 do netlib-java ... o desempenho é equivalente (e às vezes ultrapassa) o código Fortran, e ele pode usar nativos otimizados para máquina sem nenhuma alteração no código do usuário. Considere isso ao procurar bibliotecas de álgebra linear de baixo nível. Também mantenho o MTJ , que faz uso do netlib-java. Em Scala, use Breeze (também powered by netlib-java)
fommil
4
Usando ND4j e java - meu laptop relativamente antigo completa a multiplicação sugerida dentro de 219 millis. Enquanto python + numpy o completa dentro de 349 millis
bennyl 15/12/16
2
E só para acrescentar no meu último comentário sobre o uso nd4j, eu usei-plataforma nativa como seu backend, se eu usar CUDA-plataforma leva cerca de 1 milissegundo
bennyl
Você publicou seu código para benchmarks em algum lugar?
bruziuz
108

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.

Peter Abeles
fonte
6
Só pensei em mencionar que sua referência é realmente útil! Obrigado por dedicar seu tempo a isso.
hohonuuli
1
O JBLAS parece suportar SVD a partir de setembro '13: mikiobraun.github.io/jblas/javadoc/org/jblas/…
Leopd
trabalho maravilhoso, muito obrigado.
Webpat
Existe uma lista em algum lugar das bibliotecas que você avaliou, mas não publicou resultados e os motivos de cada uma?
Kevin Krumwiede 4/16/16
1
MTJ parece abandonada: o repositório é arquivado eo último commit foi em 2016.
Danila Piatov
51

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 !

Mikio Braun
fonte
2
inspirado por seu trabalho, eu fiz uma coisa semelhante em netlib-java ;-)
fommil
2
Haha, eu também, para jeigen :-)
Hugh Perkins
O JogAmp faz o mesmo, consulte jogamp-fat.jar. Boa ideia :)
gouessej
8

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

Neil Coffey
fonte
8

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.

isti_spl
fonte
8

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'
Hugh Perkins
fonte
Jeigen parece incrível! Eu recentemente implementei o Eigen em Java usando JNI e uma DLL para resolver matrizes esparsas muito grandes. Minha versão com a DLL é 20 vezes mais rápida que o potro paralelo para meus testes (mais de 8000x8000 matrizes). Eu gostaria de saber sobre Jeigen!
Z boson
6

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.

culana
fonte
4

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.

Vladimir Kostyukov
fonte
1
Não - la4j é realmente não competitivo. Veja code.google.com/p/java-matrix-benchmark
Christopher Manning
Isso mudou muito. Lancei duas versões da biblioteca desde a sua resposta. A versão atual é 0.4.0. E apenas voa.
Vladimir Kostyukov
3

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 "

Varkhan
fonte
Bom ponto! Um projeto de estágio alfa com wrappers JNI para a Atlas: jblas.org . Postagem do blog do autor: mikiobraun.blogspot.com/2008/10/…
dfrankow
3

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.

Nick Fortescue
fonte
3

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.

Zach Scrivena
fonte
2
Nós temos isso. a) Seu licenciamento é mais restritivo que o Atlas (portanto, não podemos usar todos os nossos computadores); b) não é Java (e como eu disse, temos motivos para querer estar em Java).
Dfrankow 09/02/09
ou seja, essa não é uma resposta para minha pergunta sobre bibliotecas Java (mas não tenho reputação de rebaixá-la).
Dfrankow 09/02/09
@dfrankow: atualizei minha resposta para resolver sua preocupação em usá-lo em Java.
Zach Scrivena 9/02/09
1
+1, se é a velocidade que você procura, esse parece ser o caminho a seguir #
Gab Royer
2
O último link está quebrado.
precisa saber é o seguinte
2

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.

Mark Reid
fonte
2

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

Necrowizzard
fonte
1

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.

Peter Lawrey
fonte
1

Há também UJMP

Chad Okere
fonte
0

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

Anders Peterson
fonte
0

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.

Steve Lianoglou
fonte
0

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

bmargulies
fonte