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

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

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

В операторах ветвления («if», «?» и «switch») константные условия встречаются редко и обычно являются следствием чрезмерного увлечения #define, вот, например, как здесь:

неоптимизированный вариант

#define MAX_SIZE 1024

#define REQ_SIZE 512

#define HDR_SIZE 16

…

int a = REQ_SIZE + HDR_SIZE;

if (a <= MAX_SIZE) foo(a); else return ERR_SIZE;

За исключением Intel C++, все рассматриваемые компиляторы выполняют константную подстановку, оптимизируя код, избавляясь от ветвления и ликвидируя «мертвый код», который никогда не выполняется:

foo(528);

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

[удаление копий переменных.]

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

В англоязычной литературе данный прием называется «размножением копий» («copy propagation»), что на первый взгляд не совсем логично, но если задуматься, то все проясняется: да, мы сокращаем переменные, размножая копии хранящихся в них значений, что наглядно продемонстрировано в следующем примере:

Переменные a и b — лишние

main(int n, char** v)

{

int a, b;

…

a = n+1;

b = 1-a; // избавляется от переменной a: (1 – (n + 1));

return a-b; // избавляется от переменной b: ((n + 1) – (1 – (n + 1)));

}

После оптимизации переменные a и b исчезают, а return возвращает значение выражения (2*n+1):

main(int n, char** v)

{

return 2*n+1;

}

[устранение хвостовой рекурсии.]

Хвостовой рекурсией («tail recursion») называется такой тип рекурсии, при котором вызов рекурсивной функции следует непосредственно за оператором return. Классическим примером тому является алгоритм вычисления факториала:

int fact(int n, int result)

{

if(n == 0)

{

return result;

}

else

{

return fact(n - 1, result * n);

}

}

Вызов функции — достаточно «дорогостоящая» (в плане процессорных тактов) операция, и, за исключением Intel C++, все рассматриваемые компиляторы трансформируют рекурсивный вызов в цикл:

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

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

[что надо оптимизировать.]

Теперь поговорим о том, с чем оптимизирующие компиляторы не справляются и начинают буксовать, резко снижая эффективность целевого кода. Помочь им выбраться из болота — наша задача! Чип и Дейл уже спешат! Ну а мыщъх вращает хвостом. Руководит, значит.