Linux.by

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

В этой книге есть глава, рассказывающая о том, какие оптимизации делает компилятор с кодом. Правда, рассматриваются всего три компилятора: 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 (восьми!) переходов. И что самое интересное, все перечисленные в книге компиляторы это делали. Вот что значит - прогресс!

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

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

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

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

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

"На машинах и софте общего применения процессорное время стоит существенно дешевле времени суппорта нечитабельного кода" (ц) какие-то патриархи

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

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

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

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

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

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

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

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

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

Речь же шла именно об "оптимизированном но менее понятном" коде.

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

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

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

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

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

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