Pull to refresh

Comments 23

Может книга есть какая нибудь, в стиле «Пишем быстрый код на Java»?
По аналогии «Эффективное использование С++».

Такая книга будет устаревать довольно быстро. А полезные советы превращаться во вредные.

Кажется, что в 90% случаев достаточно использовать подходящие структуры данных и алгоритмы. В связи с чем могу порекомендовать книги Лафоре (Структуры данных и алгоритмы в Java) и Седжвика (Алгоритмы на Java).
Ещё в 9% случаев нужно копать в сторону эффективности используемых фреймворков и тулкитов.
Оставшийся 1% бизнесу, как правило, не интересен.

Конечно, всё зависит от задач. Но если брать среднюю температуру по больнице, предположение выше не так уж далеко от истины.
Седжвик, да, знаком. У него есть для С++ такая же, с неё я начинал. С Лафоре меньше, но всё таки, они больше на программирование(структуры и данные) на Java, нежели на эффективное программирование.

Видимо, принцип «скомпилируй, посмотри сгенерированный код» до сих пор актуален.
И ещё мини вывод: знание ассемблера нужно.
Видимо, принцип «скомпилируй, посмотри сгенерированный код» до сих пор актуален.
И ещё мини вывод: знание ассемблера нужно.

Это в полной мере справедливо для C++, т.к. AOT-компилятор. С Java всё намного сложнее, т.к. в JIT-компиляторе огромное количество оптимизаций, а их применение зависит от собранного профиля. Последнее означает, что результат JIT-компиляции может отличаться не только между кодом реального приложения и бенчмарка, так и в разные запуски приложения, да даже в разные моменты времени в одном запущенном приложении.

Пример:
В некотором коде может произойти NullPointerException, но в течение сбора профиля оно ни разу не случалось, поэтому JIT-компилятор C2 скомпилировал только так называемый common case — код, который исполняется часто, а остальную часть кода (обработка NPE в данном случае) не скомпилировал вовсе, оставив так называемую uncommon trap. Если в какой-то момент возникнет NullPointerException, то HotSpot вынужден будет откатиться в режим интерпретатора для этого участка кода, а в результате получить деоптимизацию всего метода. Когда JIT-компилятор вновь решится компилировать код и как он это сделает — предсказать мне невозможно.
И еще одно — лобовая реализация описанного в ассемблере скорее всего будет эффективнее безумных портянок кода, сгенерированного двойным преобразованием java -> bytecode -> native code. Учим асм?
Насколько мне известно, цепочка получается подлиннее (даже без учёта перекомпиляции из C1 в C2): java -> bytecode -> IR -> native code (~ машинные коды).

И еще одно — лобовая реализация описанного в ассемблере скорее всего будет эффективнее

В конкретном примере из статьи (и во многих других) — да. Но не стоит недооценивать умение JIT-компилятора учитывать собираемый профиль (= учитывать реальное исполнение кода, реальные данные в нашем приложении).
90% случаев достаточно использовать подходящие структуры данных и алгоритмы.

И писать оптимальные SQL селекты. Если там несколько join-ов, которые выдают 50 тысяч строчек по 100 столбцов, а потом данные фильтруются Java-кодом, то тут даже ассемблер не поможет.
Дональд Э. Кнут. Искусство программирования. Том 2. Получисленные алгоритмы. Третье издание. Раздел 4.6.3. Вычисление степеней, стр. 513. — и нет никакой необходимости в объемных исследованиях реализаций :-)
К сожалению, у меня нет под рукой этой книги, но готов поспорить, что там нет ничего про интринсики в Java, как и нет информации о том, как реализовано возведение в степень в HotSpot 7 / 8 / 9.

Впрочем, всё это не отменяет того факта, что
в 90% случаев достаточно использовать подходящие структуры данных и алгоритмы.
Всегда можно написать свой эффективный велосипед, например, возведение в конкретную степень. Допустим, так:
b = a*a;
c = b*b;
res = c*c;

Или можно воспользоваться бинарным разложением степени (Алгоритмические трюки для программистов). Пример выше — частное решение.

Возможно есть ещё способ использовать биты в экспоненте, в случае степени кратной 2.
У меня по этому поводу что то смутное в голове есть.

Java умеет в JNI, а вызываемый модуль можно и на асме написать, главное, что бы выигрыш был больше, чем накладные расходы на вызов этой функции.
В общем случае, когда операнды типа float/double, FPU прекрасно посчитает x^y как 2^(y*log(x)) (при условии, что x > 0). Правда, FYL2X (y*log(x)) раз в 20-40 дороже умножения/деления в зависимости от архитектуры. Но выигрыш будет заметен на больших степенях.
Java умеет в JNI, а вызываемый модуль можно и на асме написать, главное, что бы выигрыш был больше, чем накладные расходы на вызов этой функции.

Насколько дорого ходить в JNI — можно прикинуть, если сравнить бенчмарки с интринсиком и без (последний бенчмарк).

Странно, что jit не умеет в такую оптимизацию. Те же gcc и clang умеют проводить подобного рода оптимизации. Кто-нибудь может подсказать, почему это всё ещё не реализовано в java jit компиляторе?

В какую именно? Заменять a * a * ... * a, как это сделано в примере? Так это не совсем законно (нарушает лево-ассоциативность операции умножения).

Нет. В Java вычисления с плавающей точкой реализованы в соответствии со стандартом IEEE 754. Это явно указано в javadoc к java.lang.StrictMath.


Напротив, --ffast-math допускает использование оптимизаций, нарушающих указанный стандарт.

Поэтому я и спросил про наличие такого флага :) понял, спасибо. Правильно ли я понимаю, что jit может проводить оптимизации над int?

Попробовал проверить, что делает JIT-компилятор в случае использования int — никаких намёков на оптимизацию.

Попробовал ещё в SIMD (независимые вычисления, простые циклы) — тоже безрезультатно.

Вывод: либо JIT-компилятор в это не умеет, либо я неправильно его готовлю.

Спасибо!
Надо будет поизучать этот вопрос. Неспроста же есть ключик -XX:UseAVX...

UFO landed and left these words here

Android — это вообще отдельный мир со своим байткодом и VM (Dalvik / ART) со своим JIT'ом.

Only those users with full accounts are able to leave comments. Log in, please.