Немного размышлений и советов по оптимизации кода на С++

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

Как правило, язык C++ используют там, где требуется высокая скорость работы. Но на C++ без особых усилий можно получить код, работающий медленнее какого-нибудь Python/Ruby. Именно подобным кодом оперируют многочисленные сравнения Any-Lang vs C++.

Вообще, оптимизация бывает трех типов:

1. Оптимизация уже готового, проверенного и работающего кода.
2. Изначально написание оптимального кода.
3. Просто использование оптимальных конструкций.

Специально заниматься оптимизацией готового кода следует только после того, как проект закончен и используется. Как правило, оптимизация потребуется только в небольшой части проекта. Поэтому сначала нужно найти места в коде, которые съедают большую часть процессорного времени. Ведь какой смысл ускорять код, пусть даже на 500%, если он отнимает только 1% машинного времени? И следует помнить, что, как правило, гораздо больший выигрыш в скорости дает оптимизация самих алгоритмов, а не кода. Именно про данный ее вид говорят: «преждевременная оптимизация — зло» (с).

Второй тип оптимизации — это изначальное проектирование кода с учетом требований к производительности. Такое проектирование не является ранней оптимизацией.

Третий тип даже не совсем оптимизация. Скорее это избегание неоптимальных языковых конструкций. Язык C++ довольно сложный, при его использовании частенько нужно знать, как реализован используемый код. Он достаточно низкоуровневый, чтобы программисту пришлось учитывать особенности работы процессоров и операционных систем.

1. Особенности языка C++

1.1. Передача аргументов

Передавайте аргументы по ссылке или по указателю, а не по значению. Передача аргументов по значению ведет к полному копированию объекта. И чем больше этот объект, тем больше придется копировать. А если объект класса выделяет память в куче, тогда совсем беда. Конечно же, простые типы можно и нужно передавать по значению. Но сложные следует передавать только по ссылке или по указателю.

// Неправильно, передача по значению
void func1(std::string s) {
}

// Правильно, передача по ссылке
void func2(const std::string &s) {
}

1.2. Исключения

Используйте исключения только там, где это действительно необходимо. Дело в том, что исключения — достаточно тяжелый механизм. Поэтому не следует использовать их в качестве замены goto, выхода из вложенных циклов и тому подобных вещей. Простое правило: исключения генерируются только в исключительных ситуациях. Это не значит, что от них нужно отказаться совсем. Само использование исключений дает мизерные накладные расходы из-за небольшого количества дополнительного кода. Настоящее влияние на производительность оказывает только неправильное их использование.

1.3. RTTI

В коде, от которого требуется высокая скорость работы, не используйте RTTI. Механизм RTTI в большинстве компиляторов (или во всех?) реализован через сравнение строк. Чаще всего это не критически важно. Но иногда от кода может потребоваться высокая скорость работы. В этом случае следует придумать другое решение, например числовые идентификаторы классов.

1.4. Инкремент и декремент

Используйте префиксную форму инкремента и декремента. У разработчика на языке C++ должно войти в привычку везде использовать только префиксную форму (++i и --i) и лишь при необходимости постфиксную форму (i++). Постфиксная форма реализована за счет сохранения и возврата временного значения объекта до его изменения. Конечно, в простых случаях, в операциях со встроенными типами, компилятор сможет оптимизировать код и обойтись без создания временной переменной. Но в случае пользовательского класса, вероятно, оптимизировать не будет.

1.5. Не создавайте временные объекты — 1

Временные объекты создают, к примеру, вот таким кодом:

std::string s1, s2, s3;
...
std::string s = s1 + s2 + s3;

В данном случае создается два лишних временных объекта: std::string tmp1 = s1 + s2; и std::string tmp2 = tmp1 + s3;. Правильная конкатенация строк выглядит вот так:

std::string s1, s2, s3;
...
std::string s = s1;

s += s2;
s += s3;

1.6. Не создавайте временные объекты — 2

C++ — это не C, где объявление переменных должно располагаться в самом начале. Переменную можно объявить в любом месте. И если эта переменная — сложный объект, то не следует объявлять его в местах, где он может и не понадобиться. Пример:

void foo(int x)
{
    int a, b, c;
    std::string s; // Это объявление следует расположить после return

    if( x == 0 )
        return;
    ...
}

1.7. Резервирование памяти

Возвращаясь к предыдущему примеру (п. 1.5) — совсем правильный метод конкатенации должен быть таким:

std::string s1, s2, s3;
...
std::string s;

s.reserve( s1.size() + s2.size() + s3.size() );
s += s1;
s += s2;
s += s3;

Операция выделения памяти очень дорогая. И, предварительно выделив ее один раз вызовом reserve, можно сэкономить много процессорного времени. В случае STL это относится к классам vector и string.

1.8. Вообще избегайте лишней работы

Мне казалось, этот совет есть в любой книге для начинающего, да и базового понимания C++ должно хватать, чтобы понять… Однако вижу, что некоторые неопытные программисты на это натыкаются.

std::string s = ""; // 1
s = ""; // 2

В строке 1 вызывается конструктор std::string(const char *), который не знает о том, что строка пустая. Он будет пытаться выяснить ее длину, выполнить выделение памяти и цикл копирования, иметь обработчик нехватки памяти и т. д. Это дороже, чем просто

std::string s; // Создается пустая строка

В строке 2 та же самая ситуация. Выполняется operator = (const char *s), который также не знает о том, что «программист» всего лишь хотел получить пустую строку. Эффективней будет простой вызов:

s.clear(); // Очистка строки

1.9. Оценивайте стоимость вызова функции в циклах for/while

Используя STL, можно не беспокоиться о том, что вызов функции дорог:

std::vector<int> vec;
...
for(size_t i = 0; i < vec.size(); ++i) {
    ...
}

Потому что в данном случае он дешев. Это будет эквивалентно следующему коду:

size_t size = vec.size();
for(size_t i = 0; i < size; ++i)

Однако это не всегда так. Частое заблуждение до C++11 было в том, что программисты ожидали такой же алгоритмической сложности от std::list::size, хотя во множестве реализаций его сложность была O(N). Особенно неприятно это смотрелось там, где вместо вызова if( list.empty() ) выполняли if( list.size() > 0 ).

1.10. Не используйте vector там, где можно было бы обойтись list или deque

Контейнер vector предназначен для хранения в памяти непрерывной последовательности байтов. Поэтому при добавлении новых элементов, если памяти не хватит, контейнеру придется выделить новую память и копировать данные из старого места в новое. Если это происходит часто, то производительность кода может быть снижена значительно. В отличие от vector, контейнеры list или deque не хранят непрерывную последовательность данных, поэтому копирование не требуется.

С другой стороны, использование vector с предварительным резервированием (т. е. однократным выделением всей необходимой памяти) — самый быстрый и экономный способ. Потому что в случае list или deque небольшие куски памяти выделяются много раз. При выборе контейнера следует думать, какие именно операции над ним будут выполняться.

1.11. Ссылки или указатели?

Старайтесь использовать ссылки, а не указатели. Ссылки не требуют проверок. Ссылка непосредственно указывает на объект, а указатель содержит адрес, который нужно прочитать.

1.12. Список инициализации конструктора

Инициализируйте переменные в списке инициализации конструктора. В противном случае получается, что сначала они будут инициализированы, а потом им присваивается значение.

// Плохой код
class Foo {
    public:
        Foo() {
            a = 0;        // Переменная a уже была инициализирована
            s = "string"; // И эта переменная тоже
        }

    private:
        int a;
        std::string s;
};

// Хороший код
class Foo {
    public:
        Foo() : a(0), s("string")  // Вот теперь правильно
        {}

    private:
        int a;
        std::string s;
};

2. Компиляторы

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

2.1. Разворачивание циклов

Современные процессоры содержат несколько функциональных устройств (блоки ALU и FPU) и способны выполнять команды параллельно, т. е. за один такт на одном ядре может быть выполнено несколько команд. Поэтому разворачивание цикла позволяет выполнить операцию за меньшее число шагов. Также разворачивание уменьшает количество сравнений и условных переходов:

for(int i = 0; i < len; ++i) {
    sum += s[i];
}

Должно быть развернуто во что-то вроде

switch(len) {
    case 3:
        sum += s[2];
    case 2:
        sum += s[1];
    case 1:
        sum += s[0];
        break;
    case 0:
        break;
    default:
        for(int i = 0; i < len; i += 4) {
            sum += s[i];
            sum += s[i + 1];
            sum += s[i + 2];
            sum += s[i + 3];
        }
}

Вот часть ассемблерного кода, без switch:

.L5:
        movsx   rdi, BYTE PTR [rbx+rax]
        movsx   rdx, BYTE PTR [rbx+1+rax]
        movsx   r11, BYTE PTR [rbx+2+rax]
        movsx   r10, BYTE PTR [rbx+3+rax]
        movsx   r9, BYTE PTR [rbx+4+rax]
        movsx   r8, BYTE PTR [rbx+5+rax]
        add     rsi, rdi
        movsx   rdi, BYTE PTR [rbx+6+rax]
        add     rsi, rdx
        movsx   rdx, BYTE PTR [rbx+7+rax]
        add     rax, 8
        add     rsi, r11
        add     rsi, r10
        add     rsi, r9
        add     rsi, r8
        add     rsi, rdi
        add     rsi, rdx
        cmp     rax, rcx
        jne     .L5

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

Разворачиванием циклов компилятор занимается самостоятельно. Ему следует помочь только тем, чтобы это можно было сделать. Также небольшие циклы желательно объединять в один. Но при наличии условий или большого тела цикла, наоборот, бывает лучше разбить на несколько циклов, чтобы хотя бы один из них был развернут компилятором.

2.2. Ленивость вычислений — 1

Следует помнить, что условия && (логическое И) и || (логическое ИЛИ) компилятор обрабатывает слева направо. При вычислении логического И, если первое условие ложно, второе даже не будет вычисляться. Соответственно, в логическом ИЛИ при истинности первого условия нет смысла вычислять второе. Вот простой пример:

const char *s;
...

if( strlen(s) > 3 && s[0] == 'y' ) {
    ...
}

Нам необходима строка больше трех символов, чтобы первым символом был y. При этом strlen(s) — дорогая операция, а s[0] == 'y' — дешевая. Соответственно, если поменять их местами, то, возможно, вычислять длину строки и не придется:

if( s[0] == 'y' && strlen(s) > 3 ) {
    ...
}

2.3. Ленивость вычислений — 2

Ленивость вычислений работает только до тех пор, пока вы не перегрузили оператор && или ||. Перегруженный оператор представляет из себя вызов функции:

bool operator && (аргумент1, аргумент2)

Следовательно, все аргументы должны быть вычислены до вызова.

2.4. Switch или if?

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

int func(int i)
{
    if(i == 1 )
        return 10;
    else if( i == 2 )
        return 20;
    else if( i == 3 )
        return 30;
    else if( i == 4 )
        return 40;
    else if( i == 5 )
        return 50;
    return 100;
}

транслируется в

cmp     edi, 1
mov     eax, 10
je      .L2
cmp     edi, 2
mov     al, 20
je      .L2
cmp     edi, 3
mov     al, 30
je      .L2
cmp     edi, 4
mov     al, 40
je      .L2
mov     al, 50
cmp     edi, 5
mov     edx, 100
cmovne  eax, edx

А вот такой код:

int func(int i)
{   
    switch(i) {
        case 1:
            return 10;
            break;
        case 2:
            return 20;
            break;
        case 3:
            return 30;
            break;
        case 4:
            return 40;
            break;
        case 5:
            return 50;
            break;
        default:
            return 100;
    }
}

транслируется в

dec     edi
mov     eax, 100
cmp     edi, 4
ja      .L10
mov     eax, DWORD PTR CSWTCH.1[0+rdi*4]

CSWTCH.1:
        .long   10
        .long   20
        .long   30
        .long   40
        .long   50

2.5. Ключевое слово inline

Казалось бы, это ключевое слово как раз и придумано для того, чтобы ускорять программы. Но некоторые понимают это слишком буквально и начинают вставлять inline перед каждой функцией. Это приводит к тому, что код раздувается. Чем больше код, тем больше ему требуется памяти, и особенно памяти в кеше процессора. Современные компиляторы давно уже перестали обращать внимание на это слово и сами решают, когда стоит делать функцию встраиваемой, а когда нет. Но программисты все равно стараются раздуть код, вставляя что-нибудь вроде __forceinline. Использовать inline следует только там, где это действительно необходимо.

2.6. RVO — Return Value Optimization

Эта оптимизация позволяет компилятору C++ не создавать копию возвращаемого значения. Следует помочь компилятору использовать эту оптимизацию.

// Плохой код
std::string foo() {
    std::string s = "string";
    return s; // Компилятор не может использовать RVO 
}

// Хороший код
std::string foo() {
    return std::string("string"); // Компилятор может использовать RVO
}

Поэтому одна точка выхода хоть и красивее, но менее эффективна:

std::string bar(...)
{
    std::string result;

    if( x ) {
        result = foo();
    }

    return result; // Одна точка выхода, но RVO не задействована
}

std::string bar(...)
{
    if( x ) {
        return foo();  // Компилятор будет использовать RVO
    }
    else {
        return std::string(); // Компилятор будет использовать RVO
    }
}

Этот совет почти потерял актуальность, так как компиляторы научились хорошо использовать NRVO, к тому же появилась возможность перемещения. Однако не всегда NRVO может быть задействована, и не у всех объектов есть конструктор перемещения.

2.7. Выравнивание структур

В объявлении классов и структур старайтесь располагать переменные по убыванию их размера. Особенно нужно уделить внимание группировке вместе переменных, чей размер меньше 8 байт. Компиляторы, в целях оптимизации, выравнивают адреса переменных, потому что обращение к переменной с типом long по выровненному адресу занимает всего один такт процессора, а если переменная не выровнена, то два такта на архитектуре i386. На некоторых архитектурах читать по невыровненному адресу вообще нельзя. Грубо говоря, невыровненная переменная располагается в нескольких ячейках памяти: первая часть в одной и часть в следующей. Так вот, благодаря этому выравниванию переменная размером 1 байт займет 4 или 8 байт. Вот иллюстрирующий пример:

#include <stdio.h>

class Foo {
    int a;
    char b;
    int c;
    char d;
};

class Bar {
    int a;
    int c;
    char b;
    char d;
};

int main() 
{
    printf( "%d - %dn", sizeof(Foo), sizeof(Bar) );

    return 0;
}

На моей машине вывод будет следующий:

$ g++ test.cpp && ./a.out
16 - 12

Тут видно, что выравнивание велось по границе четырех байт. И совершенно одинаковые классы Foo и Bar занимают в памяти разный объем. Обычно на это можно и не обращать внимания. Но если требуется создать тысячи экземпляров класса, то вариант Bar предпочтительней. Разумеется, сам компилятор не имеет права переставлять переменные.

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

3. Многопоточность

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

3.1. Атомарные операции

Вообще, почти любое обращение к ядру — это дорогая операция. Как с памятью, так и со многими другими вызовами. Чем меньше таких обращений делает программа, тем лучше. В случае синхронизации дополнительные накладные расходы создает необходимость переключать контекст при конкуренции. Поэтому, если есть большая конкуренция и синхронизация выполняется с помощью мьютекса / критической секции, накладные расходы могут быть очень серьезными. И чем больше конкуренция, тем они значительнее. Вот пример плохого кода из довольно известных программ (на момент написания статьи) LinuxDC++/StrongDC++ и, вероятно, других подобных программ, основанных на одном и том же коде:

static long safeInc(volatile long& v) {
    pthread_mutex_lock(&mtx);
    long ret = ++v;
    pthread_mutex_unlock(&mtx);
    return ret;
}

static long safeDec(volatile long& v) {
    pthread_mutex_lock(&mtx);
    long ret = --v;
    pthread_mutex_unlock(&mtx);
    return ret;
}

static long safeExchange(volatile long& target, long value) {
    pthread_mutex_lock(&mtx);
    long ret = target;
    target = value;
    pthread_mutex_unlock(&mtx);
    return ret;
}

Этот код компилируется для сборки под ОС Linux. При этом для Windows код правильный:

static long safeInc(volatile long& v) { return InterlockedIncrement(&v); }
static long safeDec(volatile long& v) { return InterlockedDecrement(&v); }
static long safeExchange(volatile long& target, long value) { return InterlockedExchange(&target, value); }

Разница в том, что для Linux используются критические секции, а для Windows — атомарные операции, не требующие тяжелых мьютексов.

3.2. Cache Line

Старайтесь не допускать обращений разных потоков к близко расположенным участкам памяти. К примеру, имеется вот такая структура:

struct Shared {
    int a;
    int b;
    int c;
};

и потоки, обращающиеся к одной из переменных. Если потоки будут выполняться на разных ядрах, то произойдет событие, называемое Cache line ping-pong: когда двум разным ядрам необходимо видеть изменения друг друга и для этого приходится сбрасывать кеш и запрашивать данные из оперативной памяти. В подобных случаях, когда потокам требуются разделяемые данные, надо вставить между переменными кусок памяти, который поместится в Cache-Line процессора. Сложность в том, что размер этого Cache-Line у каждого процессора свой. Я ориентируюсь на значение 128 байт:

struct Shared {
    int a;
    char pad1[128];
    int b;
    char pad2[128];
    int c;
};

4. Операционные системы

Это тот уровень, на который следует спускаться, только если хорошо понимаешь используемые функции. Ловушки могут подстерегать в самых неожиданных местах.

4.1. Память

Старайтесь избегать частого выделения памяти. Это очень дорогая операция. И разница между «выделить 100 Мб» и «выделить 1 Мб» небольшая. Поэтому надо стараться организовать код так, чтобы заранее выделить большой объем памяти и использовать его без обращений к ядру ОС.

Если необходимо часто выделять память, учитывайте, что встроенный в стандартную библиотеку аллокатор неэффективен, особенно в случае активных операций с памятью из параллельных потоков. Рассмотрите возможность использования альтернативного аллокатора вроде nedmalloc или TCMalloc или пулов памяти вроде Boost.Pool.

4.2. Буферизация ввода-вывода

Системные вызовы вроде read/write или ReadFile/WriteFile не используют буферизацию. Поэтому при чтении одного байта будет прочитан целый блок данных и из него отдан один-единственный байт. При чтении следующего байта снова пойдет чтение этого же самого блока. Аналогично при записи: запись одного байта приведет к немедленной записи этого байта. Это очень и очень неэффективно. Поэтому следует использовать функции, которые обеспечивают буферизацию, к примеру fread/fwrite.

5. Процессоры

5.1. RAM уже давно не RAM

RAM расшифровывается как Random Access Memory. Однако на сегодняшний день попытка использовать оперативную память как источник с быстрым случайным доступом не приведет ни к чему хорошему. Потому что доступ к памяти занимает несколько сотен тактов процессора!

И единственное, что спасает, — кеш процессора, доступ к которому стоит около десятка тактов (источник). Из этого следует, что надо стараться делать так, чтобы все нужные данные размещались в кеше процессора. Это не только данные программы, но и сам код. По возможности нужно использовать последовательный доступ к памяти. При организации структуры вроде хеш-таблицы или ассоциативной структуры ключи не должны содержать лишней информации, чтобы максимальное их количество поместилось в кеше.

5.2. Signed или unsigned?

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

int func(int i) {
    return i / 4;
}

будет транслирован в

lea         eax, [rdi+3]
test        edi, edi
cmovns      eax, edi
sar         eax, 2

А вот этот:

unsigned int func(unsigned int i) {
    return i / 4;
}

получится значительно короче:

mov     eax, edi
shr     eax, 2

Типичные места, где предпочтительно использовать беззнаковые числа: деление и умножение, счетчики в циклах, индексы массивов.

Типы данных с плавающей точкой не могут быть беззнаковыми. Но для них используются специальные команды процессора.

5.3. Ветвления

Конвейер процессора потому и называется конвейером, что обрабатывает непрерывный поток команд. Процессор безостановочно поставляет команды на конвейер, чтобы после выполнения одной команды он сразу же принялся за другую. Но когда встречается ветвление, т. е. условие if … else, процессор не знает, для какой ветки следует использовать команды — для if или else. Поэтому он пытается предсказать, какая из них будет использована. В случае ошибки в предсказании приходится сбрасывать данные конвейера и загружать в него новые команды, при этом конвейер простаивает.

Это означает, что чем раньше предсказатель переходов поймет, по какой ветке пойдет выполнение программы, тем меньше вероятность сброса конвейера. Обычно рекомендуется располагать наиболее вероятную ветку в самом начале (т. е. в условии if).

6. Заключение

Итак, в этой статье мы рассмотрели некоторые способы оптимизации кода на С++. Надеюсь, какие-то из них оказались вам полезны. Если вы знаете другие способы, не упомянутые в статье, пишите их в комментариях!

И напоследок еще два совета:

1. Предпочитайте готовые решения. Они уже проверены, не надо тратить время на их поддержку и доработку, они будут развиваться и исправляться силами других людей. Изобретение велосипедов очень хорошо для саморазвития, но очень плохо для коллективной разработки.
2. Больше думайте о том, как сделать простой и понятный код, а не быстрый. Простота кода гораздо важнее.

Автор: Mail.Ru Group

Источник