акробатика для программиста

КРИС КАСПЕРСКИ

Спецвыпуск: Хакер, номер #071, стр. 071-056-4

Рассмотрим типичный пример:

for(a=0;a<strlen(s);a++) b+=s[a];

Если только компилятор не заинлайнит функцию strlen, она будет вычисляться на каждой итерации цикла, что приведет к значительному снижению производительности. Но если вынести инвариант за пределы цикла, все будет ОК:

t = strlen(s);

for(a=0;a<t;a++) b+=s[a];

[нормализация циклов.]

Нормализованным называется цикл, начинающийся с нуля и в каждой итерации увеличивающий свое значение на единицу. В книгах по программированию можно встретить утверждение, что нормализованный цикл компилируется в более компактный и быстродействующий код, однако, это только теоретическая схема и многие процессорные архитектуры (включая x86) предпочитают иметь дело с циклом, стреляющимся к нулю.

Рассмотрим типичный цикл:

for (a = from; a < to; i+=(-step))

{

// тело цикла

}

Алгоритм нормализации выглядит так:

for (NCL = 0; i < (to - from + step)/step - 1; 1)

{

i = step*NLC + from;

// тело цикла

}

i = step * _max((to - from + step)/step, 0) + from;

Наибольшую отдачу нормализация дает на циклах с заранее известным количеством итераций, то есть когда выражение (to from + step)/step представляет собой константу, вычисляемую еще на стадии трансляции.

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

[разворот циклов.]

Процессоры с конвейерной архитектурой (к которым относится и x86) плохо справляются с ветвлениями (а циклы как раз и представляют одну из разновидностей ветвлений), резко снижая свою производительность. Образно их можно сравнить с гоночной машиной, ползущей по петляющей дороге. И у машины, и у процессора максимальная скорость достигается только на участках, свободных от ветвлений.

Компактные циклы вида for(a=0;a<n;a++) *dst++= *src++; исполняются крайне медленно и должны быть развернуты (unrolled). Под «разворотом» в общем случае понимается многократное дублирование цикла, которое в классическом случае реализуется так:

for(i=1; i<n;i+)

k += (n % i);

цикл, развернутый на 4 итерации (меньший размер, большая скорость)

for(i=1; i<n;i+=4)

{

k += (n % i) +\

(n % i+1) + \

(n % i+2) + \

(n % i+3);

}

// выполняем оставшиеся итерации

for(i=4; i<n;i++) k += (n % i);

За исключением Microsoft Visual C++, все остальные рассматриваемые компиляторы умеют разворачивать циклы и самостоятельно, но... делают это настолько неумело, что вместо ожидаемого увеличения производительности сплошь и рядом наблюдается ее падение, поэтому автоматический разворот лучше сразу запретить и оптимизировать программу вручную, подбирая подходящую степень разворота опытным путем (вместе с профилировщиком).

Тут ведь как — чем сильнее разворот, тем больше места занимает код, и появляется риск, что в кэш первого уровня он может вообще не влезть, вызывая обвальное падение производительности! (Подробнее о влиянии степени разворота на быстродействие можно прочитать в моей «технике оптимизации», электронная копия которой, как обычно, лежит на моем мыщъхином ftp://nezumi.org.ru).