Оптимізація у GCC
У цій статті надано відповіді на 6 питань з вікторини щодо оптимізацій компілятора GCC. У кожному по дві вставки коду. Перша вставка ілюструє код до певної оптимізації, друга - після неї. Чи зможе GCC змінити перший код таким чином, щоб він став другим? Чи вірна взагалі проведена оптимізація (чи швидше другий код першого)?
Для тестів використовувався давній GCC 4.2.1. Якщо нові версії поводяться інакше, то обов'язково повідомте про це мені!
1. Оптимізація рекурсії
GCC замінює рекурсію:
ось таким циклом:
Компілятор може перетворювати деякі рекурсивні функції на хвостові рекурсивні, а потім у звичайний цикл. Більшість компіляторів функціональних мов навіть цього не може!
Мені подобається цей приклад, тому що він сумнівається в тому, що хвостова рекурсія — це покращений варіант звичайної рекурсії. Ми знаємо, що хвостова рекурсія може виконувати з константними витратами пам'яті, якщо компілятор це підтримує. У нашому випадку навіть звичайна рекурсія може бути оптимізована так, що вона не споживатиме лінійну кількість пам'яті. Таким чином, хвостова рекурсія перестає бути чимось особливим, будучи цікавою для нас лише у випадках, коли наш компілятор не може оптимізувати звичайну рекурсію.
2. Винесення виклику функції
Компілятор винесе strlen() в окрему змінну в такому коді:
і він стане еквівалентним такому:
GCC зробить це тому, що strlen() — це вбудована функція. GCC розпізнає її та оптимізує її використання у місцях, де це потрібно. Вимкнути це можна за допомогою параметра -fno-builtin, що вказується під час компіляції.
Як і в попередньому випадку, цей прикладпоказує, як оптимізація може змінити тимчасову та просторову складність алгоритму.
3. Заміна множення на 2 на додавання (цілі числа)
У випадках із цілими числами код множення на два:
буде замінено складанням числа із самим собою:
GCC оптимізує цей код. Взагалі цей приклад — проста вправа на зниження вартості операцій. Є багато способів оптимізувати цей код: на i386 GCC використовує інструкцію add, на x86-64 - інструкцію leal, а PowerPC здійснює зсув на один розряд вліво. У будь-якому випадку виходить щось ефективніше, ніж множення на два.
А що буде з числами з плаваючою точкою?
4. Заміна множення на 2 на додавання (числа з плаваючою точкою)
Здавалося б, багато неточностей у обчисленнях з плаваючою точкою. Чи буде замінено цей код:
Ця оптимізація огорнута мороком невизначеності — можливо, вона невірна? Але ні, все вірно, GCC зробить це.
Операції з дробовими числами в розумі зручно моделювати так: спочатку ми обчислюємо точний результат, а потім округляємо його до найближчого уявного числа з плаваючою точкою. З такої точки зору, математично ця операція вірна, адже складання числа із самим собою — це те саме, що й множення на два. Проте є деякі нюанси, які ускладнюють стан речей.
По-перше, так діють лише базові операції. Більш складні функції на кшталт sin або sqrt через особливості роботи округлення можуть повертати не перше найближче число, що представляється, а друге, і то тільки в тому випадку, якщо вони написані грамотно.
Множення на 2 - також особливий випадок, адже воно вимагає лише одну операцію додавання. Звичайно, ми можемо замінити множення на кілька почергових додавань, але так у процесі буденакопичуватися проміжна помилка в точності, а точність найчастіше набагато важливіша за час роботи.
Ще один камінь спотикання - NaN. Це значення запарює багато потенційних оптимізації. Наприклад, ми можемо скоротити x-x до 0 , оскільки NaN-NaN дорівнюватиме NaN . Однак перед виконанням операції можна перевіряти, чи мають дані, що оперуються, прийнятні значення.
Мораль всього така: компілятор набагато важче оптимізувати операції з плаваючою точкою, ніж цілочисленну арифметику. І наведений приклад із множенням на два — це виняток, а не витримка з правил.
5. Заміна поділу на 2 на зсув праворуч
Код із розподілом на два:
не замінюватиметься зрушенням вправо:
Оптимізація невірна сама собою. Зрушення вправо еквівалентний поділу, яке округляється у бік негативної нескінченності, а не до нуля, як має бути. Таким чином, «оптимізований» код видаватиме неправильний результат під час оперування непарними негативними числами.
Ця проблема може бути виправлена за допомогою додавання найбільш значущого біта до чисельника, і GCC робить це.
6. Послідовність if-else проти switch
Чи застосовує GCC ті ж оптимізації до ланцюжка if-else :
що і до switch, як у варіант нижче?
GCC не робить це навіть для довгих ланцюжків if-else , принаймні давня версія 4.2.1, на якій я тестував цей код (може, версії поводяться краще в такому випадку).
switch був оптимізований в джамп-таблицю, а if-else стали лише послідовністю порівнянь.
Я був неприємно вражений цим фактом. На щастя, clang робить цю оптимізацію.
Висновок
Багато хто думає, що оптимізації — це лише зміна константи в Big-O нотації вашого коду.Тим не менш, як ми бачимо з прикладів 1 і 2, оптимізації можуть змінити асимптотику програми на краще і навіть вплинути на отриманий результат (приклад 4).
З іншого боку, деякі начебто «очевидні» оптимізації можуть погіршити ваш код, особливо якщо вони торкаються операцій з плаваючою точкою. Хоча, якщо вам не дуже важлива точність результату, ви можете розв'язати компілятор руки за допомогою параметра -ffast-math або просто внести деякі оптимізації самі.
І насамкінець: не витрачайте свій час на мікрооптимізації. Вони забирають у вас час, не набагато прискорюють код, і до того ж при їх внесенні легко припуститися помилки (як у прикладі 5).