Производительность алгоритма неожиданно увеличивается в ~ 10 раз

Question

Справочная информация

Я недавно передал задание для моего класса по алгоритмам и структурам данных. Задача состояла в том, чтобы реализовать решение для поиска максимума-подмассива случайно сгенерированных массивов. Нас попросили реализовать как алгоритм перебора, так и рекурсивный алгоритм «разделяй и властвуй».

Затем нас попросили проанализировать время выполнения, чтобы увидеть, при каком размере проблемы алгоритм перебора будет быстрее, чем рекурсивное решение. Это было сделано путем измерения времени выполнения (с использованием измерений System.nanoTime ()) обоих алгоритмов для увеличения размера проблемы.

Однако определить это оказалось немного сложнее, чем я ожидал.

Любопытство

Если я начну с запуска обоих алгоритмов с размерами проблем 5000, более чем в 10 раз, время выполнения рекурсивного алгоритма сократится от одного прогона к следующему примерно в 10 раз (от ~ 1800 мкс выполнить, до ~ 200 мкс), и он останется намного быстрее для остальных итераций. Смотрите рисунок ниже для примера

2-й и 3-й столбец просто для проверки того, что оба алгоритма возвращают правильный максимальный подмассив

Это было протестировано на OS X 10.7.3 с Java 1.6.0_29 - результаты были одинаковыми при выполнении на ПК под управлением Windows 7 и Java 1.6 (точный номер версии неизвестен).

Исходный код программы можно найти здесь: https://gist.github.com/2274983

У меня такой вопрос: Что заставляет алгоритм внезапно работать намного лучше после "разогрева"?

Answer 1

Комментаторы уже указали, что JIT, вероятно, вызывает такое поведение, но кажется, что ОП не знает, что это такое. Так что просто кратко объясню:

Ваша виртуальная машина Java может запустить программу двумя способами:

1. Интерпретация байт-кода Java. По сути, интерпретатор «обходит» байт-коды один за другим, проверяет, что каждый из них, и выполняет соответствующее действие.

2. Преобразование байт-кода в машинный код, который базовый ЦП может запускать напрямую. Это называется «Компиляция точно в срок» или JIT.

Программы, которые были JIT-обработаны для машинного кода, работают намного быстрее, но компиляция требует времени, что может замедлить запуск программы. Таким образом, ваша JVM идет на компромисс: изначально она просто интерпретирует байт-код, но если определенный метод выполняется много раз, JIT компилирует , этот отдельный метод только . Обычно только небольшая часть программного кода будет выполняться много раз (внутренние циклы и т. Д.), Поэтому эта стратегия эффективна.

Результатом этого является то, что когда вы тестируете код Java, вы должны сначала "прогреть" JVM, выполняя ваш код в цикле достаточное количество раз, чтобы все критичные для производительности методы были скомпилированы JIT.

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

Answer 2

Я предлагаю вам запустить с -XX:+PrintCompliation, и вы должны увидеть, что после примерно 10 000 вызовов или итераций критические методы были скомпилированы.Это покажет вам, какие методы имели значение, если вы хотите увидеть, какой код проверять, если вы хотите знать, что посмотреть.Весь смысл компиляции в том, чтобы повысить производительность вашего кода.

---

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

Чтобы иметь хороший пример, вам нужно оптимизировать код, поэтому я

• уронил Math.floor (), поскольку он ничего не делает, (hi + lo) /2 всегда является целым числом.Самый быстрый и безопасный способ сделать это - (hi + lo) >>> 1
• , использующий Math.max для получения максимума.
• добавил break;, чтобы остановить циклы суммирования при достижении максимума.

Для меня это сократило время на 70%, полученное соотношение составляет 110 раз.

Answer 3

Одно из предложений, не читая ни одной строки вашего кода, заключается в том, что когда вы «прогреваете» свое приложение, вы получаете виртуальную машину с некоторым объемом памяти, который фиксирован для вашего приложения.

Например, позволяетскажем, ваши 5000 объектов массива в ArrayList - один за другим.Список массивов начинается с фиксированного размера, а когда он достигает своего предела, он удваивает свой размер и копирует старый массив в новый.Если вы повторно используете этот ArrayList - во втором запуске этот список будет в идеальном размере и будет работать быстрее.

Такая ситуация может возникнуть в некоторых других местах.