Введение в технику оптимизации циклов

Отлично. Заставляет пересмотреть написание циклов в лоб. Для нахождения числа Пи, думаю, можно применить сначала разрезание а потом развёртку.
Хотелось бы и дальше видеть Ваши статьи по оптимизации на Хабре.

Как насчет примеров с числами? Насколько эффективны подобные оптимизации, например, на современных двух/четырех-ядерных процессорах?

Спасибо, узнал много нового — постараюсь выполнять данные методики на практике (в случаях, когда это нужно)

С разрезанием странный пример — введение временной переменной на этой же итерации не поможет сократить количество необходимых регистров. В случае с gcc временная переменная повлияет только на название операнда в SSA (static single assignment) — вместо сделанного автоматически будет tmp.

>>>for (int i = 0; i < iN; i+=3){
res *= a[i];
res *= a[i+1];
res *= a[i+2];
}

В начале таких статей всегда должен быть эпиграф: «Преждевременная оптимизация — корень всех бед».

Следовало бы упомянуть об устройстве Даффа — en.wikipedia.org/wiki/Duff%27s_device.

Неужели те же gcc и icc не делают всего этого автоматически в -02 \ -03?

А в C# такие действия имеют смысл?

>>>for (int j = 0; j < jN; j++){
for (int k = 0; k < kN; k++){
for (int m = 0; m < mN; m++){
i = j * k + m;
a[i] = b[i] * c[i] + f[i]/e[i]+ x[i] — y[i] +
z[i]/r[i] + d[i] * x[i];
}
}
}
А здесь может так:
for (int j = 0; j < jN; j++){
for (int k = 0; k < kN; k++){
for (int m = 0; m < mN; m++){
i = j * kN + k * mN + m;
a[i] = b[i] * c[i] + f[i]/e[i]+ x[i] — y[i] +
z[i]/r[i] + d[i] * x[i];
}
}
}

о каком языке программирования идёт речь?

>>Доступ к памяти с большим шагом еще больше замедляет программу.
Предлагаю определить что значит «большой шаг».

Все ок, до тех пор пока вы не начнете выходить за пределы страницы (4К на обычных системах). В общем случае имеет смысл:
а) Утилизация обращений к памяти. Читается всегда кэшлайн (64байта), если вы работаете с float и идете со страйдом у вас часть кэшлинии получается ненужный мусор;
б) Эффективность префетчера. Хардварный префетчер хорошо распознает обычную загрузку с постоянным страйдом. Но — префетчер отключается в случае выхода за границу страницы (иначе возникнет TLB-miss, а это долго и сложно обработать).

>> вынесите из цикла все переменные, которые в нем не изменяются.
Это настолько тривиальная оптимизация, что в большинстве случаев можно «не париться» ухудшая, например, читабельность программы.

и немного про раскрутку цикла…
В современных процессорах небольшие циклы хорошо детектируются и сохраняются во внутреннем буфере уже после стадии декодировния. Это т.н. loop stream detector (LSD :) Если раскрутить такой цикл он может не влезть в буфер и получится замедление

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

Не факт, что компилятор оставит порядок ветвлений в нетронутом состоянии. Лучше для этого использовать встроенные возможности компилятора. У gcc и clang, например, есть специальный встроенный макрос __builtin_expect:

#if defined(__GNUC__) || defined(__clang__) /* Так можно определять наличие макроса,
                                             * но лучше это делать с помощью cmake/autoconf */
 #define COMPILER_HAVE_BUILTIN_EXPECT 1
#endif

#ifdef COMPILER_HAVE_BUILTIN_EXPECT
 #define likely(X) __builtin_expect((X), 1)
 #define unlikely(X) __builtin_expect((X), 0)
#else
 #define likely(X) (X)
 #define unlikely(X) (X)
#endif


for (i = 0;; i++)
 if (unlikely(i % 1000 == 0))
 {
   /* Менее вероятный переход */
 }
 else
 {
   /* Более вероятный переход */
 }