С-шные трюки от мыщъх'а (выпуск 2)

Автор: (c)Крис Касперски ака мыщъх

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

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

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()
{
        char buf; 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. Оптимизированный вариант - счетчик цикла совмещен с указателем на массив.

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