Наглядная демонстрация качества машинной оптимизации
Разговор о качестве машинной оптимизации был бы неполным без конкретных примеров. Показатели производительности – слишком абстрактные величины. Они дают пищу для размышлений, но не объясняют: почему откомпилированный код оказался хуже. Как говорится, пока не увижу своими глазами, пока не пощупаю своими руками – не поверю!
Что ж, такая возможность у нас есть! Давайте изучим непосредственно сам ассемблерный код, сгенерированный компилятором. Для экономии бумажного пространства ниже приведен лишь один пример – результат компиляции программы пузырьковой сортировки компилятором MicrosoftVisual C++. Пример довольно показательный, ибо ощутимо улучшить его качество, не вывихнув при этом себе мозги, практически невозможно. Да вы смотрите сами. Если не владеете ассемблером – не расстраивайтесь, в листинге присутствуют подробные комментарии (надеюсь, вы понимаете, что их вставил не компилятор?).
.text:004013E0 ; ---------- S U B
R
O
U
T
I
N
E
----------
.text:004013E0
.text:004013E0
.text:004013E0 с_sort proc near ; CODE XREF: sub_401420+DAp
.text:004013E0
.text:004013E0 arg_0 = dword ptr 8
.text:004013E0 arg_4 = dword ptr 0Ch
.text:004013E0
.text:004013E0 push ebx
.text:004013E0 ; сохраняем регистр EBX, т.к. функция обязана сохранять
.text:004013E0 ; модифицируемые регистры, иначе программа рухнет
.text:004013E0 ;
.text:004013E1 mov ebx, [esp+arg_4]
.text:004013E1 ; загружаем в ebx самый правый аргумент – количество элементов
.text:004013E1 ; точно так поступил бы и человек
.text:004013E1 ; ага, локальные переменные адресуются непосредственно через ESP
.text:004013E1 ; это экономит один регистр (EBP), высвобождая его для других нужд
.text:004013E1 ; человек так не умеет… вернее, не то, что бы совсем не умеет,
.text:004013E1 ; но адресация через ESP
заставляет заново вычислять
.text:004013E1 ; местоположение локальных переменных при всяком перемещении
.text:004013E1 ; верхушки стека (в частности при передаче функции аргументов),
.text:004013E1 ; что ну очень утомительно…
.text:004013E1 ;
.text:004013E5 push ebp
.text:004013E6 push esi
.text:004013E6 ; сохраняем еще два регистра
.text:004013E6 ; вообще-то, человек мог воспользоваться и командой PUSHA,
.text:004013E6 ; сохраняющей все регистры общего назначения, что было бы
.text:004013E6 ; намного короче, но в то же время, увеличило бы потребности
.text:004013E6 ; программы в стековом пространстве и несколько снизило бы
.text:004013E6 ; ее скорость
.text:004013E6 ;
.text:004013E7 cmp ebx, 2
.text:004013E7 ; сравниваем значение аргумента n
с константой 2
.text:004013E7 ;
.text:004013EA push edi
.text:004013EB jl short loc_40141B
.text:004013EB ; а вот здесь пошла оптимизация кода под ранние процессоры P-P MMX
.text:004013EB ; сравнение содержимого EBX
и анализ результата сравнения разделен
.text:004013EB ; командой сохранения регистра EDI. Дело в том, что P-P MMX
.text:004013EB ; могли спаривать команды, если они имели зависимость по данным
.text:004013EB ; впрочем, в данном конкретном случае такая оптимизация излишня
.text:004013EB ; т.к. процессор пытается предсказать направление перехода еще до
.text:004013EB ; его реального исполнения. Впрочем, перестановка команд –
.text:004013EB ; карман не тянет и никому не мешает
.text:004013EB ;
.text:004013ED mov ebp, [esp+0Ch+arg_0]
.text:004013ED ; загружаем в EBP значение кране левого аргумента –
.text:004013ED ; указателя на сортируемый массив. Как уже сказано, так
.text:004013ED ; адресовать аргументы умеют только компиляторы,
.text:004013ED ; человеку это не под силу
.text:004013ED ;
.text:004013F1
.text:004013F1 loc_4013F1: ; CODE XREF: C_Sort+39j
.text:004013F1 ; цикл начинается с нечетного адреса. Плохо!
.text:004013F1 ; это весьма пагубно сказывается на производительность
.text:004013F1 ;
.text:004013F1 xor esi, esi
.text:004013F1 ; очищаем регистр ESI, выполняя логического XOR
над ним самим
.text:004013F1 ; вот на это человек – способен!
.text:004013F1 ;
.text:004013F3 cmp ebx, 1
.text:004013F6 jle short loc_40141B
.text:004013F6 ; эти две команды лишние.
.text:004013F6 ; Для человека очевидно, если EBX
>= 2, то он всегда больше одного
.text:004013F6 ; А вот для компилятора это – вовсе не факт! (Ну темный он)
.text:004013F6 ; Дело в том, что он превратил возрастающий цикл for
.text:004013F6 ; в убывающий цикл do/while с пост условием
.text:004013F6 ; /* убывающие циклы с постусловием реализуются на
.text:004013F6 ; х86-процессорах намного более эффективно */
.text:004013F6 ; но для этого компилятор должен быть уверен, что цикл
.text:004013F6 ; исполняется хотя бы раз – вот он и помещает
.text:004013F6 ; в код дополнительную и абсолютно лишнюю в данном случае
.text:004013F6 ; проверку. Впрочем, она не отнимает много времени
.text:004013F6 ;
.text:004013F8 lea eax, [ebp+4]
.text:004013F8 ; быстрое сложить EBP
с 4 и записать результат в EAX
.text:004013F8 ; об этом трюке знают далеко не все программисты,
.text:004013F8 ; и обычно выполняют данную задачу в два этапа
.text:004013F8 ; MOV EAX, EBX\ADD EAX, 4
.text:004013F8 ;
.text:004013FB lea edi, [ebx-1]
.text:004013FB ; быстро вычесть из EBX
единицу и записать результат в EDI
.text:004013FB ;
.text:004013FE
.text:004013FE loc_4013FE: ; CODE XREF: C_Sort+35j
.text:004013FE mov ecx, [eax-4]
.text:004013FE ; Оп
с! Команда, расположенная в начале цикла пересекает
.text:004013FE ; границу 0x10 байт, что приводит к ощутимым задержка исполнения
.text:004013FE ; Да, забыл сказать, эта инструкция загружает ячейку src[a-1]
.text:004013FE ; в регистр ECX
.text:004013FE ;
.text:00401401 mov edx, [eax]
.text:00401401 ; загружаем ячейку src[a] в регистр EDX
.text:00401401 ;
.text:00401403 cmp ecx, edx
.text:00401403 ; сравниваем ECX (src[a-1]) и
EDX (src[a])
.text:00401403 ; вообще-то, это можно было реализовать и короче
.text:00401403 ; CMP ECX, [EAX], избавлюсь от команды MOV EDX, [EAX]
.text:00401403 ; однако, это ни к чему, т.к. значение [EAX] нам потребуется ниже
.text:00401403 ; при обмене переменными и эта команда все равно бы вылезла там.
.text:00401403 ;
.text:00401405 jle short loc_401411
.text:00401405 ; переход на ветку loc_401411, если ECX
<= EDX
.text:00401405 ; в противном случае – выполнить обмен ячеек
.text:00401405 ;
.text:00401407 mov [eax-4], edx
.text:0040140A mov [eax], ecx
.text:0040140A ; обмен
ячейками. Вообще-то, можно было бы реализовать это и
.text:0040140A ; через XCHG, что было бы на несколько байт короче, но у этой
.text:0040140A ; инструкции свои проблемы – не на всех процессорах она работает
.text:0040140A ; быстрее…
.text:0040140A ;
.text:0040140C mov esi, 1
.text:0040140C ; устанавливаем ESI (флаг f) в
.text:0040140C ; человек мог бы сократить это на несколько байт, записав это так:
.text:0040140C ; MOV ESI, ECX. Поскольку ECX
> EDX, то ECX
!=0,
.text:0040140C ; при условии, конечно, что EDX
>= 0.
.text:0040140C ; разумеется, компиляторам такое не по зубам, однако, это
.text:0040140C ; алгоритмическая оптимизация и к качеству кодогенерации она
.text:0040140C ; не имеет никакого отношения
.text:0040140C ;
.text:00401411 loc_401411: ; CODE XREF: C_Sort+25j
.text:00401411 add eax, 4
.text:00401411 ; увеличиваем EAX (a) на
4 (sizeof(int))
.text:00401411 ;
.text:00401414 dec edi
.text:00401414 ; уменьшаем счетчик цикла на единицу
.text:00401414 ; (напоминаю, компилятор превратил наш for
в убывающий цикл)
.text:00401414 ;
.text:00401415 jnz short loc_4013FE
.text:00401415 ; переход к началу цикла, пока EDI
не равен нулю
.text:00401415 ; некоторые человеки здесь лепят LOOP, который хоть и компактнее
.text:00401415 ; но исполняется значительно медленнее
.text:00401415 ;
.text:00401417 test esi, esi
.text:00401417 ; проверка флага f на равенство нулю
.text:00401417 ;
.text:00401419 jnz short loc_4013F1
.text:00401419 ; повторять цикл, пока f
равен нулю
.text:0040141B
.text:0040141B loc_40141B:
.text:0040141B pop edi
.text:0040141C pop esi
.text:0040141D pop ebp
.text:0040141E pop ebx
.text:0040141E ; восстанавливаем все измененные регистры
.text:0040141E ;
.text:0040141F retn
.text:0040141F ; выходим из функции
.text:0040141F C_Sort endp
.text:0040141F
Итак, какие у противников компиляторов есть претензии к качеству кода? Смогли бы они реализовать эту же процедуру хотя бы процентов на десять эффективнее? Согласитесь, здесь есть чему поучиться даже весьма квалифицированным программистам!
