Какие оптимизации делает GCC?

Все о программировании под *nix
Аватара пользователя
Victor Gr.
Неотъемлемая часть форума
Сообщения: 891
Зарегистрирован: 13 авг 2004, 15:39
Откуда: Минск
Контактная информация:

Какие оптимизации делает GCC?

Сообщение Victor Gr. »

Читаю книжку Криса Касперского "Техника оптимизации программ: Эффективное использование памяти". Книжка потрясающая! Всем, кто не читал - рекомендую! Очень подробный и интересный рассказ об устройстве памяти (оперативной и кэш), а так же техника оптимизации программ на языках высокого уровня (т.е. без применения ассемблера).

В этой книге есть глава, рассказывающая о том, какие оптимизации делает компилятор с кодом. Правда, рассматриваются всего три компилятора: MS Visual C++ 6, Borland C++ 5 и WATCOM C++ 10.

В лидеры вышел MS Visual C++, по приведенным параметрам, он и правда обошёл остальные компиляторы. Но, хочется рассмотреть ещё и gcc. Какие приёмы предкопиляционной оптимизации он использует?

В книге рассматривались следующие приёмы:

Размножение констант
Свертка констант
Вычисление константных выражений
Свёртка функций
Удаление неиспользуемых переменных
Удаление неиспользуемых присвоений
Удаление копий переменных
Удаление лишних присвоений
Удаление лишних вызовов функий
Выполнение алгебраических упрощений
Оптимизация подвыражений
Замена деления сдвигом
Замена деления умножением
Замена оператора взятия остатка битовыми операциями
Быстрое вычисление остатка
Замена умножения сдвигом
Замена умножения сложением
Использование LEA для быстрого сложения (умножения, вычитания)
Замена условных переходов арифметическими операциями
Удаление лишних условий
Удаление заведомо ложных условий
Балансировка дерева case-переховод
Создание таблицы переходов
Разворот циклов
Слияние циклов
Вынос инвариантного кода за пределы цикла
Замена циклов с предусловием на циклы с постусловием
Замена возрастающих циклов на убывающие циклы
Удаление ветвлений из цикла
Учет частоты использования переменных при помещении их в регистр
Передача аргументов в регистрах по умолчанию
Количество регистров, выделенных для передачи аргументов функции
Адресация локальных переменных через ESP
Оптимизация инициализации константных строк
Удаление "мертвого" кода
Оптимимзация константных условий

Конечно, каждый из них подробно расписан и приведены примеры, так что, если кому-то будет интересно - могу переписать из книги описание приёма.

Для чего это надо? Вовсе не для сравнений Visual C++ vs. GCC, а для себя. Т.е. нужно ли самому вручную писать оптимизированный, но менее понятный код, или довериться компилятору?

Признаюсь, настоящим откровением для меня стала оптимизация switch-case-переходов. Если просматривать такое дерево "влоб", то это будет просто последовательный перебор значений и в худшем случае, переборов будет ровно столько, сколько пунктов в switch.

А с помощью балансировки такого дерева можно сократить его до 8 (восьми!) переходов. И что самое интересное, все перечисленные в книге компиляторы это делали. Вот что значит - прогресс!

Аватара пользователя
Silos
Неотъемлемая часть форума
Сообщения: 287
Зарегистрирован: 15 фев 2004, 19:04
Откуда: Belarus, Minsk
Контактная информация:

Сообщение Silos »

Victor Gr., както читал я linux gazette и наткнулся я на статью одного товарища. В этой статье был рассказ о оптимизациях которые делает gcc. Пять или четыре приводилось там и вроде были ссылки на доки по теме.
Поищи, может подойдет.

Аватара пользователя
Victor Gr.
Неотъемлемая часть форума
Сообщения: 891
Зарегистрирован: 13 авг 2004, 15:39
Откуда: Минск
Контактная информация:

Сообщение Victor Gr. »

Silos, на русском или на языке оригинала?

Поищу конечно! Большое спасибо!

Аватара пользователя
sanitar
Неотъемлемая часть форума
Сообщения: 1116
Зарегистрирован: 28 ноя 2002, 02:23
Откуда: Минск

Сообщение sanitar »

"Т.е. нужно ли самому вручную писать оптимизированный, но менее понятный код"

Карамба!
Триста раз нет, независимо от компилятора.
За исключением случаев, когда ты программируешь жестко ограниченные в ресурсах системы, или там ОС реального времени и т.п.

"На машинах и софте общего применения процессорное время стоит существенно дешевле времени суппорта нечитабельного кода" (ц) какие-то патриархи
I'll kill this code without a knife -- with only fork().

Аватара пользователя
Victor Gr.
Неотъемлемая часть форума
Сообщения: 891
Зарегистрирован: 13 авг 2004, 15:39
Откуда: Минск
Контактная информация:

Сообщение Victor Gr. »

sanitar, интересное мнение!

Но, ведь мало кто будет спорить, что

$b = 2;
$c = 3;
$d = 16;

for ($i=0; $i<10000; $i++)
{
$result = $i * ($b/$c+sqrt($d));
print $result;
}

Следует изначально писать оптимизированным? Хотя, хороший компилятор (у в gcc я не сомневаюсь) сам исправит подобную оплошность.

Аватара пользователя
Silos
Неотъемлемая часть форума
Сообщения: 287
Зарегистрирован: 15 фев 2004, 19:04
Откуда: Belarus, Minsk
Контактная информация:

Сообщение Silos »

Victor Gr. писал(а):Silos, на русском или на языке оригинала?

Поищу конечно! Большое спасибо!
Есть перевод на русский. И ссылки на англоязычные ресурсы.

Аватара пользователя
sanitar
Неотъемлемая часть форума
Сообщения: 1116
Зарегистрирован: 28 ноя 2002, 02:23
Откуда: Минск

Сообщение sanitar »

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

Речь же шла именно об "оптимизированном но менее понятном" коде.
I'll kill this code without a knife -- with only fork().

Аватара пользователя
soko1
Интересующийся
Сообщения: 40
Зарегистрирован: 03 сен 2004, 20:22
Откуда: Менск
Контактная информация:

Сообщение soko1 »

Оптимизация (которую проделывает GCC), насколько я понимаю выглядет так:
программер пишет:
char mass[] = {'b', 's', 'd'};
а компилятор это переводит в:
mass[0] = 'b';
mass[1] = 's';
mass[2] = 'd';
ну это конечно самый простой пример.

Аватара пользователя
Victor Gr.
Неотъемлемая часть форума
Сообщения: 891
Зарегистрирован: 13 авг 2004, 15:39
Откуда: Минск
Контактная информация:

Сообщение Victor Gr. »

sokol, это правда очень простой пример).

Вобщем-то, компилятору пофиг как записан массив. Всё-равно он его определяет.

Гораздо более интересным является замена деления умножением:

a / b = 2^N / b * a / 2^N, где N - разрядность числа.

Аватара пользователя
soko1
Интересующийся
Сообщения: 40
Зарегистрирован: 03 сен 2004, 20:22
Откуда: Менск
Контактная информация:

Сообщение soko1 »

это и в правду интересно.

Ответить