Сортировка во второй раз быстрее

Question

В рамках школьного упражнения я хотел бы сравнить и сравнить алгоритмы сортировки с упражнением Java.

Я сам реализовал алгоритмы сортировки, и мы сортируем объекты класса Person, который реализует интерфейс Comparable.

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

• Лучшими: массив уже отсортированный
• Худшие: массив отсортирован в обратном порядке
• Avg: объекты в массиве в случайном порядке

Это мой выход:

1-call of the sorting methods 
InsertionSort Best:1799ms Worst:78ms Avg:789ms 
MergeSort  Best:10ms  Worst:3ms Avg:5ms  

2-call of the sorting methods 
InsertionSort Best:1065ms Worst:39ms Avg:691ms 
MergeSort  Best:3ms  Worst:2ms Avg:5ms  

3-call of the sorting methods 
InsertionSort Best:1066ms Worst:39ms Avg:692ms 
MergeSort  Best:3ms  Worst:2ms Avg:5ms  

4-call of the sorting methods 
InsertionSort Best:1065ms Worst:39ms Avg:691ms 
MergeSort  Best:3ms  Worst:2ms Avg:5ms  

Является ли JVM любой оптимизацией при последующих вызовах?
Я озадачен и очень признателен за любую помощь!

Редактировать: Спасибо за предложения и ответы до сих пор! Чтобы сделать несколько точек понятными - каждый из вызовов в моем выводе относится к времени, которое требуется для полной сортировки!
После каждой сортировки я снова делаю новый вызов с массивами UNSORTED!

Мой исходный код может быть загружен как затмение проекта в виде архива, по следующей ссылке: Dropbox dropbox link to eclipse project.zip

P.S. У меня нет опыта работы с профайлерами - если бы вы могли указать мне на учебное пособие или так было бы здорово.

Answer 1

Обработка отсортированного массива выполняется быстрее, чем обработка неупорядоченной из-за Branch Prediction.
Обложка экстенсивно в the most famous Stack Overflow question.

Answer 2

Здесь есть много вещей, как показывает разнообразие ответов.

Но длительное время работы первого запуска, вероятно, объясняется компиляцией JIT (точно в момент времени). Как discussed here, ваш алгоритм будет работать в JVM некоторое время как интерпретируемый байт-код. Когда монитор Hotspot определяет, что петли вашего типа являются дорогостоящими, JVM скомпилирует их в собственный код. После этого они будут работать значительно быстрее. Первый пробег становится недостатком работы в интерпретаторе на некоторое время плюс дополнительные затраты на компиляцию. Вот почему "warming up" is a common term in Java benchmarks.

Различия в производительности на разных входах привязаны к алгоритму сортировки. Многие алгоритмы ведут себя по-разному, основываясь на первоначальной организации данных, и многие из них намеренно организованы, чтобы преуспеть в первоначально отсортированных или почти отсортированных данных. Here is a brilliant demonstration for the case of nearly sorted input. Например. вставка сортировки - это квадратичное время в целом, но линейное время на почти отсортированном входе (на самом деле O ((k + 1) n) для ввода размера n, где элементы не более, чем k позиций из правильно отсортированного).

Тогда есть проблема с предсказанием ветви, на которую ссылается ссылка. Современные процессоры имеют различные механизмы, которые пытаются «угадать», каким образом ветвь (по существу, «if» на уровне машины) будет идти на основе недавней истории, собранной по мере запуска программы. Стоимость плохой догадки высока. На доброту предположения, вероятно, повлияют как алгоритм, так и данные.