Как стать автором
Обновить
31
Карма
0
Рейтинг
Григорий Кошелев @gnkoshelev

Team Lead

  • Подписчики 22
  • Подписки

Альтернативный взгляд на задачу от Одноклассников с JPoint 2018

Строго говоря, ни одна из спецификаций (JLS, JVMS) это не гарантирует. Соглашусь с тем, что на практике проблема скорее всего надуманная.

Разбор задачек от Одноклассников на JPoint 2018

А может вы знаете лучшие решения? Добро пожаловать в комменты!

Вызов принят! Лучшие-нелучшие, но есть, что обсуждать. :)

Разбор перформансных задач с JBreak (часть 4)

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

Генеральная уборка в компании

Электронные книги тоже теперь дарят? :)
К тому же много кто предпочитает бумажные книги.

Разбор перформансных задач с JBreak (часть 4)

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

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

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

Генеральная уборка в компании

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

Я же пишу про альтернативный вариант, который сложнее для автора, но имеет ряд преимуществ.

Генеральная уборка в компании

Только не связывайтесь с издательствами — зачем лишняя головная боль с цензурой и правами, которые отходят издателю?

В компании же есть хорошие дизайнеры, которые смогут самостоятельно сверстать книгу?

А печать уже делать в типографии. Был опыт издания книг небольшим тиражом в Екатеринбурге (за отдельную плату можно получить ISBN) — могу рассказать, как это происходит.

Разбор перформансных задач с JBreak (часть 3)

Отправил соответствующий баг в Oracle по странному различию в производительности по сути идентичного кода (см. FinalOrNotFinalBenchmark). Сегодня подтвердили баг: JDK-8200412.

Разбор перформансных задач с JBreak (часть 4)

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

Разбор перформансных задач с JBreak (часть 4)

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


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

Разбор перформансных задач с JBreak (часть 4)

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

Разбор перформансных задач с JBreak (часть 4)

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

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

Разбор перформансных задач с JBreak (часть 4)

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

Разбор перформансных задач с JBreak (часть 4)

Насколько мне известно, цепочка получается подлиннее (даже без учёта перекомпиляции из C1 в C2): java -> bytecode -> IR -> native code (~ машинные коды).

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

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

Разбор перформансных задач с JBreak (часть 4)

К сожалению, у меня нет под рукой этой книги, но готов поспорить, что там нет ничего про интринсики в Java, как и нет информации о том, как реализовано возведение в степень в HotSpot 7 / 8 / 9.

Впрочем, всё это не отменяет того факта, что
в 90% случаев достаточно использовать подходящие структуры данных и алгоритмы.

Разбор перформансных задач с JBreak (часть 4)

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

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

Пример:
В некотором коде может произойти NullPointerException, но в течение сбора профиля оно ни разу не случалось, поэтому JIT-компилятор C2 скомпилировал только так называемый common case — код, который исполняется часто, а остальную часть кода (обработка NPE в данном случае) не скомпилировал вовсе, оставив так называемую uncommon trap. Если в какой-то момент возникнет NullPointerException, то HotSpot вынужден будет откатиться в режим интерпретатора для этого участка кода, а в результате получить деоптимизацию всего метода. Когда JIT-компилятор вновь решится компилировать код и как он это сделает — предсказать мне невозможно.

Разбор перформансных задач с JBreak (часть 4)

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

Конечно, всё зависит от задач. Но если брать среднюю температуру по больнице, предположение выше не так уж далеко от истины.

Полный перечень intrinsic-функций в HotSpot в JDK 7, 8, 9 и 10

Про интринсик
_dpow     java.lang.Math.pow(double, double)

опубликовал разбор задачи с JBreak: Разбор перформансных задач с JBreak (часть 4).

Полный перечень intrinsic-функций в HotSpot в JDK 7, 8, 9 и 10

Их упоминание в vmSymbols.hpp обусловлено необходимостью отличить их в рантайме по другой причине.
Выглядит костыльно. Дополню статью этим комментарием.

Throwable.fillInStackTrace начиная с JDK 9 вовсе убрали из списка интринсиков.

Информация

В рейтинге
Не участвует
Откуда
Екатеринбург, Свердловская обл., Россия
Работает в
Зарегистрирован
Активность