Comments 84
UFO just landed and posted this here
Эм. Что вас тут смутило?
меня смутило слово «непосредственно», и чем отличаются локальные переменные с final и без final.
Все просто. Если участок байт кода компилируется в нативный то c final перменными будет примерно следующие:
Для простой перменной:
Для final:
Т.е. на машинных инструкциях x86 команды сравнения/переходов будут применены не к переменной а к значению.
Для простой перменной:
int a;
for (int i=0; i<a; i++) { }
Для final:
final int a = 10;
for (int i=0; i<10; i++) { }
Т.е. на машинных инструкциях x86 команды сравнения/переходов будут применены не к переменной а к значению.
Я не эксперт, но по-моему на машинных инструкциях x86 команды сравнения применяются к регистрам процессора в любом случае.
К тому же у вас в статье сравниваются в первом случае — вызов метода объекта, куда может включаются кучка дополнительных проверок, во втором — фиксация значений в локальных переменных. Мне кажется, final тут не при чем. Попробуйте сравнить тоже самое, только без слова final, должно получиться тоже время.
К тому же у вас в статье сравниваются в первом случае — вызов метода объекта, куда может включаются кучка дополнительных проверок, во втором — фиксация значений в локальных переменных. Мне кажется, final тут не при чем. Попробуйте сравнить тоже самое, только без слова final, должно получиться тоже время.
Команда сравнения CMP может применяться и для пары регистр/значение — не только для памяти. (http://siyobik.info/index.php?module=x86&id=35)
Вызов метода влюбом случае заинлайнится, т.к. методы columns() и rows() очеь короткие. Если мне не изменяет склероз инлайнтится все что меньшее 35 байткодов (это настраивается).
Простые переменные я пробовал. Прирост дают именно final.
Вызов метода влюбом случае заинлайнится, т.к. методы columns() и rows() очеь короткие. Если мне не изменяет склероз инлайнтится все что меньшее 35 байткодов (это настраивается).
Простые переменные я пробовал. Прирост дают именно final.
А теперь скомпилируйте .java исходник, в одном случае с final перед локальной переменной, в другом случае без final, и сравните побайтно получившиеся .class файлы.
Мне удалось убедиться, что с final значения инлайнятся уже в байткоде. в то время как без final явная переменная «int a» тоже исчезла, и вместо неё появилось
byte byte0 = 10;
for(int i = 0; i < byte0; i++);
смотрел jad'ом
Однако, это само по себе ничего не доказывает. Надо смотреть что именно производит jit.
byte byte0 = 10;
for(int i = 0; i < byte0; i++);
смотрел jad'ом
Однако, это само по себе ничего не доказывает. Надо смотреть что именно производит jit.
С числовыми константами все понятно. Не о них речь. Вы сравните
final int aColumns = A.columns(); и
int aColumns = A.columns();
Автор утверждал, что с final будет быстрее. Я же говорю, что такого быть не может, поскольку байткод получается абсолютно одинаковым!
final int aColumns = A.columns(); и
int aColumns = A.columns();
Автор утверждал, что с final будет быстрее. Я же говорю, что такого быть не может, поскольку байткод получается абсолютно одинаковым!
Вопрос такой. Тогда в чем по-вашему разница между final и не-final c точки зрения генеринруемого кода?
С точки зреня этапа компиляции понятно. final перменные неизменяемые. Их модификация приводит в ошибки компиляции.
С точки зреня этапа компиляции понятно. final перменные неизменяемые. Их модификация приводит в ошибки компиляции.
В байткоде нигде не остается информации о том, была ли локальная переменная final или не final, поэтому JIT о final ничего не знает, и генерируемый код ничем не отличается. Тем не менее, JIT и сам умеет определять, что значение переменной не меняется, и применять соответствующие оптимизации (common subexpression elimination, loop invariant hoisting...)
Следует отличать эту ситуацию от двух других:
— когда final приписывается к полям класса, в этом случае в байткоде имеется информация об атрибуте final поля;
— когда final локальные переменные используются в замыканиях (анонимных классах внутри метода) — в этом случае значения этих переменных передаются в конструктор анонимного класса. Впрочем, на производительность это также не влияет.
Следует отличать эту ситуацию от двух других:
— когда final приписывается к полям класса, в этом случае в байткоде имеется информация об атрибуте final поля;
— когда final локальные переменные используются в замыканиях (анонимных классах внутри метода) — в этом случае значения этих переменных передаются в конструктор анонимного класса. Впрочем, на производительность это также не влияет.
Я бы до 2 пункта не догадался наверное… Полезные советы, спасибо!
См. тж. пункт 2.6.2 «Как оптимизировать матричное умножение» книги Дж. Деммеля «Вычислительная линейная алгебра». В нем обсуждается блочная версия матричного умножения.
И не совсем корректно говорить, «что Fortran не имеет такой проблемы». В приведенном примере медленным будет обращение уже к элементам матрицы A[i][k].
Если хочется добиться еще большей производительности, стоит взглянуть в сторону эффективных реализаций BLAS'овской dgemm.
Также, как оказывается, по запросу «BLAS java» можно много чего нагуглить.
Успехов!
И не совсем корректно говорить, «что Fortran не имеет такой проблемы». В приведенном примере медленным будет обращение уже к элементам матрицы A[i][k].
Если хочется добиться еще большей производительности, стоит взглянуть в сторону эффективных реализаций BLAS'овской dgemm.
Также, как оказывается, по запросу «BLAS java» можно много чего нагуглить.
Успехов!
Про блочный алгоритм я знал и про Штрассена знал. Я хотел добиться сравнимой скорости без использования быстрых алгоритмов.
Спс за советы :)
Спс за советы :)
Как можно добиться скорости без использования быстрых алгоритмов? :)
Выходит что это скорее академический интерес, чем практическая работа? ведь иначе причин не использовать «быстрые» алгоритмы я не вижу.
Действительно основная стоимость в анализе мелких трюков оптимизации на приемре этого алгоритма, чем реальная оптимизация алгоритма умножения матриц, которую можно было бы использовать.
Действительно основная стоимость в анализе мелких трюков оптимизации на приемре этого алгоритма, чем реальная оптимизация алгоритма умножения матриц, которую можно было бы использовать.
Не подскажете, в каком месте библиотеки непосредственно находится этот код?
Параметры A, B и C имеют тип Matrix?
Параметры A, B и C имеют тип Matrix?
Я немного перефразировал код, чтобы он бы понятнее. Вам нужно смотреть класс la4j.matrix.DenseMatrix. Метод multiply(Matrix matrix);
Не вижу такого класса
Ну как же. Вот он — code.google.com/p/la4j/source/browse/trunk/src/la4j/matrix/DenseMatrix.java
Только с небольшим зачечанием. Грязный хак с исключениями еще не попал в trunk. С точки зрения перформанса это хорошее решение. А вот с точки зрения стабилити — не уверен.
Я привел его просто для примера в статье. Возможно, скокро его закомичу.
Я привел его просто для примера в статье. Возможно, скокро его закомичу.
Странно, в архиве нет. Они на гугл-коде не автоматически обновляются?
isTreangle() -> isTriangle()
Станет ещё быстрее если использовать простой массив вместо массива массивов («двумерного» массива)
Очень понравилось как изложен ход мыслей при решении задачи по оптимизации. Пишите еще.
Помнится ещё в лохматом 2007 году Алексей Тутубалин перемножением матриц процессоры «щупал»:
blog.lexa.ru/2007/01/04/o_peremnozhenii_matric_i_prochix_arxitekturnix_zamorochkax.html
Правда он все это делал на C.
blog.lexa.ru/2007/01/04/o_peremnozhenii_matric_i_prochix_arxitekturnix_zamorochkax.html
Правда он все это делал на C.
Спс за ссылку!
Там в таблице для матрицы 1024x1024 время 2.58 (что почти сравнимо с моим). Учитывая что это а) 2007 год б) Си в) Старый добрый VS2005.
Там в таблице для матрицы 1024x1024 время 2.58 (что почти сравнимо с моим). Учитывая что это а) 2007 год б) Си в) Старый добрый VS2005.
Странно. Обычно «щупают» решением СЛАУ.
А он потом этими же матрицам «щупает» CUDA…
Вроде параллелятся они не плохо…
Вроде параллелятся они не плохо…
Да, параллелятся хорошо. Извините, не могу вспомнить, где в вычислительной физике нужны быстрые перемножения матриц и где эта операция была бы «горлышком бутылки». В 3D графике понятно, все преобразования пространства — перемножения матриц.
А вот решение СЛАУ — это то, к чему сводятся решения разностных задач в неявных схемах и всевозможные методы конечных элементов. И вот они уже решаются блочной LU декомпозицией.
А вот решение СЛАУ — это то, к чему сводятся решения разностных задач в неявных схемах и всевозможные методы конечных элементов. И вот они уже решаются блочной LU декомпозицией.
Очередная порция вредных советов, основанная на неправильных измерениях.
Пожалуй, единственная содержательная оптимизация из вышеперечисленных — Шаг 2.
Во-первых, забудьте про Client VM — она уже в прошлом. На многопроцессорном компьютере с >=2GB RAM (т.е. практически на любом современном ноутбуке) предпочтительней запускать Server VM. К счастью, в новых релизах JDK больше не будет разделения на client/server, останется одна Tiered VM.
Во-вторых, вспомните про правила бенчмаркинга, если вдруг вы измеряете не так.
Теперь по оптимизациям.
Шаг 1: final int aColumns = A.columns() писать неплохо, но эта оптимизация в любом случае выполняется C2-компилятором автоматически.
Шаг 3: В случае Server VM на 64-битной системе применение этой «оптимизации» ухудшило результат на 3%. C2-компилятор лучше справляется с простой вложенностью циклов.
Шаг 4: Вообще зло. Мало того, что использование исключений при нормальном поведении — крайне плохой стиль, так еще бросание Exception — самая дорогая операция в Java VM, исчисляемая десятками, а то и сотнями тысяч простых арифметических операций. При бросании исключения происходит деоптимизация фреймов (т.е. возврат из скомпилированного кода в интерпретируемый), проход по стеку с заполнением stack trace, поиск exception handler'а. Конечно, 1000 операций это слишком мало, чтоб заметить разницу, попробуйте вставить ловлю исключения во внутренний цикл. Кроме того, C2-компилятор умет сам избавляться от лишних проверок на выход за пределы массива (array bounds check elimination).
Вообще, пример с матрицами очень хорош для совсем другого рода высокоуровневых оптимизаций: распараллеливания вычислений и преобразования многомерных массивов в одномерные, но вы про них даже словом не обмолвились.
Пожалуй, единственная содержательная оптимизация из вышеперечисленных — Шаг 2.
Во-первых, забудьте про Client VM — она уже в прошлом. На многопроцессорном компьютере с >=2GB RAM (т.е. практически на любом современном ноутбуке) предпочтительней запускать Server VM. К счастью, в новых релизах JDK больше не будет разделения на client/server, останется одна Tiered VM.
Во-вторых, вспомните про правила бенчмаркинга, если вдруг вы измеряете не так.
Теперь по оптимизациям.
Шаг 1: final int aColumns = A.columns() писать неплохо, но эта оптимизация в любом случае выполняется C2-компилятором автоматически.
Шаг 3: В случае Server VM на 64-битной системе применение этой «оптимизации» ухудшило результат на 3%. C2-компилятор лучше справляется с простой вложенностью циклов.
Шаг 4: Вообще зло. Мало того, что использование исключений при нормальном поведении — крайне плохой стиль, так еще бросание Exception — самая дорогая операция в Java VM, исчисляемая десятками, а то и сотнями тысяч простых арифметических операций. При бросании исключения происходит деоптимизация фреймов (т.е. возврат из скомпилированного кода в интерпретируемый), проход по стеку с заполнением stack trace, поиск exception handler'а. Конечно, 1000 операций это слишком мало, чтоб заметить разницу, попробуйте вставить ловлю исключения во внутренний цикл. Кроме того, C2-компилятор умет сам избавляться от лишних проверок на выход за пределы массива (array bounds check elimination).
Вообще, пример с матрицами очень хорош для совсем другого рода высокоуровневых оптимизаций: распараллеливания вычислений и преобразования многомерных массивов в одномерные, но вы про них даже словом не обмолвились.
О каком С2 вы говорите?
1 ) Это библиотека для простых пользователей, которые даже не знают что Hotspot есть клиентский а есть серверный.
2) Это не бенчмарка, где все еречисленные вещи (распараллеливание) были бы интерестными;
3) Это библиотека. Еще раз повторю. Распараллеливание ее считается чуть ли не дурным тоном. Привидите мне хоти один пример (кроме MKL)? Считается априори, что пользователь если ему надо — сам напишет map-reduce код используя рутины библиотеки для парралельного исполнения.
1 ) Это библиотека для простых пользователей, которые даже не знают что Hotspot есть клиентский а есть серверный.
2) Это не бенчмарка, где все еречисленные вещи (распараллеливание) были бы интерестными;
3) Это библиотека. Еще раз повторю. Распараллеливание ее считается чуть ли не дурным тоном. Привидите мне хоти один пример (кроме MKL)? Считается априори, что пользователь если ему надо — сам напишет map-reduce код используя рутины библиотеки для парралельного исполнения.
С1 и С2 — это условные названия JIT-компиляторов в Client VM и Server VM соответственно.
Пользователям про них и не надо знать, тем более, что уже через год, думаю, Client VM почти нигде не останется.
Я считаю, что не стоит делать из красивого и логичного кода некрасивый и нелогичный, называя это оптимизацией, только потому, что на устаревающей VM он работает чуточку быстрее.
Пользователям про них и не надо знать, тем более, что уже через год, думаю, Client VM почти нигде не останется.
Я считаю, что не стоит делать из красивого и логичного кода некрасивый и нелогичный, называя это оптимизацией, только потому, что на устаревающей VM он работает чуточку быстрее.
Похоже, что для Вас подобные задачи так и остались чисто алгоритмическо-математическими.
Есть сотня кодов, где подобные задачи приходится распараллеливать:
1) Enzo гидродинамический код с МГД и AMR (http://lca.ucsd.edu/portal/software/enzo)
2) ZEUS: lca.ucsd.edu/portal/software/zeus-mp2
Разве для Java нет BLAS/LAPACK?
Есть сотня кодов, где подобные задачи приходится распараллеливать:
1) Enzo гидродинамический код с МГД и AMR (http://lca.ucsd.edu/portal/software/enzo)
2) ZEUS: lca.ucsd.edu/portal/software/zeus-mp2
Разве для Java нет BLAS/LAPACK?
UFO just landed and posted this here
да что там сервер, похоже что автор без прогрева мерил, даже в клиенте были бы совсем другие результаты
А есть где-нибудь поподробнее про механизм выкидывания exceptions в Java? Для меня вот было откровением, что при этом происходит деоптимизация. Проход по стек трейсу и поиск хендлера не выглядит как тяжелая операция, я бы предположил, что вот потом разворачивание стека до этого хендлера будет заметно тяжелее, чем собственно поиск и анализ. Впрочем, это мои догадки, было бы любопытно поглубже узнать этот вопрос.
Не знаю, я по исходникам изучал :)
Деоптимизация происходит не всегда (в частности, не требуется, когда exception handler есть в том же методе), а, вот, как раз для корректного разворачивания она нужна (т.к. один фрейм скомпилированного кода может соответствовать нескольким фреймам интерпретатора), для отпускания мониторов и т.п.
Деоптимизация происходит не всегда (в частности, не требуется, когда exception handler есть в том же методе), а, вот, как раз для корректного разворачивания она нужна (т.к. один фрейм скомпилированного кода может соответствовать нескольким фреймам интерпретатора), для отпускания мониторов и т.п.
Крут, завидую белой завистью. А не помнишь где конкретно эти исходники брать, а то тоже очень интересно. И приблизительно куда глядеть. Ну если не сложно, если сложно не надо, мне просто любопытно.
И еще, я вот не удивлюсь, что там какие-то оптимизации таки есть под это дело. Ну, надеюсь, что есть. А то деоптимизация на каждый эксепшен звучит устрошающе.
И еще, я вот не удивлюсь, что там какие-то оптимизации таки есть под это дело. Ну, надеюсь, что есть. А то деоптимизация на каждый эксепшен звучит устрошающе.
hg clone http://hg.openjdk.java.net/jdk7/hotspot/hotspot
src/cpu/x86/vm/sharedRuntime_x86_64.cpp
OptoRuntime::generate_exception_blob — генерация прослойки на ASM, вызываемой из скомпилированного кода;
src/share/vm/opto/runtime.cpp
OptoRuntime::handle_exception_C_helper — обработка Exception в контексте VM;
src/share/vm/runtime/sharedRuntime.cpp
SharedRuntime::compute_compiled_exc_handler — поиск Exception Handler.
А где параметры запуска? Где описание того как мерили время?
прикрутили бы еще какой-то метод с передачей произвольного количества матриц внутрь и реализацией такого вот:
ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B5_%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86
ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B5_%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86
Насчет фортрана что-то не понял. В одной матрице идет по строкам, в другой — по столбцам. На фортране была бы абсолютно такая же ситуация, но для первой матрицы, нет?
>>Примечательно, что Fortran не имеет такой проблемы. Многомерные массивы в
>> нем хранятся по столбцам. Поэтому, кеш будет эксплуатироваться как следует
>> и штатная реализация кубического алгоритма будет работать в разы быстрее.
Не будет там транспонирование в разы быстрее, а если будет то не по этой причине.
Есть два варинта:
а) Читать по строкам, писать по столбцам;
б) Читать по столбцам, писать по строкам.
Так вот, читать по строкам будет быстре, за счет того что вы вычитываете целый кэшлайн и чаще всего с хардварным префетчем. Запись застрянет в кэше и вполне возможно что «склеится» на следущих итерациях.
Когда вы делаете блокинг (шаг 2) вы реализуете «софтварный» префетч, но тут надо подумать о ширине блока. После первого блока «миссов» начала следущих блоков будут у вас уже в кэше.
В отличие от Java на С можно поиграться еще и с явными префетчами, сделанными чаще всего на интринсиках:
msdn.microsoft.com/en-us/library/84szxsww%28v=vs.80%29.aspx
>> нем хранятся по столбцам. Поэтому, кеш будет эксплуатироваться как следует
>> и штатная реализация кубического алгоритма будет работать в разы быстрее.
Не будет там транспонирование в разы быстрее, а если будет то не по этой причине.
Есть два варинта:
а) Читать по строкам, писать по столбцам;
б) Читать по столбцам, писать по строкам.
Так вот, читать по строкам будет быстре, за счет того что вы вычитываете целый кэшлайн и чаще всего с хардварным префетчем. Запись застрянет в кэше и вполне возможно что «склеится» на следущих итерациях.
Когда вы делаете блокинг (шаг 2) вы реализуете «софтварный» префетч, но тут надо подумать о ширине блока. После первого блока «миссов» начала следущих блоков будут у вас уже в кэше.
В отличие от Java на С можно поиграться еще и с явными префетчами, сделанными чаще всего на интринсиках:
msdn.microsoft.com/en-us/library/84szxsww%28v=vs.80%29.aspx
Проведите, пожалуйста, тесты приведённых реализаций с размером 1024*1024 и 1025*1025. Должны получится забавные цифры.
С месяц пишу такой же топик о c++ :)
А как эти цифры соотностся с сишными библиотеками? Например с IPP? Интересно было бы увидеть сколько ещё можно выжать.
Использовать исключения в логике весьма неудачная идея
Шаг 4 у вас два раза
Всегда плюсую подобные статьи. Когда дочитав до конца приходишь к однозначному выводу, что текст понятен и ошибочен, то обсуждение/комментарии обещают быть информативными и полезными, а значит и достойны повисеть на главной…
Ну чо?
Как уже говорилось, надо было измерять на HotSpot.
Во-вторых, да, тут много примеров как делать не надо.
Например — исключения для управления. На практике, это очень тормозная операция. По опыту могу сказать, что отказ от такого рода управления в пользу традиционного может дать прирост в несколько раз(если исключения кидались особенно интенсивно).
Еще полезно посмотреть доклад «Performance Anxiety» Joshua Bloch.
Опять же, кто мешает использовать blas? Или написать обертку для нативных библиотек?
Как уже говорилось, надо было измерять на HotSpot.
Во-вторых, да, тут много примеров как делать не надо.
Например — исключения для управления. На практике, это очень тормозная операция. По опыту могу сказать, что отказ от такого рода управления в пользу традиционного может дать прирост в несколько раз(если исключения кидались особенно интенсивно).
Еще полезно посмотреть доклад «Performance Anxiety» Joshua Bloch.
Опять же, кто мешает использовать blas? Или написать обертку для нативных библиотек?
Ну ничо!
А на чем по вашему я измерял, если не на HotSpot (читайте про окружение)?
За ссылку на доклад спс.
Идея заключается в реализации «pure java library» безо всяких стронних штучек. Практика показывает, что разработчики на Java стараются избегать подобных нативных вещей и все более склоняются в сторону чистых Java решений.
А на чем по вашему я измерял, если не на HotSpot (читайте про окружение)?
За ссылку на доклад спс.
Идея заключается в реализации «pure java library» безо всяких стронних штучек. Практика показывает, что разработчики на Java стараются избегать подобных нативных вещей и все более склоняются в сторону чистых Java решений.
Шаг 4 — это такой бред. Никогда не стройте так логику на исключениях.
Рассмотрим простейший кубический алгоритм перемножения матриц. Пожалуй, его знает любой студент или даже школьник.
Видимо не все так просто. У вас там ошибка. Я понимаю, что статья не про это, но странно видеть одну и ту же элементарную ошибку в каждом листинге статьи.
Поправьте пожалуйста, а то копипастят же!
При перемножении матрицы A размерностью mxn и матрицы B размерностью nxk, должна получаться матрица C размерностью mxk. Ваш алгоритм будет работать корректно только для квадратных матриц.
Детали тут
Sign up to leave a comment.
История одной оптимизации