gcc предоставляет очень простой способ производить оптимизацию:

 опция -O. Она и ускоряет выполнение вашего кода, и сжимает размер итогового кода. У неё существует пять вариантов:

#include 
int main(int argc, char *argv[])
{
int i,j,k;
unsigned long acc=0;
for(i=0;i<10000;i++)
    for(j=0;j<5000;j++)
            for(k=0;k<4;k++)
                    acc+=k;
printf("acc = %lu\n",acc);
return 0;
}

С помощью gcc, создадутся четыре разных бинарных файла, используя каждый из -O вариантов (кроме -Os). Утилита time запишет их время исполнения, таким образом:

$ time ./non-optimized

Для упрощения, будем использовать следующие обозначения:

— Non-optimized обозначает исполняемый файл, скомпилированный с опцией -O0.— OptimizedO1 обозначает исполняемый файл, скомпилированный с опцией -O1.— OptimizedO2 обозначает исполняемый файл, скомпилированный с опцией -O2.— OptimizedO3 обозначает исполняемый файл, скомпилированный с опцией -O3.

Как вы могли заметить, время выполнения программы, скомпилированной с -O1 в семь раз меньше, чем время выполнения программы, при компиляции которой не использовалась оптимизация. Обратите внимание, что нет большой разницы между -O1, -O2 и -O3, — на самом деле, они почти одинаковы. Так в чем же магия -O1?

После беглого изучения исходного кода, вы должны отметить, что такой код конечен для оптимизации. Прежде всего, давайте посмотрим на короткое сравнение дизассемблированных версий non-optimized и optimizedO1:

$ objdump -D non-optimized
$ objdump -D optimizedO1

(Примечание: вы можете получить другие результаты, поэтому используйте эти как основные)

Приведенные примеры реализуют самый вложенный цикл (for (k=0;k<4;k++)). Обратите внимание на различие: неоптимизированный код напрямую загружает и хранит из адреса памяти, в то время как optimized01 использует регистры ЦПУ в качестве сумматора и счетчик цикла. Как вам, возможно, известно, доступ к регистрам может быть получен в сотни или тысячи раз быстрее, чем к ячейкам ОЗУ.Не удовлетворяясь простым использованием регистров ЦПУ, gcc использует другой трюк оптимизации. Давайте снова посмотрим дизассемблированный код optimizedO1 и обратим внимание на функцию main():

......
08048390 :
...
80483a1:       b9 00 00 00 00          mov    $0x0,%ecx
80483a6:       eb 1f                   jmp    80483c7 
80483a8:       81 c1 30 75 00 00       add    $0x7530,%ecx

0x7530 это 30000 в десятичной форме, поэтому мы можем быстро угадать цикл. Этот код представляет собой самый вложенный и самый внешний циклы (for(j=0;j<5000;j++) ... for(k=0;k<4;k++)), так как они являются буквальным запросом на 30000 проходов. Примите во внимание, что вам нужно всего лишь три прохода внутри. Когда k=0, acc остается прежним, поэтому первый проход можно проигнорировать.

   80483ae:       81 f9 00 a3 e1 11       cmp    $0x11e1a300,%ecx
80483b4:       74 1a                   je     80483d0 
80483b6:       eb 0f                   jmp    80483c7 

Хмм, теперь это соответствует 300 000 000 (10 000*5 000*6). Представлены все три цикла. После достижения этого числа проходов, мы переходим прямо к printf() для вывода суммы (адреса 0x80483d0 - 0x80483db).

   80483b8:       83 c2 06                add    $0x6,%edx
80483bb:       83 c0 01                add    $0x1,%eax
80483be:       3d 88 13 00 00          cmp    $0x1388,%eax
80483c3:       74 e3                   je     80483a8
80483c5:       eb f1                   jmp    80483b8 

Шесть добавляется в сумматор при каждой итерации. В итоге, %edx будет содержать всю сумму после выполнения всех трех циклов. Третья и четвертая строки показывают нам, что после выполнения 5000 раз, должен быть переход к адресу 0x80483a8 (как указано ранее).

Мы можем заключить, что gcc создает здесь упрощение. Вместо прохода три раза в самый вложенный цикл, он просто добавляет шесть для каждого среднего цикла. Это звучит просто, но это заставляет вашу программу сделать только 100 000 000 проходов вместо 300 000 000. Это упрощение, называемое разворачиванием цикла, одно из тех задач, которые делают -O1/2/3. Конечно же, вы и сами можете это сделать, но иногда неплохо знать, что gcc может определить такие вещи и оптимизировать их.

С опциями -O2 и -O3 gcc тоже пытается произвести оптимизацию. Обычно она достигается посредством переупорядочивания [5] и трансформацией кода. Целью этой процедуры является устранить столько ошибочных ветвей, сколько возможно, что повышает качество использования конвейера. Например, мы можем сравнить, как non-optimized и optimizedO2 выполняет самый внешний цикл.

 80483d4:       83 45 ec 01             addl   $0x1,0xffffffec(%ebp)
80483d8:       81 7d ec 0f 27 00 00    cmpl   $0x270f,0xffffffec(%ebp)
80483df:       7e c4                   jle    80483a5

Бинарный файл non-optimized использует jle для выполнения перехода. Математически это означает, что вероятность выбора ветви 50%. С другой стороны, версия optimizedO2 использует следующее:

80483b4:       81 c1 30 75 00 00       add    $0x7530,%ecx
80483ba:       81 f9 00 a3 e1 11       cmp    $0x11e1a300,%ecx
80483c0:       75 e1                   jne    80483a3

Теперь, вместо jle используется jne. При условии, что любое целое может быть сопоставлено в предыдущем cmp, нетрудно сделать вывод, что это увеличит шанс выбора ветви почти до 100%. Это небольшое, но полезное указание процессору для определения того, какой код должен быть выполнен. Хотя, для большинства современных процессоров, этот вид трансформации не является ужасно необходимым, так как предсказатель переходов достаточно умен для того, чтобы сделать это сам.

Для доказательства того, как сильно это изменение может помощь, к нам на помощь придет OProfile. Oprofile выполнен для записи числа изолированных ветвей и изолированных ошибочных ветвей. Изолированные здесь обозначает «выполненные внутри конвейера данных ЦПУ»

$ opcontrol --event=RETIRED_BRANCHES_MISPREDICTED:1000 --event=RETIRED_BRANCHES:1000;

Мы запустим non-optimized и optimizedO2 пять раз каждый. Затем мы возьмем максимум и минимум примеров. Мы посчитаем степень ошибки, используя эту формулу (выведена отсюда).

Степень ошибки = изолированные ошибочные ветви / изолированные ветви

Теперь вычислим степень ошибки для каждого бинарного файла. Для non-optimized получилось 0,5117%, в то время как optimizedO2 получил 0,4323% — в нашем случае, выгода очень мала. Фактическая выгода может различаться для реальных случаев, так как gcc сам по себе не может много сделать без внешних указаний. Пожалуйста, прочтите о __builtin_expect() в документации по gcc для подробной информации.