Трюки от Криса

Крис Касперски

Хакер, номер #091, стр. 091-132-1

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

Борьба с инвариантами

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

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

{

x += s[a];

}

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

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

n = strlen(s);

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

{

x += s[a];

}

Выравнивание строк

Наиболее эффективно обрабатываются строки, начинающиеся с адреса, кратного четырем. Именно так компилятор размещает их в стеке и статической памяти. Отсюда функция 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];

}

Компилятор не может поместить переменную 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; // запись конечного результата в память

}

Неудачный выбор приоритетов в Си

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

Содержание  Вперед на стр. 091-132-2
ttfb: 3.1380653381348 ms