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

Фоновая информация

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

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

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

Любопытство

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

2-й и 3-й столбцы - это просто подтверждение того, что оба алгоритма вернут правильный максимальный субарейр

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

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

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

Ответ 1

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

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

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

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

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

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