Производительность математических библиотек Java матрицы? [закрыто]

Мы вычисляем что-то, чье время выполнения связано с матричными операциями. (Некоторые детали ниже, если интересно.) Этот опыт вызвал следующий вопрос:

Есть ли у людей опыт работы с библиотеками Java для матричной математики (например, умножение, обратное и т. Д.)? Например:

• JAMA
• COLT
• Apache Commons Math

Я искал и ничего не нашел.

Детали нашего сравнения скорости:

Мы используем Intel FORTRAN (ifort (IFORT) 10.1 20070913). Мы переопределили его в Java (1.6), используя Apache Commons Math 1.2 OPS, и он согласен со всеми цифрами точности. (У нас есть причины желать этого в Java.) (Java удваивается, Fortran real * 8). Фортран: 6 минут, Java 33 минуты, та же машина. Профилирование jvisualm показывает много времени, проведенного в RealMatrixImpl. {getEntry, isValidCoordinate} (который, похоже, отсутствует в невыпущенных Apache commons math 2.0, но 2.0 не быстрее). Fortran использует процедуры Atlas BLAS (dpotrf и т. Д.).

Очевидно, что это может зависеть от нашего кода на каждом языке, но мы считаем, что большую часть времени находятся в эквивалентных матричных операциях.

В некоторых других вычислениях, в которых не используются библиотеки, Java работала не намного медленнее, а иногда и намного быстрее.

Просто чтобы добавить мои 2 цента. Я сравнил некоторые из этих библиотек. Я попытался умножить матрицу парных чисел 3000 на 3000 с собой. Результаты приведены ниже.

При использовании многопоточного ATLAS с C / C ++, Octave, Python и R время работы составило около 4 секунд.

Используя Jama с Java, время заняло 50 секунд.

Используя Colt и Parallel Colt с Java, время заняло 150 секунд!

При использовании JBLAS с Java время снова составило около 4 секунд, поскольку JBLAS использует многопоточный ATLAS.

Поэтому для меня было ясно, что библиотеки Java работают не слишком хорошо. Однако если кто-то должен кодировать на Java, то лучшим вариантом является JBLAS. Джама, Кольт и Параллельный Кольт не быстрые.

Я являюсь автором Java Matrix Benchmark ( JMatBench ), и я поделюсь своими мыслями об этом обсуждении.

Между библиотеками Java есть существенная разница, и хотя во всем диапазоне операций нет явного победителя, есть несколько явных лидеров, которые можно увидеть в последних результатах производительности (октябрь 2013 г.).

Если вы работаете с «большими» матрицами и можете использовать нативные библиотеки, то абсолютный победитель (примерно в 3,5 раза быстрее) - MTJ с netlib, оптимизированным системой . Если вам нужно чисто Java-решение, тогда MTJ , OjAlgo , EJML и Parallel Colt - хороший выбор. Для маленьких матриц EJML - явный победитель.

Библиотеки, о которых я не упомянул, показывали значительные проблемы с производительностью или отсутствовали ключевые функции.

Я являюсь основным автором jblas и хотел бы отметить, что я выпустил версию 1.0 в конце декабря 2009 года. Я много работал над упаковкой, а это означает, что теперь вы можете просто скачать «толстую банку» с библиотеками ATLAS и JNI для Windows, Linux, Mac OS X, 32 и 64 бит (кроме Windows). Таким образом, вы получите собственную производительность, просто добавив файл jar в путь к классам. Проверьте это на http://jblas.org !

Я не могу комментировать конкретные библиотеки, но в принципе нет особых причин замедлять такие операции в Java. Hotspot обычно выполняет те действия, которые вы ожидаете от компилятора: он компилирует базовые математические операции с переменными Java в соответствующие машинные инструкции (он использует инструкции SSE, но только по одной на операцию); доступ к элементам массива компилируется для использования «сырых» инструкций MOV, как и следовало ожидать; когда это возможно, он принимает решение о том, как распределять переменные по регистрам; он переупорядочивает инструкции, чтобы воспользоваться преимуществами архитектуры процессора ... Возможное исключение состоит в том, что, как я уже говорил, Hotspot будет выполнять только одну операцию на инструкцию SSE; в принципе, вы могли бы иметь фантастически оптимизированную матричную библиотеку, которая выполняла несколько операций для каждой инструкции, хотя я не Не знаю, скажем, ваша конкретная библиотека FORTRAN делает это или же такая библиотека существует. Если это произойдет, в настоящее время у Java (или, по крайней мере, у Hotspot) нет возможности конкурировать с этим (хотя вы, конечно, можете написать свою собственную нативную библиотеку с этими оптимизациями для вызова из Java).

Так что же все это значит? Хорошо:

• в принципе, стоит поискать более эффективную библиотеку, хотя, к сожалению, я не могу рекомендовать одну
• если производительность действительно критична для вас, я бы рассмотрел просто кодирование ваших собственных матричных операций, потому что тогда вы сможете выполнять определенные оптимизации, которые библиотека обычно не может выполнять или которые не использует конкретная библиотека (если у вас есть многопроцессорная машина, узнайте, действительно ли библиотека многопоточная)

Препятствием для операций с матрицами часто являются проблемы с локальностью данных, возникающие, когда вам нужно пройти как по строкам, так и по столбцам, например, при умножении матриц, поскольку вам нужно хранить данные в порядке, который оптимизирует один или другой. Но если вы пишете код вручную, вы можете иногда комбинировать операции для оптимизации локальности данных (например, если вы умножаете матрицу на ее преобразование, вы можете превратить обход столбца в обход строки, если вы пишете выделенную функцию вместо комбинирования две библиотечные функции). Как обычно в жизни, библиотека даст вам неоптимальную производительность в обмен на более быструю разработку; вам нужно решить, насколько важна производительность для вас.

Я только что сравнил Apache Commons Math с jlapack.

Тест: разложение по сингулярности случайной матрицы 1024x1024.

Машина: процессор Intel® Core ™ 2 Duo E6750 с частотой 2,66 ГГц, Linux x64

Октавный код: A = rand (1024); крестики; [U, S, V] = SVD (А); TOC

время выполнения результатов
-------------------------------------------------- -------
Октава 36,34 сек

JDK 1.7u2 64bit
    jlapack dgesvd 37,78 сек
    apache commons математика SVD 42,24 сек


JDK 1.6u30 64bit
    jlapack dgesvd 48,68 сек
    apache commons математика SVD 50,59 сек

Родные процедуры
Lapack * вызывается из C: 37,64 сек
Intel MKL 6,89 сек (!)

Мой вывод заключается в том, что jlapack, вызываемый из JDK 1.7, очень близок к производительности двоичного пакета lapack. Я использовал двоичную библиотеку lapack, поставляемую с дистрибутивом Linux, и вызвал подпрограмму dgesvd, чтобы также получить матрицы U, S и VT. Все тесты проводились с использованием двойной точности на одной и той же матрице каждый прогон (кроме Octave).

Отказ от ответственности - я не специалист по линейной алгебре, не связан ни с одной из вышеперечисленных библиотек, и это не является строгим эталоном. Это «домашний» тест, так как мне было интересно сравнить повышение производительности JDK с 1,7 до 1,6, а также общее вычисление SVD с jlapack.

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

• включает в себя библиотеку Eigen C ++ http://eigen.tuxfamily.org , которая является одной из самых быстрых доступных доступных библиотек C ++
• относительно краткий синтаксис, например, 'mmul', 'sub'
• обрабатывает как плотные, так и разреженные матрицы

Быстрый тест, умножая две плотные матрицы, то есть:

импорт статического 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();

Полученные результаты:

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

• По сравнению с джамой все быстрее :-P
• По сравнению с jblas, Jeigen не так быстр, но он обрабатывает разреженные матрицы.
• По сравнению с ojalgo, Jeigen тратит примерно столько же времени, но только на одно ядро, поэтому Jeigen использует половину всего процессора. Jeigen имеет более короткий синтаксис, то есть «mmul» против «multiplyRight»

В http://www.gcode.com/p/java-matrix-benchmark/ есть несколько различных пакетов матриц, доступных для нескольких различных конфигураций оборудования. Но это не заменит ваш собственный тест.

Производительность будет зависеть от типа используемого вами оборудования (процессор, ядра, память, кэш L1-3, скорость шины), размера матриц и алгоритмов, которые вы собираетесь использовать. Разные библиотеки по-разному воспринимают параллелизм для разных алгоритмов, поэтому однозначного ответа нет. Вы также можете обнаружить, что накладные расходы на перевод в форму, ожидаемую собственной библиотекой, сводят на нет преимущество в производительности для вашего варианта использования (некоторые из библиотек Java имеют более гибкие параметры в отношении хранения в матрице, которые можно использовать для дальнейшей оптимизации производительности).

Однако в целом JAMA, Jampack и COLT стареют и не представляют состояние текущей производительности, доступной в Java для линейной алгебры. Более современные библиотеки более эффективно используют многоядерные и процессорные кэши. JAMA была эталонной реализацией и в значительной степени реализует алгоритмы из учебников, мало заботясь о производительности. COLT и IBM Ninja были первыми библиотеками Java, которые показали, что производительность в Java возможна, даже если они отстают на 50% от собственных библиотек.

Я являюсь автором библиотеки la4j (Linear Algebra for Java), и вот моя точка зрения. Я работаю над la4j в течение 3 лет (последний выпуск - 0.4.0 [01 июня 2013]), и только сейчас я могу начать выполнять анализ и оптимизацию производительности, поскольку я только что рассмотрел минимально необходимый функционал. Итак, la4j не так быстр, как я хотел, но я трачу много времени, чтобы изменить его.

В настоящее время я занимаюсь портированием новой версии la4j на платформу JMatBench . Я надеюсь, что новая версия покажет лучшую производительность, чем предыдущая, поскольку в la4j я сделал несколько улучшений, таких как гораздо более быстрый формат внутренней матрицы, небезопасные средства доступа и алгоритм быстрой блокировки для умножения матриц.

Код Linalg, который в значительной степени опирается на возможности векторных вычислений Pentiums и более поздних процессоров (начиная с расширений MMX, таких как LAPACK и теперь Atlas BLAS), не «фантастически оптимизирован», а просто является отраслевым стандартом. Чтобы воспроизвести это исполнение в Java, вам понадобятся нативные библиотеки. У меня была та же проблема с производительностью, которую вы описали (в основном, чтобы иметь возможность вычислять разложения Холецки), и я не нашел ничего по-настоящему эффективного: Jama - это чистая Java, поскольку предполагается, что это просто шаблон и справочный набор для разработчиков. .. чего никогда не было Вы знаете, математическое достояние Apache ... Что касается COLT, мне еще предстоит его протестировать, но, похоже, он сильно зависит от улучшений Ninja, большинство из которых были достигнуты путем создания специального компилятора Java, поэтому я сомневаюсь, что это поможет. На данный момент, я думаю, что мы "

Мы использовали COLT для довольно серьезных финансовых расчетов и были очень довольны. В нашем сильно профилированном коде нам почти никогда не приходилось заменять реализацию COLT на нашу собственную.

В своем собственном тестировании (очевидно, не независимом) я думаю, что они утверждают в 2 раза больше, чем оптимизированные вручную процедуры ассемблера Intel. Хитрость его правильного использования заключается в том, чтобы вы понимали их философию дизайна и избегали постороннего выделения объектов.

Вы взглянули на библиотеку Intel Math Kernel ? Он утверждает, что превосходит даже ATLAS . MKL можно использовать в Java через оболочки JNI.

Основываясь на сообщении Вархана, что родной код для Pentium будет лучше:

• jBLAS: проект альфа-стадии с упаковщиками JNI для Atlas: http://www.jblas.org .

  • Сообщение в блоге автора: http://mikiobraun.blogspot.com/2008/10/matrices-jni-directbuffers-and-number.html .

• MTJ: еще один такой проект: http://code.google.com/p/matrix-toolkits-java/

Вы можете проверить проект jblas . Это относительно новая библиотека Java, которая использует BLAS, LAPACK и ATLAS для высокопроизводительных матричных операций.

Разработчик опубликовал несколько тестов, в которых jblas выгодно отличается от MTJ и Colt.

Для приложений с трехмерной графикой реализация вектора lwjgl.util превзошла вышеупомянутую jblas примерно в 3 раза.

Я сделал 1 миллион матричных умножений vec4 с матрицей 4x4.

lwjgl финишировал примерно за 18мс, jblas потребовалось около 60мс

(Я предполагаю, что подход JNI не очень подходит для быстрого последовательного применения сравнительно небольших умножений. Поскольку преобразование / отображение может занять больше времени, чем фактическое выполнение умножения.)

Я обнаружил, что если вы создаете много многомерных матриц, вы можете сделать Jama примерно на 20% быстрее, если измените его на использование одномерного массива вместо двухмерного массива. Это потому, что Java не поддерживает многомерные массивы так эффективно. то есть. он создает массив массивов.

Colt уже делает это, но я обнаружил, что это сложнее и мощнее, чем Jama, что может объяснить, почему простые функции медленнее с Colt.

Ответ действительно зависит от того, что вы делаете. Джама не поддерживает часть вещей, которые может сделать Кольт, которые делают большую разницу.

Там также UJMP

Существует много различных свободно доступных библиотек линейной алгебры Java. http://www.ujmp.org/java-matrix/benchmark/ К сожалению, этот тест дает только информацию о умножении матриц (транспонирование теста не позволяет различным библиотекам использовать свои соответствующие конструктивные особенности).

Вы должны посмотреть, как эти библиотеки линейной алгебры работают, когда их просят вычислить различные матричные разложения. http://ojalgo.org/matrix_compare.html

Matrix Tookits Java (MTJ) уже упоминался ранее, но, возможно, стоит упомянуть еще раз для всех, кто наткнулся на эту тему. Для тех, кто интересуется, кажется, что есть также разговор о том, чтобы MTJ заменил библиотеку linalg в apache commons math 2.0 , хотя я не уверен, как это продвигается в последнее время.

Вы должны добавить Apache Mahout в свой список покупок.