c-triks-II

сишные трюки от мыщъха

крис касперски ака мыщъх, no-email

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

борьба с инвариантами: самой распространенной ошибкой, в разы снижающей производительность, является присутствие функций-инвариантов в теле цикла. Вот классический пример:

for(a = 0, x = 0; a < strlen(s); a++)

{

x += s[a];

}

Листинг 1 не оптимизированный вариант с инвариантом в теле цикла

С точки зрения программиста очевидно, что функция strelen _не_ модифицирует строку s, а потому может быть вычислена лишь однажды. Только вот компилирует этого не знает, придерживаясь принципа: все, что может быть передано по ссылке, _может_ быть изменено, поэтому strlen(s) заново вычисляется на _каждой_ итерации цикла, что при длинных строках снижает производительность более чем на порядок!

Исправленный вариант выглядит так:

n = strlen(s);

for(a = 0, x = 0; a < n; a++)

{

x += s[a];

}

Листинг 2 оптимизированный вариант с выносом инварианта

выравнивание строк: наиболее эффективно обрабатываются строки, начинающиеся с адреса, кратного четырем. Именно так компилятор размещает их в стеке и статической памяти. отсюда функция strlen(s) выполняются эффективно, а вот strlen(s+1) — не очень. Тоже самое относится и ко всем остальным функциям. Поэтому, всегда стремитесь выравнивать строки, когда это только возможно. Скажем, «strcpy(s, «bytes »); strcat(s, very_long_string);» выполняется неэффективно, но если переписать код так: «strcpy(s, «bytes: »); strcat(s, very_long_string);», то скорость его выполнения значительно возрастет, за счет того, что адрес конца строки s станет кратен 4 байтам.

правильный выбор функций: при работе с относительно короткими строками замена strlen(s) на strchr(s, 0) может дать до 5-7% ускорения, а вот замена нескольких strcat'ов на последовательность вызов нестандартной функцией stpcpy (которая тем не менее присутствует _во всех_ современных компиляторах), дает выигрыш уже в разы!

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

Вот, например:

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

{

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

}

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

Компилятор не может поместить переменную dst в регистр, поскольку если ячейки *x и *dst частично или полностью перекрываются, модификация ячейки *dst приводит к неожиданному изменению *x! Бред, конечно, но Стандарт таких трюков не запрещает, а оптимизатор не имеет права отступать от Стандарта, поэтому обращения к памяти происходят на _каждой_ итерации, а это весьма «дорогостоящая» в плане процессорных тактов операция!

Переписанный код выглядит так:

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

{

int i,t =0;

for (i=0;i<n;i++) t+=x[i]; сохранение суммы во временной переменной *dst+=t; запись конечного результата в память

}

Листинг 4 оптимизированный вариант

операции разыменования: префиксы намного выгоднее по сравнению с постфиксов при разыменовании, в результате чего код while(*++p) существенно эффективнее чем while(*p++), во всяком случае на платформе x86 и, по всей видимости x86-64 (к сожалению, в силу отсутствия железа проверить возможности не было). Однако, операциями разыменования смешивать с постфиксами и префиксами следует _крайней_ осторожно, иначе можно получить очень неожиданный результат (см. «неудачный выбор приоритетов в Си»). При работе на x86 (с распространёнными компиляторами) использование индексов эффективнее сдвига указателей. Не всегда, но очень часто. То есть, код типа «for(a=0;a<len;a++) *dst++ = *src++;» гораздо сложнее оптимизируется, чем «for(a=0;a<len;a++) dst[a] = src[a];», хотя качественный оптимизатор в обоих случаях должен сгенерировать идентичный машинный код.

неудачный выбор приоритетов в Си: вопреки «здравому смыслу» конструкция типа *p[a]++ увеличивает отнюдь _не_ содержимое ячейки, на которую указывает *(p+a), а значение самого указателя p! Для достижения ожидаемого результата необходимо либо явно навязать наше намерение компилятору путем расстановки скобок: «(*p)[a]++;», либо же вовсе отказаться от оператора «++», заменив его оператором «+=» и тогда наш код будет выглядеть так: «*p[a]+=1;»

Представляется интересным докопаться до _сути_ происходящего. Ведь основное кредо Си - краткость. Чего стоит один неявный int, который попил много крови разработчикам компиляторов. И тут… вдруг сталкиваешься с таким расточительством! Ведь, чтобы использовать '*' надо ставить скобки, а это - целых два нажатия на клаву. Зачем? Может быть, есть такие ситуации, где именно такой расклад приоритетов дает выигрыш? Вообще: о чем думали в этот момент разработчики языка? В доступных мне книжках никаких вразумительных объяснений ситуации я так и не нашел.

…прозрение наступило внезапно и причина, как выяснилась, оказалась даже не в самом языке, а… в особенностях косвенной автоинкрементной/авто-декрементной адресации процессора PDP-11, из которого, собственно, и вырос Си. Команда типа «MOV @(p)+, xxx» пересылает содержимое p в xxx и затем увеличивает значение p. Да! Именно p, а отнюдь не ячейки, на которую p ссылается!!!

Так стоит ли удивляться тому, что люди, взращенные на идеологии PDP-11, перенесли ее поведение и на разрабатываемый ими язык? И, кстати, о птичках. Система адресации PDP-11 _намного_ мощнее, удобней и элегантнее, того уродства, что реализовано в x86…

Хотите испытать свой компилятор? Нет проблем! Вот довольно познавательный листинг!

main()

{

charbuf; char* p_buf[2]; char p; #define INIT buf=0x66; *p_buf=&buf;*(p_buf+1)=&buf; p=&p_buf; INIT; printf(«char p;\n»);

printf(«p = %p; *p = %p; p = %x\n\n»,p, *p, p);

*p[0]++;printf(«*p[0]++;\n»);

printf(«p = %p; *p = %p; p = %x\n»,p, *p, p);

printf(«смотрите, увеличилось _не_ содержимое p,\n»); printf(«а указатель, на который ссылается *p!\n»); printf(«т.е. мы получили _совсем_ не то, что хотели!\n\n»); INIT; (*p)[0]++;printf(«(*p)[0]++;\n»); printf(«p = %p; *p = %p; p = %x;\n»,p, *p, p); printf(«хорошо, заключаем *p в скобки, тем самым явно\n»); printf(«навязывая компилятору последовательность действий\n\n»); INIT; *p[0]+=1;printf(«*p[0]+=1;\n»); printf(«p = %p; *p = %p; p = %x;\n»,p, *p, **p);

printf(«забавно, но замена оператора ++ на оператор +=\n»);

printf(«эту проблему как рукой снимает!\n»);

}

Листинг 5 пример, демонстрирующий специфику приоритетов операций разыменования в Си

Для преодоления катастрофической нехватки регистров, некоторые компиляторы стремятся совмещать счетчик цикла с указателем на обрабатываемые данные. Код вида «for (i = 0; i < n; i++) n+=a[i];» трансформируется оптимизатором в «for (p= a; p < &a[n]; p++) n+=*p;» Экономия налицо! Вместо четырех переменных после преобразования остались всего лишь три!

Впервые (насколько мне известно) эта техника использовалась в компиляторах фирмы Hewlett-Packard, где она фигурировала под термином register reassociation. А что же конкуренты?! Возьмем следующий код (кстати, выдранный из документации на HP компилятор):

int a[10][20][30];

void example (void)

{

int i, j, k;

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

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

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

a[i][j][k] = 1;

}

Листинг 6 неоптимизированный кандидат на регистровую ре-ассоциацию

Грамотный оптимизатор должен переписать его так:

int a[10][20][30];

void example (void)

{

int i, j, k;

register int (*p)[20][30];

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

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

for (p = (int (*)[20][30]) &a[0][j][k], i = 0; i < 10; i++)

*(p++[0][0]) = 1;

}

Листинг 7 оптимизированный вариант — счетчик цикла совмещен с указателем на массив

Эксперимент показывает, что ни MicrosoftVisualC++, ни GCC не выполняют регистровых реассоциаций ни в сложных, ни даже в простейших случаях. С приведенным примером справился один лишь Intel C++, да и то лишь частично, поэтому, в критических к производительности случаях, оптимизировать код необходимо вручную.