Новые страницы- Введение
- Особенности языка C++
- Передача аргументов
- Исключения
- RTTI
- Инкремент и декремент
- Не создавайте временные объекты 1
- Не создавайте временные объекты 2
- Резервирование памяти.
- Оценивайте стоимость вызова функции в циклах for/while
- Не используйте vector там, где можно было бы обойтись list или deque
- Ссылки или указатели?
- Список инициализации конструктора
- Компиляторы
- Многопоточность
- Операционные системы
- Процессоры
Введение
Как правило, язык C++ используют там, где требуется высокая скорость работы. Но если постараться, на C++ можно написать так, что код будет работать медленнее, чем на любом другом языке. Именно подобным кодом оперируют многочисленные сравнения Any-Lang vs C++. Данные советы предназначены для того, чтобы избегать подобного кода.
Вообще оптимизация бывает трех типов:
Ускорение уже работающего кода.
Изначально написание оптимального кода.
Просто использование оптимальных конструкций
Специально заниматься ускорением написанного кода следует только после того, как проект завершен. Как правило, оптимизация потребуется только в небольшой части проекта. Поэтому сначала нужно найти места в коде, которые съедают большую часть процессорного времени. Ведь какой смысл ускорять код, пусть даже на 300%, если он съедает только 1% машинного времени? И следует помнить, что как правило, гораздо больший выигрыш в скорости дает оптимизация самих алгоритмов, а не кода.
Второй тип оптимизации – это изначальное проектирование кода с учетом требований к производительности. Такое проектирование не является ранней оптимизацией. Потому, что если изначально спроектировать приложение неправильно, потом придется смириться с низкой скоростью или переделывать.
Третий тип не совсем является оптимизацией. Скорее это избегание не оптимальных языковых конструкций. Язык C++ достаточно сложный, при его использовании частенько нужно знать, как реализован используемый код. Он достаточно низкоуровневый, чтобы программисту пришлось учитывать особенности работы процессоров и операционных систем.
Особенности языка C++
Передача аргументов
Передавайте аргументы по ссылке или по указателю, а не по значению. Передача аргументов по значению ведет к полному копированию объекта. И чем больше этот объект, тем больше придется копировать. А если объект класса выделяет память в куче, тогда совсем беда. Конечно же простые типы можно и нужно передавать по значению. Но сложные следует передавать только по ссылке или по указателю.
// Неправильно, передача по значению
void func1(std::string s) {
}
// Правильно, передача по ссылке
void func2(const std::string &s) {
}
Исключения
Используйте исключения только там, где это действительно необходимо. Дело в том, что исключения – достаточно тяжелый механизм. Поэтому не следует использовать их в качестве замены goto, выхода из вложенных циклов и тому подобных вещей. Простое правило: исключения генерируются только в исключительных ситуациях. Это не значит, что от них нужно отказывать совсем. Само использование исключений дает мизерные накладные расходы из-за небольшого количества дополнительного кода. Настоящее влияние на производительность оказывает только неправильное их использование.
RTTI
В коде, от которого требуется высокая скорость работы, не используйте RTTI. Механизм RTTI в большинстве (или во всех?) компиляторов реализован через сравнение строк. Чаще всего это не является критически важным. Но иногда от кода может потребоваться высокая скорость работы. В этом случае следует придумать другое решение.
Инкремент и декремент
Используйте префиксную форму инкремента и декремента. У разработчика на языке C++ должно войти в привычку везде использовать только префиксную форму (++i и --i) . И только в случае необходимости постфиксную форму (i++). Постфиксная форма реализована за счет сохранения и возврата временного значения объекта до его изменения. Конечно в простых случаях, в операциях со встроенными типами, компилятор сможет оптимизировать код и обойтись без создания временной переменной. Но в случае пользовательского класса, вероятно, оптимизировать не будет.
Не создавайте временные объекты 1
Временные объекты создают, к примеру, вот таким кодом:
std::string s1, s2, s3;
...
std::string s = s1 + s2 + s3;
В данном случае создается 2 лишних временных объекта: std::string tmp1 = s1 + s2; и std::string tmp2 = tmp1 + s3;. Правильная конкатернация строк выглядит вот так:
std::string s1, s2, s3;
...
std::string s = s1;
s += s2; s += s3;
Не создавайте временные объекты 2
C++ – это не C, где объявления переменных должно располагаться в самом начале. Переменную можно объявить в любом месте. И если эта переменная – сложный объект, то не следует объявлять его в местах, где он может и не понадобится. Пример:
void foo(int x)
{
int a, b, c;
std::string s; // это объявление следует расположить после return
if( x == 0 )
return;
...
}
Резервирование памяти.
Возвращаясь к предыдущему примеру, совсем правильный метод конкатернации должен быть таким:
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.
Оценивайте стоимость вызова функции в циклах 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)
Однако вот в этом случае мы получим значительное замедление:
СFile file; // Класс CFile из MFC
...
for(size_t i = 0; i < file.GetLength(); ++i)
Мало того, что функция GetLength не может быть inline, она еще и виртуальная.
Не используйте vector там, где можно было бы обойтись list или deque
Контейнер vector предназначен для хранения в памяти непрерывной последовательности байт. Поэтому при добавлении новых элементов, в случае нехватки памяти, контейнеру придется выделить новую память и копировать данные из старого места в новое. Если это происходит часто, то производительность кода может быть снижена значительно. В отличии от vector, контейнеры list или deque не хранят непрерывную последовательность данных, поэтому копирование не требуется.
С другой стороны, использование vector с предварительным резервированием (т.е. однократным выделением всей необходимой памяти) – самый быстрый и экономный способ. Потому, что в случае list или deque небольшие куски памяти выделяются много раз.
Ссылки или указатели?
Старайтесь использовать ссылки, а не указатели. Ссылки не требуют проверок. Ссылка непосредственно указывает на объект, а указатель содержит адрес, который нужно прочитать. Подробнее: разница между ссылками и указателями.
Список инициализации конструктора
Инициализируйте переменные в списке инициализации конструктора. В противном случае получается, что сначала они будут инициализированы, а потом им присваивается значение.
// Плохой код
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;
};
Компиляторы
Компилятор способен выполнять множество различных оптимизаций. Иногда ему следует помочь. Иногда наоборот, попытка оптимизировать вручную приведет к тому, что компилятор не сможет оптимизировать код так, как сделал бы это в случае отсутствия этой “помощи”.
Разворачивание циклов
Современные процессоры содержат несколько функциональных устройств (блоки 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 байт. Дополнительные условия внутри цикла, или же вычисления, влияющие на счетчик цикла, приведут к невозможности развернуть цикл.
Разворачиванием циклов компилятор занимается самостоятельно. Ему следует помочь только тем, чтобы цикл можно было развернуть. Также небольшие циклы желательно объединять в один. Но в случае наличия условий, или большого тела цикла, наоборот, бывает лучше разбить на несколько циклов, чтобы хотя-бы один из них был развернут компилятором.
Ленивость вычислений
Следует помнить, что условия && (логическое И) и || (логическое ИЛИ) компилятор обрабатывает справа налево. При вычислении логического И, если первое условие будет ложно, второе даже не будет вычисляться. Соответственно в в логическом ИЛИ при истинности первого условия нет смысла вычислять второе. Вот простой пример:
const char *s;
...
if( strlen(s) > 3 && s[0] == 'y' ) {
...
}
Нам необходима строка больше 3-х символов, чтобы первым символом был y. При этом strlen(s) дорогая операция, а s[0] == 'y' дешевая. Соответственно, если переставить их местами, то возможно вычислять длину строки и не придется:
if( s[0] == 'y' && strlen(s) > 3 ) {
...
}
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
Ключевое слово inline
Казалось бы, это ключевое слово как раз и придумано для того, чтобы ускорять программы. Но некоторые понимают это слишком буквально и начинают вставлять inline перед каждой функцией. Это приводит к тому, что код раздувается. Чем больше код, тем больше ему требуется памяти и особенно памяти в кеше процессора. Хотя современные компиляторы давно уже перестали обращать внимание на это слово и сами решают, когда стоит делать функцию встраиваемой, а когда нет. Но программисты все равно стараются заставить его раздувать код используя что-нибудь вроде __forceinline. Использовать inline следует только там, где это действительно необходимо.
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
}
}
Выравнивание структур
В объявлении классов и структур старайтесь располагать переменные по мере снижения их размера. Особенно нужно уделить вниманию группировке вместе переменных, чей размер меньше 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 - %d\n", sizeof(Foo), sizeof(Bar) );
return 0;
}
На моей машине вывод будет следующий:
$ g++ test.cpp && ./a.out
16 - 12
Тут видно, что выравнивание осуществлялось по границе 4-х байт. И совершенно одинаковые классы Foo и Bar занимают в памяти разный объем. Обычно на это можно и не обращать внимание. Но если требуется создать тысячи экземпляров класса, то вариант Bar предпочтительней. Разумеется сам компилятор не имеет права переставлять переменные местами.
Конечно же не следует рассчитывать размер каждой переменной с целью максимально плотно их упаковать. Размер переменных может зависеть от компилятора, параметров компиляции и архитектуры. Также не следует подавлять выравнивание.
Многопоточность
Важно знать, что написание многопоточного кода заключается не в расставлении в правильном месте объектов синхронизации, а в написании кода, который не требует синхронизации.
Атомарные операции
Вообще почти любое обращение к ядру, это дорогая операция. Как с памятью, так и со многими другими вызовами. Чем меньше таких обращений делает программа, тем лучше. В случае синхронизации, дополнительные накладные расходы создает необходимость переключения контекста в случае конкуренции. Поэтому, если есть большая конкуренция и синхронизация выполняется с помощью мьютекса/критической секции, накладные расходы могут быть очень большими. И чем больше конкуренция, тем больше накладные расходы. Вот пример плохого кода из довольно известных программ 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 атомарные операции, не требующие синхронизации.
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;
};
Операционные системы
Это тот уровень, на который следует спускаться только в случае хорошего понимания используемых функций. Ловушки могут поджидать в самых неожиданных местах.
Память
Старайтесь избегать частого выделения памяти. Это очень дорогая операция. И разница между “выделить 100 Мб” или “выделить 1 Мб” небольшая. Поэтому надо стараться организовать код так, чтобы заранее выделить большой объем памяти и использовать его без обращений к ядру ОС.
В случае необходимости частого выделения памяти учитывайте, что встроенный в стандартную библиотеку аллокатор не эффективен. Особенно в случае активных операций с памятью из параллельных потоков. Рассмотрите возможность использования альтернативного аллокатора вроде nedmalloc или tcmalloc или пулов памяти вроде Boost.Pool.
Буферизация ввода-вывода
Системные вызовы вроде read/write или ReadFile/WriteFile не используют буферизацию. Поэтому при чтении 1 байта, будет прочитан целый блок данных и из него отдан один единственный байт. При чтении следующего байта снова пойдет чтение этого же самого блока. Аналогично при записи, запись 1 байта приведет к немедленной записи этого байта. Это очень и очень неэффективно. Поэтому следует использовать функции, которые обеспечивают буферизацию, к примеру fread/fwrite.
Процессоры
RAM уже давно не RAM
RAM расшифровывается как Random Access Memory. Однако на сегодняшний день попытка использовать оперативную память как источник с быстрым случайным доступом не приведет ни к чему хорошему. Потому, что доступ к памяти занимает несколько сотен тактов процессора!
И единственное, что спасает – кеш процессора, доступ к которому стоит около десятка тактов (источник). Из этого следует, что надо стараться делать так, чтобы все нужные данные размещались к кеше процессора. Это не только данные программы, но и сам код. По возможности следует использовать последовательный доступ к памяти. При организации структуры вроде хеш-таблицы или ассоциативной структуры ключи не должны содержать лишней информации, чтобы максимальное их количество поместилось в кеше.
Signed или unsigned?
Чаще всего программисты не задумываются о том, должна ли переменная быть со знаком или нет. Например длинна строки, она ведь не может быть отрицательной. Также вес или цена чего-либо и многие другие значения. Вероятно, диапазона значений для знакового числа вполне хватает для хранения нужного значения, однако еще имеется разница в инструкциях процессора. К примеру вот этот код:
int func(int i) {
return i / 4;
}
будет транслирован в:
lea eax, [rdi+3]
test edi, edi
cmovns eax, edi
sar eax, 2
ret
а вот этот:
unsigned int func(unsigned int i) {
return i / 4;
}
получится значительно короче:
mov eax, edi
shr eax, 2
Типичные места, где предпочтительно использовать беззнаковые числа: деление и умножение, счетчики в циклах, индексы массивов.
Типы данных с плавающей точкой не могут быть беззнаковыми. Но для них используются специальные команды процессора.
Ветвления
Конвейер процессора потому и называется конвейером, что обрабатывает непрерывный поток команд. Процессор непрерывно поставляет команды на конвейер, чтобы после выполнения одной команды он сразу же принялся за другу. Но когда встречается ветвление, т.е. условие if … else, процессор не знает, для какой ветки следует использовать команды: для if или else? Поэтому он пытается предсказать, какая ветка будет использована. В случае ошибки в предсказании приходится сбрасывать данные конвейера и загружать в него новые команды, при этом конвейер простаивает.
Это означает, что чем раньше предсказатель переходов поймет, по какой ветке пойдет выполнение программы, тем меньше вероятности сброса конвейера. Обычно рекомендуется располагать наиболее вероятную ветку в самом начале (т.е. в условии if).
