RDot: White Hat Security Community

RDot: White Hat Security Community (https://rdot.org/forum/index.php)
-   Статьи/Articles (https://rdot.org/forum/forumdisplay.php?f=10)
-   -   [Кодинг] Основы низкоуровневой оптимизации (https://rdot.org/forum/showthread.php?t=2886)

b30v3r 13.10.2013 09:02

[Кодинг] Основы низкоуровневой оптимизации
 
Примеры, описанные в статье, носят исключительно академический характер.

Всем привет.

Хотелось бы рассказать об основах этого нелегкого, но интереснейшего занятия. В качестве рабочего инструмента я буду использовать язык программирования C++, а конкретнее — компилятор g++. Так как само название «низкоуровневой оптимизации» говорит нам о том, что работать мы будем на уровне языка ассемблера, то стоит заметить, что я использую ОС GNU/Linux, а значит мы будем иметь дело не стандартным синтаксисом INTEL, а с синтаксисом AT&T, немного отличающимся от привычного нам кода, например, в MASM или TASM. Перед константными выражениями в соответствии с правилами синтаксиса AT&T мы будем ставить знак $, перед именами регистров – %, а в командах пересылки на первое место ставится источник, на второе — назначение (в синтаксисе INTEL всё как раз наоборот).

Синтаксис AT&T может показаться совершенно непонятным на первый взгляд, а, может быть, даже неуклюжим и глупым. Но лично я считаю его более удобным и совершенным: логичнее указывать источник первее, чем назначение, а обозначение регистров со знаком % и констант со знаком $ в конце-концов делает код более читабельным и простым для восприятия.

Кроме того, стоит заметить, что так же я использую архитектуру x86_64, а значит, если Вы работаете в 32-разрядной операционной системе, то в некоторых моментах код для Вашей платформы может немного отличаться от моего.

На этом закончим вступительную часть и приступим непосредственно к теме статьи.

Общая информация

Код на C++ будет переведён компилятором в машинные команды, а значит, скорее всего, может быть переведён в код на языке Assembler. Так оно и есть. Для этого укажите компилятору опцию -S:

Код:

g++ test.cpp -S
и он создаст в текущем каталоге файл test.s, содержащий конвертированный код.

Чем нам может быть полезен код на ассемблере? А тем, что компилятор реализует инструкции «общим случаем», т.е. таким образом, чтобы они работали всегда. Отсюда и идёт некоторая потеря производительности: то тут лишняя инструкция влезла, тот там ещё лишние пять. Давайте сразу рассмотрим пример:

Код:

int main()
{
for (int i=0; i<10; i++);
return 0;
}

Казалось бы, код — проще некуда, и оптимизировать в нём совершенно нечего. Но давайте сохраним его в файле test.cpp и переведём его в код на ассемблере:

Код:

g++ test.cpp -S
Получится файл примерно следующего содержания:

Код:

.file        «test.cpp»
.text
.globl main
.type        main, @function
main:
.LFB0:
.cfi_startproc
.cfi_personality 0×3,__gxx_personality_v0
pushq        %rbp
.cfi_def_cfa_offset 16
movq        %rsp, %rbp
.cfi_offset 6, -16
.cfi_def_cfa_register 6
movl        $0, -4(%rbp)
jmp        .L2
.L3:
addl        $1, -4(%rbp)
.L2:
cmpl        $9, -4(%rbp)
setle        %al
testb        %al, %al
jne        .L3
movl        $0, %eax
leave
ret
.cfi_endproc
.LFE0:
.size        main, .-main
.ident        «GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3″
.section        .note.GNU-stack,»",@progbits

Как вы, наверное, заметили (а скорее всего не заметили =)), цикл «for» реализуется не совсем так, как хотелось бы. Если быть точнее, то не очень хорошо выбрано место для хранения переменной-счётчика:

Код:

movl        $0, -4(%rbp)
jmp        .L2
.L3:
addl        $1, -4(%rbp)
.L2:
cmpl        $9, -4(%rbp)

jne        .L3

Что тут не так? А то, что значение переменной i хранится в оперативной памяти, доступ к которой производится не так быстро, как к регистрам процессора. В данном случае необязательно править код на ассемблере. Достаточно объявить переменную i как регистровую:

Код:

for (register int i=0; i<10; i++);
и мы получим asm-листинг, в котором i хранится не в ячейке памяти, а в регистре ebx, работа с которым производится быстрее, чем с ячейкой ОЗУ.

Вот, собственно, мы и сделали первый шаг, используя метод низкоуровневой оптимизации и имеем следующий код:

Код:

.file        «test.cpp»
.text
.globl main
.type        main, @function
main:
.LFB0:
.cfi_startproc
.cfi_personality 0×3,__gxx_personality_v0
pushq        %rbp
.cfi_def_cfa_offset 16
movq        %rsp, %rbp
.cfi_offset 6, -16
.cfi_def_cfa_register 6
pushq        %rbx
movl        $0, %ebx
.cfi_offset 3, -24
jmp        .L2
.L3:
addl        $1, %ebx
.L2:
cmpl        $9, %ebx
setle        %al
testb        %al, %al
jne        .L3
movl        $0, %eax
popq        %rbx
leave
ret
.cfi_endproc
.LFE0:
.size        main, .-main
.ident        «GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3″
.section        .note.GNU-stack,»",@progbits

Лично меня не устраивает строчка:

Код:

addl        $1, %ebx
Зачем использовать команду сложения для того, чтобы прибавить единицу? Ведь намного рациональнее будет использовать операцию инкремента (увеличения на единицу):

Код:

inc        %ebx
По-идее, да. Использовать операцию инкремента было бы рациональнее, но мы поступим другим образом.

Достаточно вспомнить про инструкцию loop, используемую специально для циклов со счётчиком типа for.

Немного напомню о принципе работы loop для тех, кто о нём забыл и тех, кто о нём даже не подозревал. Все циклы со счётчиком имеют следующую конструкцию:

Код:

movl        $10, %ecx
.L:        /*
*        Тело цикла
*/
dec        $ecx        /*        операция декремента (уменьшения на единицу)        */
cmp        %ecx, 0        /*        (%ecx == 0) ???        */
jne        .L        /*        если (%ecx != 0) то jmp L        */

Инструкция loop заменяет собой три последних строки: декремент, сравнение и условный переход. Как вы, наверное, уже догадались, работает loop быстрее, чем эти три инструкции. Выглядит использование этого оператора так:

Код:

mov        $10, %ecx
.L:        /*
*        Тело цикла
*/
loop .L

Попрошу заметить, что переменная-счётчик должна находиться в регистре %ecx! Так же, учитывайте то, что туда надо заносить именно количество необходимых проходов цикла! Никаких «плюс/минус единиц», как в C/C++!

Учитывая всё вышесказанное, оптимизируем код нашей программы так:

Код:

.file        «test.cpp»
.text
.globl main
.type        main, @function
main:
.LFB0:
.cfi_startproc
.cfi_personality 0×3,__gxx_personality_v0
pushq        %rbp
.cfi_def_cfa_offset 16
movq        %rsp, %rbp
.cfi_offset 6, -16
.cfi_def_cfa_register 6
pushq        %rbx
movl        $10, %ecx
.cfi_offset 3, -24
.L2:
/*
*        Тело цикла
*/
loop        .L2
movl        $0, %eax
popq        %rbx
leave
ret
.cfi_endproc
.LFE0:
.size        main, .-main
.ident        «GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3″
.section        .note.GNU-stack,»",@progbits

Как и обещалось, код, полученный в самом начале нашей статьи существенно оптимизировался. И это не смотря на то, что наша С-программа состояла всего лишь из одной строки! Я имею ввиду ту самую строку, которая несёт смысловую нагрузку в нашем демонстрационном примере =)

Asm-функции на основе шаблонов C++

Конечно, оптимизация отдельно взятых кусков кода — это большой плюс к производительности. Но Вы можете самостоятельно реализовать на ассемблере целые функции (процедуры). Рассмотрим пример:

Код:

void sum(int a, int b, int *c) { }
int main() {
int a = 5, b = 4, c;
sum(a, b, &c);
}

В данном случае мы преднамеренно не определили алгоритм функции sum(…), чтобы реализовать его непосредственно на ассемблере. Функция sum(…) должна складывать первые два аргумента и записывать результат в третий аргумент. Запустим g++ с ключом -S и получим листинг:

Код:

.file        «test.cpp»
.text
.globl _Z3sumiiPi
.type        _Z3sumiiPi, @function
_Z3sumiiPi:
.LFB0:
.cfi_startproc
.cfi_personality 0×3,__gxx_personality_v0
pushq        %rbp
.cfi_def_cfa_offset 16
movq        %rsp, %rbp
.cfi_offset 6, -16
.cfi_def_cfa_register 6
movl        %edi, -4(%rbp)
movl        %esi, -8(%rbp)
movq        %rdx, -16(%rbp)
leave
ret
.cfi_endproc
.LFE0:
.size        _Z3sumiiPi, .-_Z3sumiiPi
.globl main
.type        main, @function
main:
.LFB1:
.cfi_startproc
.cfi_personality 0×3,__gxx_personality_v0
pushq        %rbp
.cfi_def_cfa_offset 16
movq        %rsp, %rbp
.cfi_offset 6, -16
.cfi_def_cfa_register 6
subq        $16, %rsp
movl        $5, -4(%rbp)
movl        $4, -8(%rbp)
leaq        -12(%rbp), %rdx
movl        -8(%rbp), %ecx
movl        -4(%rbp), %eax
movl        %ecx, %esi
movl        %eax, %edi
call        _Z3sumiiPi
movl        $0, %eax
leave
ret
.cfi_endproc
.LFE1:
.size        main, .-main
.ident        «GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3″
.section        .note.GNU-stack,»",@progbits

По метке _Z3sumiiPi: находится функция sum(). Почему имя функции записано так искажённо? Здесь sum это имя функции, а iiPi — список аргументов: int, int, * int (последний происходит от pointer — указатель). Это делается для поддержки возможности перегрузки функций.

Реализация алгоритма функции на языке ассемблера выглядит так:

Код:

/* Значение первого параметра перемещаем в %eax */
movl        -8(%rbp), %eax
/* Значение второго параметра перемещаем в %edx */
movl        -4(%rbp), %edx
/* Складываем %eax и %edx */
addl        %eax, %edx
/* Перемещаем адрес, указанный в третьем параметре, в %rax */
movq        -16(%rbp), %rax
/* Записываем сумму в ячейку, с адресом, указанным в %rax */
movl        %edx, (%rax)

Для того, чтобы функция заработала, вышеприведённый код следует вставить непосредственно перед инструкцией leave.

Теперь немного о параметрах. Компиляторы, например от Microsoft или Borland, передают параметры в функцию через стек таким образом, что первым туда попадает крайний правый параметр, а последним — крайний левый. Возвращает же значение функция через регистр ax (для 16-битных компиляторов, для других — через соответствующие регистры).

В случае компилятора g++ вопрос передачи параметров решается немного по-другому. Попробуйте сами сгенерировать код, содержащий передачу параметров функции в количестве от одного до десяти, и посмотреть как это делается. Уверяю Вас, это действительно интересно!

Вообще говоря, изучайте свою систему, свой компилятор. Потому что даже разные версии одного и того же компилятора могут генерировать разный код.

Заключение

На этом я, пожалуй, закончу. Надеюсь, мне удалось показать вам основы низкоуровневой оптимизации в той мере, которая необходима для понимания данного метода. Использование возможностей ассемблера при программировании на языках высокого уровня даёт вашей программе не только прирост в скорости и эффективности. Вы так же можете выполнять аппаратно-зависимые функции, недоступные в C/C++ или других языках. Кроме того, может возникнуть ситуация, когда Вам будет необходимо обойти запреты ООП или операционной системы. Команды процессора «прорвут» инкапсуляцию, даже не подозревая о её существовании. Экспериментируйте с ассемблерными вставками и вы узнаете о своём компиляторе массу новой и полезной информации.

HeartLESS 14.10.2013 08:47

Хм, а есть готовые решения для оптимизации по мелочам?
Я хочу сказать, что вряд ли программисты в серьезных проектах будут рады видеть ассемблерные вставки среди фабрик фабрик фабрик. А вот если бы в коде был декоратор @{Оптимизируй это}, то было бы гораздо удобнее же.
PS: Декоратор, а не глобальный оптимизатор, так как проще компилятору сказать, что эта переменная нужна только для цикла, чем обучать его, что надо оптимизировать, а что - нет.

SynQ 14.10.2013 10:29

Можно оптимизировать отдельные функции:
Цитата:

int function() __attribute__((optimize("-O3")));


Часовой пояс GMT +3, время: 06:27.

Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd. Перевод: zCarot