На Сodeforces часто возникают обсуждения различных оптимизаций и особенностей работы современных процессоров. Думаю, будет интересно почитать про ситуацию, когда выигрыш в производительности достигается довольно неочевидным образом, полагаясь на branch prediction (предсказание переходов). Что это такое, и какая ситуация рассматривается, можно почитать вот тут: http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array
Вкратце, ситуация следующая: простая линейная обработка массива целых чисел на конкретном примере выполняется почти в 6 раз быстрее, если предварительно этот массив отсортировать. Вопрос — почему?
Странно, что именно в 6 раз. Казалось бы, должно быть в ~2 раза меньше обращений к памяти.
Но вот что более странно: почему не оптимизируется цикл по i?
Я не являюсь особым знатоком архитектуры современных процессоров, но сам факт существования конвейера, кэшей разного уровня и предсказателя переходов уже не дает возможности вот так навскидку оценить во сколько на самом деле должно быть быстрее/медленнее в данном случае, даже зная характеристики конкретного процессора.
По поводу второго вопроса, там под ответом есть как раз информация о том, какие оптимизации в каких компиляторах приводят к другим результатам тестирования. ICC, например, переставляет циклы местами.
Нам (MSU Unpredictable) года 4 назад branch prediction помог на контесте (т.е. немного переписали один метод, избавившись от "if" ценой небольшого увеличения числа операций; как ни странно, это действительно помогло справиться с TL). Так что вполне жизненная оптимизация :)
Касается ли данное ухищрение с сортированным массивом и Явы?
Там ведь по ссылке в самом вопросе приводится пример кода и на джаве.