Wydajność bibliotek matematycznych Java Matrix? [Zamknięte]

Obliczamy coś, czego czas wykonania jest ograniczony operacjami macierzowymi. (Niektóre szczegóły poniżej, jeśli są zainteresowane). To doświadczenie wywołało następujące pytanie:

Czy ludzie mają doświadczenie w wykonywaniu bibliotek Java dla matematyki macierzowej (np. Mnożenie, odwrotność itp.)? Na przykład:

• JAMA
• ŹREBIĘ
• Matematyka Apache commons

Szukałem i nic nie znalazłem.

Szczegóły naszego porównania prędkości:

Używamy Intel FORTRAN (ifort (IFORT) 10.1 20070913). Ponownie zaimplementowaliśmy go w Javie (1.6) przy użyciu operacji macierzowych Apache commons math 1.2 i zgadza się na wszystkie cyfry dokładności. (Mamy powody, by chcieć tego w Javie.) (Java podwaja się, Fortran real * 8). Fortran: 6 minut, Java 33 minuty, ta sama maszyna. Profilowanie jvisualm pokazuje dużo czasu spędzonego w RealMatrixImpl. {getEntry, isValidCoordinate} (które wydają się znikać w niewydanej Apache commons Math 2.0, ale 2.0 nie jest szybsze). Fortran używa procedur Atlas BLAS (dpotrf itp.).

Oczywiście może to zależeć od naszego kodu w każdym języku, ale uważamy, że przez większość czasu wykonywane są równoważne operacje macierzowe.

W kilku innych obliczeniach, które nie obejmują bibliotek, Java nie była dużo wolniejsza, a czasami znacznie szybsza.

Dodam tylko moje 2 centy. Porównałem niektóre z tych bibliotek. Podjęłam próbę pomnożenia macierzy przez 3000 razy 3000 macierzy podwójnych. Wyniki są następujące.

Używając wielowątkowego ATLAS z C / C ++, Octave, Python i R, zajęło to około 4 sekund.

W przypadku korzystania z Jamy z Javą zajęło to 50 sekund.

Używając Colta i Parallel Colta z Javą, zajęło to 150 sekund!

Używając JBLAS z Javą, zajęło to ponownie około 4 sekund, ponieważ JBLAS używa wielowątkowego ATLAS.

Więc dla mnie było jasne, że biblioteki Java nie działają zbyt dobrze. Jeśli jednak ktoś musi kodować w Javie, to najlepszą opcją jest JBLAS. Jama, Colt i Parallel Colt nie są szybkie.

Jestem autorem Java Matrix Benchmark ( JMatBench ) i podzielę się swoimi przemyśleniami na temat tej dyskusji.

Istnieją znaczące różnice między bibliotekami Java i chociaż nie ma wyraźnego zwycięzcy w całym zakresie operacji, jest kilku wyraźnych liderów, co widać w najnowszych wynikach wydajności (październik 2013).

Jeśli pracujesz z "dużymi" macierzami i możesz korzystać z natywnych bibliotek, to wyraźnym zwycięzcą (około 3,5x szybciej) jest MTJ ze zoptymalizowanym systemem netlib . Jeśli potrzebujesz czystego rozwiązania w języku Java , dobrym wyborem są MTJ , OjAlgo , EJML i Parallel Colt . W przypadku małych matryc EJML jest wyraźnym zwycięzcą.

Biblioteki, o których nie wspomniałem, wykazywały poważne problemy z wydajnością lub brakowało im kluczowych funkcji.

Jestem głównym autorem jblas i chciałem zwrócić uwagę, że wypuściłem wersję 1.0 pod koniec grudnia 2009. Dużo pracowałem nad opakowaniem, co oznacza, że ​​teraz możesz po prostu pobrać "fat jar" z bibliotekami ATLAS i JNI dla Windows, Linux, Mac OS X, 32 i 64 bit (z wyjątkiem Windows). W ten sposób uzyskasz natywną wydajność, po prostu dodając plik jar do ścieżki klas. Sprawdź to na http://jblas.org !

Naprawdę nie mogę komentować konkretnych bibliotek, ale w zasadzie nie ma powodu, aby takie operacje były wolniejsze w Javie. Hotspot generalnie wykonuje takie rzeczy, jakich oczekuje się od kompilatora: kompiluje podstawowe operacje matematyczne na zmiennych Java do odpowiednich instrukcji maszynowych (używa instrukcji SSE, ale tylko po jednej na operację); dostęp do elementów tablicy są kompilowane z użyciem „surowych” instrukcji MOV, tak jak można się tego spodziewać; podejmuje decyzje o przydzielaniu zmiennych do rejestrów, kiedy tylko jest to możliwe; zmienia kolejność instrukcji, aby wykorzystać architekturę procesora ... Możliwym wyjątkiem jest to, że jak wspomniałem, Hotspot wykona tylko jedną operację na instrukcję SSE; w zasadzie możesz mieć fantastycznie zoptymalizowaną bibliotekę macierzy, która wykonywałaby wiele operacji na instrukcję, chociaż ja tego nie robię wiem, czy, powiedzmy, twoja konkretna biblioteka FORTRAN tak robi, czy też taka biblioteka w ogóle istnieje. Jeśli tak, nie ma obecnie możliwości, aby Java (a przynajmniej Hotspot) mogła z tym konkurować (chociaż możesz oczywiście napisać własną bibliotekę natywną z optymalizacjami do wywoływania z Javy).

Więc co to wszystko oznacza? Dobrze:

• w zasadzie warto poszukać lepiej działającej biblioteki, choć niestety nie mogę jej polecić
• jeśli wydajność jest dla Ciebie naprawdę krytyczna, rozważyłbym po prostu zakodowanie własnych operacji macierzowych, ponieważ możesz wtedy być w stanie przeprowadzić pewne optymalizacje, których biblioteka na ogół nie może, lub że konkretna biblioteka, której używasz, nie (jeśli masz maszyna wieloprocesorowa, sprawdź, czy biblioteka jest rzeczywiście wielowątkowa)

Przeszkodą w operacjach na macierzach są często problemy z lokalizacją danych, które pojawiają się, gdy trzeba przechodzić zarówno wiersz po wierszu, jak i kolumna po kolumnie, np. Przy mnożeniu macierzy, ponieważ dane muszą być przechowywane w kolejności optymalizującej jedno lub drugie. Ale jeśli ręcznie piszesz kod, możesz czasami łączyć operacje w celu optymalizacji lokalizacji danych (np. Jeśli mnożysz macierz przez jej transformację, możesz zmienić przechodzenie kolumny na przechodzenie przez wiersz, jeśli napiszesz dedykowaną funkcję zamiast łączenia dwie funkcje biblioteczne). Jak zwykle w życiu, biblioteka zapewni nieoptymalną wydajność w zamian za szybszy rozwój; musisz zdecydować, jak ważna jest dla Ciebie wydajność.

Właśnie porównałem Apache Commons Math z jlapackiem.

Test: rozkład wartości osobliwych losowej macierzy 1024x1024.

Maszyna: procesor Intel (R) Core (TM) 2 Duo E6750 @ 2,66 GHz, linux x64

Kod oktawy: A = rand (1024); tic; [U, S, V] = svd (A); toc

czas wykonania wyników
-------------------------------------------------- -------
Oktawa 36,34 sek

JDK 1.7u2 64-bitowy
    jlapack dgesvd 37,78 sek
    apache commons matematyka SVD 42,24 sek


JDK 1.6u30 64-bitowy
    jlapack dgesvd 48,68 sek
    apache commons matematyka SVD 50,59 sek

Rodzime procedury
Lapack * wywołany z C: 37,64 sek
Intel MKL 6,89 s (!)

Mój wniosek jest taki, że jlapack wywołany z JDK 1.7 jest bardzo zbliżony do natywnej wydajności binarnej lapacka. Użyłem binarnej biblioteki lapack dostarczanej z dystrybucją Linuksa i wywołałem procedurę dgesvd, aby uzyskać również macierze U, S i VT. Wszystkie testy wykonano z podwójną precyzją na dokładnie tej samej matrycy w każdym przebiegu (z wyjątkiem Octave).

Zastrzeżenie - nie jestem ekspertem w algebrze liniowej, nie jestem związany z żadną z powyższych bibliotek i nie jest to rygorystyczny punkt odniesienia. To test „domowej roboty”, ponieważ byłem zainteresowany porównaniem wzrostu wydajności JDK 1.7 do 1.6, a także zwykłej matematyki SVD do jlapacka.

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

• otacza bibliotekę Eigen C ++ http://eigen.tuxfamily.org , która jest jedną z najszybszych dostępnych darmowych bibliotek C ++
• stosunkowo zwięzła składnia, np. „mmul”, „sub”
• obsługuje zarówno gęste, jak i rzadkie matryce

Szybki test polegający na pomnożeniu dwóch gęstych macierzy, czyli:

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

Wyniki:

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

• W porównaniu do jamy wszystko jest szybsze :-P
• W porównaniu do jblas, Jeigen nie jest tak szybki, ale obsługuje rzadkie macierze.
• W porównaniu z ojalgo, Jeigen zajmuje mniej więcej tyle samo czasu, który upłynął, ale używa tylko jednego rdzenia, więc Jeigen zużywa połowę całkowitego procesora. Jeigen ma terser składnię, tj. „Mmul” kontra „multiplyRight”

Na http://code.google.com/p/java-matrix-benchmark/ dostępny jest test porównawczy różnych pakietów macierzy dostępnych w java dla kilku różnych konfiguracji sprzętowych. Ale to nie zastąpi zrobienia własnego testu porównawczego.

Wydajność będzie się różnić w zależności od typu posiadanego sprzętu (procesor, rdzenie, pamięć, pamięć podręczna L1-3, szybkość magistrali), rozmiaru macierzy i algorytmów, których zamierzasz używać. Różne biblioteki mają różne podejście do współbieżności dla różnych algorytmów, więc nie ma jednej odpowiedzi. Może się również okazać, że narzut związany z tłumaczeniem do postaci oczekiwanej przez bibliotekę natywną neguje przewagę wydajnościową w przypadku użycia (niektóre biblioteki java mają bardziej elastyczne opcje dotyczące pamięci macierzowej, które można wykorzystać do dalszej optymalizacji wydajności).

Jednak generalnie JAMA, Jampack i COLT starzeją się i nie reprezentują aktualnego stanu dostępnego w Javie dla algebry liniowej. Bardziej nowoczesne biblioteki efektywniej wykorzystują wiele rdzeni i pamięci podręcznych procesora. JAMA była implementacją wzorcową i prawie implementuje podręczne algorytmy bez większego znaczenia dla wydajności. COLT i IBM Ninja były pierwszymi bibliotekami java, które pokazały, że wydajność w java była możliwa, nawet jeśli pozostawały one 50% w tyle za bibliotekami natywnymi.

Jestem autorem biblioteki la4j (Linear Algebra for Java) i o to mi chodzi. Pracuję nad la4j od 3 lat (najnowsza wersja to 0.4.0 [01 czerwca 2013]) i dopiero teraz mogę rozpocząć analizę wydajności i optymalizacje, ponieważ właśnie omówiłem minimalną wymaganą funkcjonalność. Więc la4j nie jest tak szybki, jak chciałem, ale poświęcam mnóstwo czasu, aby to zmienić.

Obecnie jestem w trakcie przenoszenia nowej wersji la4j na platformę JMatBench . Mam nadzieję, że nowa wersja pokaże lepszą wydajność niż poprzednia, ponieważ wprowadziłem kilka ulepszeń w la4j, takich jak znacznie szybszy format matrycy wewnętrznej, niebezpieczne akcesoria i szybki algorytm blokowania mnożenia macierzy.

Kod Linalg, który w dużym stopniu opiera się na procesorach Pentium i późniejszych możliwościach obliczania wektorowego (począwszy od rozszerzeń MMX, takich jak LAPACK, a teraz Atlas BLAS), nie jest „fantastycznie zoptymalizowany”, ale jest po prostu standardem branżowym. Aby odtworzyć tę wydajność w Javie, będziesz potrzebować natywnych bibliotek. Miałem ten sam problem z wydajnością, jaki opisałeś (głównie, aby móc obliczyć rozkład Choleskiego) i nie znalazłem nic naprawdę wydajnego: Jama to czysta Java, ponieważ ma być tylko szablonem i zestawem referencyjnym dla implementatorów. .. co nigdy się nie wydarzyło. Znasz matematykę Apache commons ... Jeśli chodzi o COLT, muszę go jeszcze przetestować, ale wydaje się, że w dużej mierze opiera się on na ulepszeniach Ninja, z których większość osiągnięto poprzez zbudowanie kompilatora Java ad-hoc, więc wątpię, czy to pomoże. W tym momencie myślę, że „

Użyliśmy COLT do całkiem poważnych obliczeń finansowych i jesteśmy z tego bardzo zadowoleni. W naszym mocno sprofilowanym kodzie prawie nigdy nie musieliśmy zastępować implementacji COLT naszą własną.

W swoich własnych testach (oczywiście nie niezależnych) myślę, że twierdzą, że mieszczą się w 2-krotnym stopniu zoptymalizowanej ręcznie procedury asemblera Intela. Sztuczka, aby dobrze go używać, polega na upewnieniu się, że rozumiesz filozofię projektowania i unikasz niepotrzebnego przydzielania obiektów.

Czy przyjrzałeś się bibliotece jądra Intel Math Kernel ? Twierdzi, że przewyższa nawet ATLAS . MKL może być używany w Javie za pośrednictwem opakowań JNI.

Opierając się na poście Varkhana, że ​​natywny kod dla Pentium byłby lepszy:

• jBLAS: Projekt w fazie alfa z opakowaniami JNI dla Atlas: http://www.jblas.org .

  • Post na blogu autora: http://mikiobraun.blogspot.com/2008/10/matrices-jni-directbuffers-and-number.html .

• MTJ: Kolejny taki projekt: http://code.google.com/p/matrix-toolkits-java/

Możesz sprawdzić projekt jblas . Jest to stosunkowo nowa biblioteka Java, która używa BLAS, LAPACK i ATLAS do wysokowydajnych operacji na macierzach.

Deweloper opublikował kilka testów porównawczych, w których jblas wypada korzystnie przeciwko MTJ i Coltowi.

W przypadku aplikacji graficznych 3D implementacja wektora lwjgl.util przewyższyła wyżej wymienione jblas o współczynnik około 3.

Zrobiłem 1 milion mnożenia macierzy vec4 z macierzą 4x4.

lwjgl zakończyło się w około 18 ms, jblas wymagało około 60 ms.

(Zakładam, że podejście JNI nie jest zbyt odpowiednie do szybkiego, sukcesywnego stosowania stosunkowo małych mnożeń. Ponieważ tłumaczenie / mapowanie może zająć więcej czasu niż faktyczne wykonanie mnożenia.)

Odkryłem, że jeśli tworzysz wiele wysokowymiarowych Matryc, możesz uczynić Jamę około 20% szybciej, jeśli zmienisz ją tak, aby używała jednowymiarowej tablicy zamiast dwuwymiarowej. Dzieje się tak, ponieważ Java nie obsługuje tak wydajnych tablic wielowymiarowych. to znaczy. tworzy tablicę tablic.

Colt już to robi, ale odkryłem, że jest to bardziej skomplikowane i potężniejsze niż Jama, co może wyjaśniać, dlaczego proste funkcje działają wolniej w Colcie.

Odpowiedź naprawdę zależy od tego, co robisz. Jama nie wspiera ułamka tego, co może robić Colt, a które robią większą różnicę.

Jest też UJMP

Istnieje wiele różnych, dostępnych bezpłatnie bibliotek algebry liniowej Java. http://www.ujmp.org/java-matrix/benchmark/ Niestety ten test porównawczy podaje tylko informacje o mnożeniu macierzy (transpozycja testu nie pozwala różnym bibliotekom na wykorzystanie ich odpowiednich cech konstrukcyjnych).

Powinieneś przyjrzeć się temu, jak te biblioteki algebry liniowej działają, gdy zostaną poproszone o obliczenie różnych dekompozycji macierzy. http://ojalgo.org/matrix_compare.html

Matrix Tookits Java (MTJ) była już wspomniana, ale być może warto o tym wspomnieć jeszcze raz dla każdego, kto natknie się na ten wątek. Dla zainteresowanych wydaje się, że mówi się również o tym, że MTJ zastąpi bibliotekę linalg w apache commons math 2.0 , chociaż nie jestem pewien, jak to się ostatnio rozwija.

Powinieneś dodać Apache Mahout do swojej listy zakupów.