Производительность математических библиотек Java?
Мы вычисляем что-то, чье время выполнения связано с матричными операциями. (Некоторые детали ниже, если интересно.) Этот опыт вызвал следующий вопрос:
Есть ли у людей опыт работы с библиотеками Java для матричной математики (например, умножение, обратное и т. Д.)? Например:
Я искал и ничего не нашел.
Детали нашего сравнения скорости:
Мы используем 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 работала не намного медленнее, а иногда и намного быстрее.
19 ответов
Просто чтобы добавить мои 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/!
Я только что сравнил 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"
Я не могу комментировать конкретные библиотеки, но в принципе нет особых причин замедлять такие операции в Java. Hotspot обычно выполняет те действия, которые вы ожидаете от компилятора: он компилирует основные математические операции с переменными Java в соответствующие машинные инструкции (он использует инструкции SSE, но только по одной на операцию); доступ к элементам массива компилируется для использования "сырых" инструкций MOV, как и следовало ожидать; когда это возможно, он принимает решение о том, как распределять переменные по регистрам; он переупорядочивает инструкции, чтобы использовать преимущества архитектуры процессора... Возможное исключение состоит в том, что, как я уже упоминал, Hotspot будет выполнять только одну операцию на инструкцию SSE; в принципе, вы можете иметь фантастически оптимизированную матричную библиотеку, которая выполняет несколько операций для каждой инструкции, хотя я не знаю, скажем, ваша конкретная библиотека FORTRAN делает это или же такая библиотека вообще существует. Если это произойдет, в настоящее время у Java (или, по крайней мере, у Hotspot) нет возможности конкурировать с этим (хотя вы, конечно, могли бы написать свою собственную нативную библиотеку с этими оптимизациями для вызова из Java).
Итак, что же все это значит? Что ж:
- в принципе, стоит поискать более эффективную библиотеку, хотя, к сожалению, я не могу рекомендовать одну
- если производительность действительно критична для вас, я бы подумал просто о кодировании ваших собственных матричных операций, потому что тогда вы сможете выполнять определенные оптимизации, которые библиотека обычно не может выполнять или которые не использует определенная библиотека (если у вас есть многопроцессорная машина, узнайте, действительно ли библиотека многопоточная)
Препятствием для операций с матрицами часто являются проблемы с локальностью данных, возникающие, когда вам нужно обойти как строку за строкой, так и столбец за столбцом, например, при умножении матриц, поскольку вам нужно хранить данные в порядке, который оптимизирует один или другой. Но если вы пишете код вручную, вы можете иногда комбинировать операции для оптимизации локальности данных (например, если вы умножаете матрицу на ее преобразование, вы можете превратить обход столбца в обход строки, если вы пишете выделенную функцию вместо комбинирования две библиотечные функции). Как обычно в жизни, библиотека даст вам неоптимальную производительность в обмен на более быструю разработку; вам нужно решить, насколько важна производительность для вас.
В http://code.google.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 я сделал несколько улучшений, таких как гораздо более быстрый формат внутренней матрицы, небезопасные средства доступа и алгоритм быстрой блокировки для умножения матриц.
Вы взглянули на библиотеку 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/
Мы использовали COLT для некоторых довольно серьезных финансовых расчетов и были очень довольны. В нашем сильно профилированном коде нам почти никогда не приходилось заменять реализацию COLT на нашу собственную.
В своем собственном тестировании (очевидно, не независимом) я думаю, что они утверждают в 2 раза больше, чем оптимизированные вручную процедуры ассемблера Intel. Хитрость в том, чтобы правильно его использовать, заключается в том, чтобы вы понимали их философию дизайна и избегали постороннего выделения объектов.
Код Linalg, который в значительной степени опирается на возможности векторных вычислений Pentiums и более поздних процессоров (начиная с расширений MMX, таких как LAPACK и теперь Atlas BLAS), не "фантастически оптимизирован", а просто является отраслевым стандартом. Чтобы воспроизвести это исполнение в Java, вам понадобятся нативные библиотеки. У меня была та же проблема с производительностью, которую вы описали (в основном, чтобы иметь возможность вычислять разложения Холецки), и я не нашел ничего действительно эффективного: Jama - это чистая Java, так как предполагается, что это просто шаблон и справочный набор для разработчиков, которым нужно следовать... чего никогда не было Вы знаете, Apache математическое достояние... Что касается COLT, мне еще предстоит его протестировать, но, похоже, он сильно зависит от улучшений Ninja, большинство из которых были достигнуты при создании специального компилятора Java, поэтому я сомневаюсь, что это поможет. На данный момент, я думаю, что нам "просто" нужны коллективные усилия для создания нативной реализации Jama...
Я обнаружил, что если вы создаете много многомерных матриц, вы можете сделать Jama примерно на 20% быстрее, если измените его на использование одномерного массива вместо двумерного массива. Это потому, что Java не поддерживает многомерные массивы так эффективно. то есть. он создает массив массивов.
Colt уже делает это, но я обнаружил, что это сложнее и мощнее, чем Jama, что может объяснить, почему простые функции медленнее с Colt.
Ответ действительно зависит от того, что вы делаете. Джама не поддерживает часть вещей, которые может сделать Кольт, которые делают большую разницу.
Для приложений с трехмерной графикой реализация вектора lwjgl.util превзошла вышеупомянутую jblas примерно в 3 раза.
Я сделал 1 миллион матричных умножений vec4 с матрицей 4x4.
lwjgl финишировал примерно за 18мс, jblas потребовалось около 60мс.
(Я предполагаю, что подход JNI не очень подходит для быстрого последовательного применения сравнительно небольших умножений. Поскольку преобразование / отображение может занять больше времени, чем фактическое выполнение умножения.)
Существует много различных свободно доступных библиотек линейной алгебры 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, хотя я не уверен, как это продвигается в последнее время.