Оптимизация в GCC — ответы на вопросы викторины

Рассказывает автор блога ridiculousfish.com

В этой статье даны ответы на 6 вопросов из викторины по оптимизациям компилятора GCC. В каждом по две вставки кода. Первая вставка иллюстрирует код до некой оптимизации, вторая — после нее. Сможет ли GCC изменить первый код таким образом, чтобы он стал вторым? Верна ли вообще проведенная оптимизация (быстрее ли второй код первого)?

Для тестов использовался древний GCC 4.2.1. Если новые версии ведут себя по-другому, то обязательно сообщите об этом мне!

1. Оптимизация рекурсии

GCC заменяет рекурсию:

			int factorial(int x) {
   if (x > 1) return x * factorial(x-1);
   else return 1;
}
		

вот таким циклом:

			int factorial(int x) {
   int result = 1;
   while (x > 1) result *= x--;
   return result;
}
		

Компилятор может преобразовывать некоторые рекурсивные функции в хвостовые рекурсивные, а затем в обычный цикл. Большинство компиляторов функциональных языков не может даже этого!

Мне нравится этот пример, потому что он подвергает сомнению тот факт, что хвостовая рекурсия — это улучшенный вариант обычной рекурсии. Мы уже знаем, что хвостовая рекурсия может выполнять с константными затратами памяти, если компилятор это поддерживает. В нашем же случае даже обычная рекурсия может быть оптимизирована так, что она не будет потреблять линейное количество памяти. Таким образом, хвостовая рекурсия перестает быть чем-то особенным, будучи интересной для нас только в тех случаях, когда наш компилятор не может оптимизировать обычную рекурсию.

 2. Вынесение вызова функции

Компилятор вынесет strlen() в отдельную переменную в таком коде:

			unsigned sum(const unsigned char *s) {
   unsigned result = 0;
   for (size_t i=0; i < strlen(s); i++) {
      result += s[i];
   }
   return result;
}
		

и он станет эквивалентен такому:

			unsigned sum(const unsigned char *s) {
   unsigned result = 0;
   size_t length = strlen(s);
   for (size_t i=0; i < length; i++) {
      result += s[i];
   }
   return result;
}
		

GCC сделает это, потому что strlen() — это встроенная функция. GCC распознает ее и оптимизирует ее использование в местах, где это требуется. Отключить это можно с помощью параметра -fno-builtin, указываемого при компиляции.

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

3. Замена умножения на 2 на сложение (целые числа)

В случаях с целыми числами код умножения на два:

			int double_it(int x) {
   return x * 2;
}
		

будет заменен сложением числа с самим собой:

			int double_it(int x) {
   return x + x;
}
		

GCC оптимизирует этот код. Вообще, этот пример — простое упражнение на снижение стоимости операций. Есть много способов оптимизировать этот код: на i386 GCC использует инструкцию add, на x86-64 — инструкцию leal, а на PowerPC осуществляет сдвиг на один разряд влево. В любом случае выходит что-то более эффективное, чем умножение на два.

А что будет с числами с плавающей точкой?

 4. Замена умножения на 2 на сложение (числа с плавающей точкой)

Казалось бы, клишком много неточностей в вычислениях с плавающей точкой. Будет ли заменен этот код:

			float double_it(float x) {
   return x * 2.0f;
}
		

вариантом ниже?

			float double_it(float x) {
   return x + x;
}
		

Эта оптимизация окутана мраком неопределенности — быть может, она неверна? Но нет, все правильно, GCC сделает это.

Операции с дробными числами в уме удобно моделировать так: сначала мы вычисляем точный результат, а потом округляем его до ближайшего представимого числа с плавающей точкой. С такой точки зрения, математически эта операция верна, ведь сложение числа с самим собой — это то же самое, что и умножение на два. Тем не менее, есть некоторые нюансы, которые усложняют положение вещей.

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

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

Еще один камень преткновения — NaN. Это значение запарывает многие потенциальные оптимизации. Например, мы не можем сократить x-x до 0, потому что NaN-NaN будет равно NaN. Однако перед выполнением операции можно проверять, имеют ли оперируемые данные приемлемые значения.

Мораль всего такова: компилятору гораздо труднее оптимизировать операции с плавающей точкой, чем целочисленную арифметику. И представленный пример с умножением на два — это исключение, а не выдержка из правил.

5. Замена деления на 2 на сдвиг вправо

Код с делением на два:

			int halve_it(int x) {
   return x / 2;
}
		

не будет заменяться сдвигом вправо:

			int halve_it(int x) {
   return x >> 1;
}
		

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

Эта проблема может быть исправлена c помощью добавления наиболее значимого бита к числителю, и GCC делает это.

6. Последовательность if-else против switch

Применяет ли GCC те же оптимизации к цепочке if-else:

			void function(int x) {
   if (x == 0) f0();
   else if (x == 1) f1();
   else if (x == 2) f2();
   else if (x == 3) f3();
   else if (x == 4) f4();
   else if (x == 5) f5();
}
		

что и к switch, как в вариант ниже?

			void function(int x) {
   switch (x) {
      case 0: f0(); break;
      case 1: f1(); break;
      case 2: f2(); break;
      case 3: f3(); break;
      case 4: f4(); break;
      case 5: f5(); break;
   }
}
		

GCC не делает это даже для длинных цепочек if-else, по крайней мере древняя версия 4.2.1, на которой я тестировал этот код (может, версии поновее ведут себя лучше в таком случае).

switch был оптимизирован в джамп-таблицу, а if-else стали всего лишь последовательностью сравнений.

Я был неприятно удивлен этим фактом. К счастью, clang делает эту оптимизацию.

Заключение

Многие думают, что оптимизации — это всего лишь изменение константы в Big-O нотации вашего кода. Тем не менее, как мы видим из примеров 1 и 2, оптимизации могут изменить асимптотику программы в лучшую сторону и даже повлиять на получаемый результат (пример 4).

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

И напоследок: не тратьте свое время на микрооптимизации. Они отнимают у вас время, не намного ускоряют код, и к тому же при их внесении легко допустить ошибку (как в примере 5).

Пишите свои программы с умом!