Статьи Основы низкоуровневой оптимизации

Discussion in 'Статьи' started by herfleisch, 27 Jul 2010.

  1. herfleisch

    herfleisch Elder - Старейшина

    Joined:
    7 Jan 2009
    Messages:
    577
    Likes Received:
    174
    Reputations:
    13
    Мне очень запомнилось высказывание Михаила Флёнова в одной из его книг: «Если Вы написали программу, то Вы программист. Но если Ваша программа лучше других, то Вы хакер. Оптимизация — один из способов сделать программу максимально быстрой, эффективной и выделяющейся на фоне остальных».

    Так оно и есть. Очень приятно, когда сложная и многофункциональная программа буквально «летает», и хочется убить программиста, когда его небольшая утилита «тормозит» по любому поводу.

    Первым делом я всегда осуществляю оптимизацию алгоритма. На мой взгляд, именно от алгоритма зависит весь жизненный цикл программы. После оптимизации алгоритма можно попробовать улучшить отдельные функции, небольшие связанные между собой части программы, поиграться с параметрами. Но в конце-концов наступает момент, когда всё кажется вылизанным до последней мелочи и можно считать, что программа оптимизирована. Однако, если Вы используете один из языков высокого уровня, то есть ещё один шаг — низкоуровневая оптимизация.

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

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

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

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

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

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

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

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

    Code:
    int main()
    {
    for (int i=0; i<10; i++);
    return 0;
    }
    Казалось бы, код — проще некуда, и оптимизировать в нём совершенно нечего. Но давайте сохраним его в файле test.cpp и переведём его в код на ассемблере:

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

    Code:
    .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» реализуется не совсем так, как хотелось бы. Если быть точнее, то не очень хорошо выбрано место для хранения переменной-счётчика:

    Code:
    movl	$0, -4(%rbp)
    jmp	.L2
    .L3:
    addl	$1, -4(%rbp)
    .L2:
    cmpl	$9, -4(%rbp)
    …
    jne	.L3
    Что тут не так? А то, что значение переменной i хранится в оперативной памяти, доступ к которой производится не так быстро, как к регистрам процессора. В данном случае необязательно править код на ассемблере. Достаточно объявить переменную i как регистровую:

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

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

    Code:
    .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
    Лично меня не устраивает строчка:

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

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

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

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

    Code:
    movl	$10, %ecx
    .L:	/*
    *	Тело цикла
    */
    dec	$ecx	 /*	операция декремента (уменьшения на единицу)	*/
    cmp	%ecx, 0	/*	(%ecx == 0) ???	*/
    jne	.L	 /*	если (%ecx != 0) то jmp L	*/
    Инструкция loop заменяет собой три последних строки: декремент, сравнение и условный переход. Как вы, наверное, уже догадались, работает loop быстрее, чем эти три инструкции. Выглядит использование этого оператора так:

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

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

    Code:
    .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++

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

    Code:
    void sum(int a, int b, int *c) { }
    int main() {
    int a = 5, b = 4, c;
    sum(a, b, &c);
    }
    В данном случае мы преднамеренно не определили алгоритм функции sum(…), чтобы реализовать его непосредственно на ассемблере. Функция sum(…) должна складывать первые два аргумента и записывать результат в третий аргумент. Запустим g++ с ключом -S и получим листинг:

    Code:
    .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 — указатель). Это делается для поддержки возможности перегрузки функций.

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

    Code:
    /* Значение первого параметра перемещаем в %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++ или других языках. Кроме того, может возникнуть ситуация, когда Вам будет необходимо обойти запреты ООП или операционной системы. Команды процессора «прорвут» инкапсуляцию, даже не подозревая о её существовании. Экспериментируйте с ассемблерными вставками и вы узнаете о своём компиляторе массу новой и полезной информации.

    И не слушайте умников, которые говорят что ассемблер умер и никому не нужен.

    Большое спасибо за внимание. Статья взята из моего личного блога http://www.perechnev.com/.
     
    #1 herfleisch, 27 Jul 2010
    Last edited: 24 Nov 2012
Loading...
Similar Threads - Основы низкоуровневой оптимизации
  1. Дикс
    Replies:
    0
    Views:
    7,669
  2. Dosia
    Replies:
    29
    Views:
    68,368
  3. Mozy

    Авторские статьи Основы работы компьютера

    Replies:
    30
    Views:
    16,135
  4. Troop
    Replies:
    6
    Views:
    9,968