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

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

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

обработка массивов по столбцам (неоптимизированный вариант)

for(j=0;j<m;j++)

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

a[i][j] = b[i][j] + c[i][j];

Здесь три массива обрабатываются по столбцам, что крайне непроизводительно, и для достижения наивысшей эффективности циклы i и j следует поменять местами. Устоявшегося названия у данной методики оптимизации нет, и в каждом источнике она называется по-разному: «loop permutation/interchange/reversing», «rearranging array dimensions» и т. д. Как бы там ни было, оптимизированный вариант выглядит так:

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

for(j=0;j<m;j++)

a[i][j] = b[i][j] + c[i][j];

Все рассматриваемые компиляторы поддерживают данную стратегию оптимизации, однако их интеллектуальные способности очень ограничены, и со следующим примером справляется только Hewlett-Packard C++:

сложный случай обработки данных по столбцам

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

for (j=0; j<n; j++)

for (k=0; k<n; k++)

a[j][i] = a[j][i] + b[k][i] * c[j][k];

[удаление лишних обращений к памяти.]

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

пример с лишними обращениями к памяти, от которых нельзя избавиться

f(int *a, int *b)

{

int x;

x = *a + *b; // сложение содержимого двух ячеек

*b = 0x69; // изменение ячейки *b, адрес которой не известен компилятору

x += *a; // нет гарантии, что запись в ячейку *b не изменила ячейку *a

}

Компилятор не имеет права на размещение содержимого ячейки *a в регистровой переменной, поскольку, если ячейки *a и *b частично или полностью перекрываются, модификация ячейки *b приводит к неожиданному изменению ячейки *a! Бред, конечно, но ведь Стандарт этого не запрещает, а компилятор обязан следовать Стандарту, иначе его место — на свалке.

То же самое относится и к следующему примеру:

лишние обращения к памяти, от которых можно избавиться вручную

f(char *x, int *dst, int n)

{

int i;

for (i = 0; i < n; i++) *dst += x[i];

}

Компилятор не имеет права выносить переменную dst за пределы цикла, в результате чего обращения к памяти происходят в каждой итерации. Чтобы повысить производительность, код должен быть переписан так:

f(char *x, int *dst, int n)

{

int i,t =0;

for (i=0;i<n;i++) t+=x[i]; // сохранение суммы во временной переменной

*dst+=t; // запись конечного результата в память

}

[регистровые ре-ассоциации.]

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

Код вида «for (i = 0; I < n; i++) n+=a[i];» легко оптимизировать, если переписать его так: «for (p= a; p < &a[n]; p++) n+=*p;». Насколько известно мыщъх'у, впервые эта техника использовалась в компиляторах фирмы Hewlett-Packard, где она фигурировала под термином «register reassociation». А вот остальные рассматриваемые нами компиляторы этого делать, увы, не умеют.