Эту статью я написал достаточно давно для своего блога, который теперь заброшен. Мне кажется, в ней есть весьма полезная информация, поэтому не хотелось бы, чтобы она просто исчезла. Очень может быть, что-то уже устарело, буду благодарен, если мне на это укажут.
Как правило, язык C++ используют там, где требуется высокая скорость работы. Но на C++ без особых усилий можно получить код, работающий медленнее какого-нибудь Python/Ruby. Именно подобным кодом оперируют многочисленные сравнения Any-Lang vs C++.
Вообще, оптимизация бывает трех типов:
- Оптимизация уже готового, проверенного и работающего кода.
- Изначально написание оптимального кода.
- Просто использование оптимальных конструкций.
Специально заниматься оптимизацией готового кода следует только после того, как проект закончен и используется. Как правило, оптимизация потребуется только в небольшой части проекта. Поэтому сначала нужно найти места в коде, которые съедают большую часть процессорного времени. Ведь какой смысл ускорять код, пусть даже на 500%, если он отнимает только 1% машинного времени? И следует помнить, что, как правило, гораздо больший выигрыш в скорости дает оптимизация самих алгоритмов, а не кода. Именно про данный ее вид говорят: «преждевременная оптимизация — зло» (с).
Второй тип оптимизации — это изначальное проектирование кода с учетом требований к производительности. Такое проектирование не является ранней оптимизацией.
Третий тип даже не совсем оптимизация. Скорее это избегание неоптимальных языковых конструкций. Язык C++ довольно сложный, при его использовании частенько нужно знать, как реализован используемый код. Он достаточно низкоуровневый, чтобы программисту пришлось учитывать особенности работы процессоров и операционных систем.
1. Особенности языка C++
1.1. Передача аргументов
Передавайте аргументы по ссылке или по указателю, а не по значению. Передача аргументов по значению ведет к полному копированию объекта. И чем больше этот объект, тем больше придется копировать. А если объект класса выделяет память в куче, тогда совсем беда. Конечно же, простые типы можно и нужно передавать по значению. Но сложные следует передавать только по ссылке или по указателю.
// Неправильно, передача по значению
void func1(Foo foo) {
}
// Правильно, передача по ссылке
void func2(const Foo &foo) {
}
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
Переменную можно объявить в любом месте. И если эта переменная — сложный объект, то не следует объявлять его в местах, где он может и не понадобиться. Пример:
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];
}
Должно быть развернуто во что-то вроде
if( len >= 4 ) {
for(; i < len - 3; i += 4) {
sum += s[i];
sum += s[i + 1];
sum += s[i + 2];
sum += s[i + 3];
}
}
switch(len % 4) {
case 3:
sum += s[i + 2];
case 2:
sum += s[i + 1];
case 1:
sum += s[i];
break;
}
Вот часть ассемблерного кода, без
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 && 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 - %d\n", 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. Заключение
Итак, в этой статье мы рассмотрели некоторые способы оптимизации кода на С++. Надеюсь, какие-то из них оказались вам полезны. Если вы знаете другие способы, не упомянутые в статье, пишите их в комментариях!
И напоследок еще два совета:
- Предпочитайте готовые решения. Они уже проверены, не надо тратить время на их поддержку и доработку, они будут развиваться и исправляться силами других людей. Изобретение велосипедов очень хорошо для саморазвития, но очень плохо для коллективной разработки.
- Больше думайте о том, как сделать простой и понятный код, а не быстрый. Простота кода гораздо важнее.
Комментарии (79)
bobermaniac
17.03.2016 12:26Я не очень понял насчет RVO. Есть же rvalue reference и move semantics?
nekipelov
17.03.2016 12:33Поэтому я отметил: "Этот совет почти потерял актуальность" :-)
Есть move semantics, но пока не у всех классов есть конструктор перемещения, чтобы компилятор мог это задействовать.
JIghtuse
17.03.2016 14:39+4Как это бывает, новая фича не решает всех проблем. Move semantics не заменяет RVO полностью. В Effective Modern C++ есть об этом отрывок:
Item 25In other words, they figure that given a function returning a local variable by value, such as this,
Widget makeWidget() // "Copying" version of makeWidget { Widget w; // local variable ... // configure w return w; // "copy" w into return value }
they can “optimize” it by turning the “copy” into a move:
Widget makeWidget() // Moving version of makeWidget { Widget w; ... return std::move(w); // move w into return value } // (don't do this!)
My liberal use of quotation marks should tip you off that this line of reasoning is flawed. But why is it flawed?
It’s flawed, because the Standardization Committee is way ahead of such program?mers when it comes to this kind of optimization. It was recognized long ago that the “copying” version of makeWidget can avoid the need to copy the local variable w by constructing it in the memory alloted for the function’s return value. This is known as the return value optimization (RVO), and it’s been expressly blessed by the C++ Standard for as long as there’s been one.
Wording such a blessing is finicky business, because you want to permit such copy elision only in places where it won’t affect the observable behavior of the software. Paraphrasing the legalistic (arguably toxic) prose of the Standard, this particular blessing says that compilers may elide the copying (or moving) of a local object3 in a function that returns by value if (1) the type of the local object is the same as that returned by the function and (2) the local object is what’s being returned. With that in mind, look again at the “copying” version of makeWidget:
Widget makeWidget() // "Copying" version of makeWidget { Widget w; ... return w; // "copy" w into return value }
3 Eligible local objects include most local variables (such as w inside makeWidget) as well as temporary objects created as part of a return statement. Function parameters don’t qualify. Some people draw a distinction between application of the RVO to named and unnamed (i.e., temporary) local objects, limiting the term RVO to unnamed objects and calling its application to named objects the named return value optimization (NRVO).
Both conditions are fulfilled here, and you can trust me when I tell you that for this code, every decent C++ compiler will employ the RVO to avoid copying w. That means that the “copying” version of makeWidget doesn’t, in fact, copy anything. The moving version of makeWidget does just what its name says it does (assuming Widget offers a move constructor): it moves the contents of w into makeWidget’s return value location. But why don’t compilers use the RVO to eliminate the move, again constructing w in the memory alloted for the function’s return value? The answer is simple: they can’t. Condition (2) stipulates that the RVO may be performed only if what’s being returned is a local object, but that’s not what the moving version of makeWidget is doing. Look again at its return statement:
return std::move(w);
What’s being returned here isn’t the local object w, it’s a reference to w—the result ofstd::move(w). Returning a reference to a local object doesn’t satisfy the conditions required for the RVO, so compilers must move w into the function’s return value location. Developers trying to help their compilers optimize by applyingstd::moveto a local variable that’s being returned are actually limiting the optimization options available to their compilers!
But the RVO is an optimization. Compilers aren’t required to elide copy and move operations, even when they’re permitted to. Maybe you’re paranoid, and you worry that your compilers will punish you with copy operations, just because they can. Or perhaps you’re insightful enough to recognize that there are cases where the RVO is difficult for compilers to implement, e.g., when different control paths in a function return different local variables. (Compilers would have to generate code to construct the appropriate local variable in the memory allotted for the function’s return value, but how could compilers determine which local variable would be appropriate?) If so, you might be willing to pay the price of a move as insurance against the cost of a copy. That is, you might still think it’s reasonable to apply std::move to a local object you’re returning, simply because you’d rest easy knowing you’d never pay for a copy.
In that case, applying std::move to a local object would still be a bad idea. The part of the Standard blessing the RVO goes on to say that if the conditions for the RVO are met, but compilers choose not to perform copy elision, the object being returned must be treated as an rvalue. In effect, the Standard requires that when the RVO is permitted, either copy elision takes place or std::move is implicitly applied to local objects being returned. So in the “copying” version of makeWidget,
Widget makeWidget() // as before { Widget w; ... return w; }
compilers must either elide the copying of w or they must treat the function as if it were written like this:
Widget makeWidget() { Widget w; ... return std::move(w); // treat w as rvalue, because // no copy elision was performed }
The situation is similar for by-value function parameters. They’re not eligible for copy elision with respect to their function’s return value, but compilers must treat them as rvalues if they’re returned. As a result, if your source code looks like this,
Widget makeWidget(Widget w) // by-value parameter of same { // type as function's return ... return w; }
compilers must treat it as if it had been written this way:
Widget makeWidget(Widget w) { ... return std::move(w); // treat w as rvalue }
This means that if you use std::move on a local object being returned from a function that’s returning by value, you can’t help your compilers (they have to treat the local object as an rvalue if they don’t perform copy elision), but you can certainly hinder them (by precluding the RVO). There are situations where applying std::move to a local variable can be a reasonable thing to do (i.e., when you’re passing it to a function and you know you won’t be using the variable any longer), but as part of a return statement that would otherwise qualify for the RVO or that returns a by-value parameter isn’t among them.
khdavid
18.03.2016 12:58Краткое содержание item25:
RVO эффективнее move семантики, так как в первом случае переменная аллоцируется уже нужном месте и не копируется, а во втором случае отрабатывает move constructor.
Zealint
17.03.2016 13:03+5Основные советы Вы действительно перечислили и почти всегда их хватает для обычной разработки типичных IT-задач. Есть ещё книга Скотта Майерса "Эффективное использование C++. 55 верных способов улучшить структуру и код ваших программ", в которой эти вещи, помимо прочего, тоже раскрыты.
Однако последние два совета о том, что нужно предпочитать готовые решения и стремиться к простоте кода следовало бы дать с пояснением, что это не всегда и не везде так. В соседней статье я дал комментарий (довольно длинный), в котором перечислил ряд причин, когда необходимо изобретать велосипед, более того, в этих случаях вредно предпочитать готовые решения.
А совет о простоте кода не всегда выполним. Бывают задачи, в которых сделать код простым просто нельзя. Он в принципе сложен, потому что сложен сам алгоритм и его понимание требует хорошей математической подготовки. Например, алгоритм Шёнхаге — Штрассена для перемножения длинных чисел. В исходниках GMP можно посмотреть и убедиться, что сделать его проще можно лишь в ущерб производительности, что для данной библиотеки недопустимо. Кто знает математику, лежащую в основе алгоритма, тот разберётся в этом коде, а кто не знает, один фиг, просто или сложно, всё китайская грамота.
Короче говоря, нужно учитывать область работы программиста, когда даются такие советы. В остальном согласен.
izvolov
17.03.2016 13:10-10Вы поклонник Григория Остера?
Какой-то сборник вредных советов и заблуждений.VioletGiraffe
17.03.2016 15:28-2+1. После п.1 желание читать дальше пропало, т. к. с оптимизациями компилятора автор незнаком.
EvilBeaver
17.03.2016 16:50+4Ну если уж набросили, так дайте конкретику — в чем вред, где заблуждение?
А так получается ляпнул и пошел дальше. А что сказать хотел — неизвестно.
crazylammer
17.03.2016 13:15+20Не используйте vector там, где можно было бы обойтись list или deque
Не согласен — используйте vector, пока профайлер не скажет обратного. "Discontinuous data structures are the root of all (performance) evil": https://youtu.be/fHNmRkzxHWs?t=35m
Вкратце — доступ к кэшам процессора на 1-2 порядка быстрее, чем доступ к оперативке, данные из оперативки попадают в кэши непрерывными кусками, а данные в std::list раскиданы по памяти => любые чтения из list будут крайне затратными.
Я бы использовал list, только если количество вставок/удалений в середину на порядки больше, чем количество чтений из него, или если программируешь для нестандартного железа.
Gorthauer87
17.03.2016 15:55А если уж вектор будет постоянно расти, то там шаг выделения памяти при реалокации достаточно большой, чтобы в конце концов свести их на нет. Правда, говорят, раньше его делали в районе 1,5.
gcc
17.03.2016 13:19+5Используйте префиксную форму инкремента и декремента
Однажды в книге Game Engine Architecture я наткнулся на следующий абзац:
Notice in the above example that we are using C++’s postincrement operator,
p++, rather than the preincrement operator, ++p. This is a subtle but sometimes
important optimization. The preincrement operator increments the contents
of the variable before its (now modified) value is used in the expression.
The postincrement operator increments the contents of the variable after it has
been used. This means that writing ++p introduces a data dependency into your
code—the CPU must wait for the increment operation to be completed before
its value can be used in the expression. On a deeply pipelined CPU, this introduces
a stall. On the other hand, with p++ there is no data dependency. The
value of the variable can be used immediately, and the increment operation
can happen later or in parallel with its use. Either way, no stall is introduced
into the pipeline.
Of course, within the “update” expression of a for loop (for(init_expr;
test_expr; update_expr) {… }), there should be no difference between
pre- and postincrement. This is because any good compiler will recognize that
the value of the variable isn’t used in update_expr. But in cases where the
value is used, postincrement is superior because it doesn’t introduce a stall
in the CPU’s pipeline. Therefore, it’s good to get in the habit of always using
postincrement, unless you absolutely need the semantics of preincrement.
Т.е. совет — делать с точностью да наоборот. Не указано, к каким процессорам это применимо, поэтому исхожу из предположения, что к большинству современных, в т.ч. на PC и игровых консолях. Что на этот счёт скажете?Amomum
17.03.2016 16:13Я бы сказал, что не надо у своих классов перегружать операторы инкремента. Я вообще не знаю, как это оправдать можно.
А для примитивных типов вроде бы безразлично.gcc
17.03.2016 16:22Речь о примитивных типах. В контексте перегруженных операторов вообще трудно рассуждать о подобных оптимизациях.
nekipelov
17.03.2016 16:19Скажу, что мой совет относился к стандартным итераторам, в которых хранятся "большие" объекты. В случае чего-нибудь вроде int очень даже допустимо, что все будет с точностью наоборот, правильное замечание.
burjui
17.03.2016 16:20Этот абзац относится только типам данных, помещающимся в регистр. Если p не влезает в регистр, то не получится распараллелить чтение и запись, т.к. распараллеливание идёт на уровне инструкций, а они работают с регистрами.
encyclopedist
19.03.2016 00:15Мои измерения не подтверждали этот совет (во всяком случае с современными компиляторами и процессорами).
Что на самом деле легко понять — зависимость есть в обоих случаях, а разница в том, где расположена инструкция инкремента (и то если компилятор не смог сам справиться).
Преинкремент:
- Инкремент
- Использование нового значения
- Остальное тело цикла
Постинкремент
- Использование значения
- Инкремент
- Тело цикла
Или, если рассмотреть несколько итераций:
123123123 против 213213213
Современные процессоры не только конвейиризованные, но и со внеочередным исполнением, и он сам переставляет команды так как ему хочется, и вполне может стравиться в перестановкой 1 и 3 во втором случае, что сделает цикл эквивалентным первому.
eastig
17.03.2016 13:27-1Если следовать советам автора, то в лучшем случае не будет никакого прироста производительности, а в худшем будут трудно находимые баги.
Правильные советы по оптимизации C++ на x86 от Агнера Фога:
Optimizing software in C++
An optimization guide for Windows, Linux and Mac platforms
eastig
17.03.2016 13:40+61.6. Не создавайте временные объекты — 2
C++ — это не C, где объявление переменных должно располагаться в самом начале.
Автор видимо не в курсе, что есть C99, C11.
m08pvv
17.03.2016 13:53+1Про Cache line ping-pong — тут скорее про false sharing, ибо если два потока обращаются и к a, и к b, и к c, то никакое выравнивание не спасёт, т.к. будут гоняться три строки кэша вместо одной.
bfDeveloper
17.03.2016 14:23+3Совсем правильный пример конкатенации должен быть таким:
auto s = concat(s1,s2,s3);
, где concat — ленивый диапазон отсюда (https://github.com/ericniebler/range-v3), ну или из std, когда будет.
В этом случае вообще не произойдёт выделения памяти. Понятно, что если дальше нужен быстрый произвольный доступ, то всё равно лучше создать именно строку через range::copy(concat(...), s). Но если потом вы будете читать пару символов или только последовательно, то лучше оставить ленивый диапазон.
FoxCanFly
17.03.2016 14:42+52.6 — не правда.
http://en.cppreference.com/w/cpp/language/copy_elision
И это не единственный пример дезинформации.
Вообще такое ощущение, что автор пишет о каких то древних компиляторах, не умеющих в оптимизацию. Они давно достаточно умны, что бы почти обо всех пунктах заботиться не приходилось.nekipelov
17.03.2016 15:07+2Что именно неправда? Что NRVO не всегда может быть задействована? Или что не у всех классов есть конструктор перемещения? Что в примере не может быть задействовано RVO? Так и по ссылке тоже самое:
std::vector<Noisy> f() { std::vector<Noisy> v = std::vector<Noisy>(3); // copy elision from temporary to v return v; // NRVO from v to the returned nameless temporary } // or the move constructor is called if optimizations are disabled
Или про "совет почти потерял актуальность"?
Вы уж поконкретней, пожалуйста :-)FoxCanFly
17.03.2016 15:12+1В примере "плохой код" в этом пункте NRVO будет задействована. Поэтому считать этот код не оптимальным и говорить что надо писать только так нельзя.
nekipelov
17.03.2016 15:17А кто говорит про NRVO? Я написал "// Компилятор не может использовать RVO". Не NRVO, а RVO. "Плохой код" — это образное выражение относительно RVO, разумеется в нем нет ничего плохого.
nekipelov
17.03.2016 15:21С этим разобрались. Что еще вы считаете дезинформацией?.
FoxCanFly
17.03.2016 15:55+21.10 Вредный совет.
vector при последовательном добавлении элементов всегда будет оптимальнее. Да, тогда когда он упирается в границы выделенной памяти, придется выделить новый блок, но все реализации выделяют память с запасом — в 1,5 / 2 раза больше от текущей. В результате, копирование и аллокация блока в куче — не такое уж частое явление, тогда как std::list делает аллокацию под каждый новый элемент. И это уж если не говорить о том, что у вектора самый быстрый последовательный и случайный доступ к элементам. В результате я бы сказал по другому — всегда используйте vector, если нет веских причин использовать list или deque.nekipelov
17.03.2016 16:08Согласен, что совет спорный. Сильно зависит от количество вставок и того, куда вставляется. Но я слишком часто на практике сталкивался с тем, что приходилось переделывать с vector на deque или list. Поэтому призываю думать, а не бездумно писать vector в надежде, что кто-нибудь потом регулярно будет прогонять код профайлером под изменившиеся условия и исправит, когда vector станет работать плохо.
FoxCanFly
17.03.2016 16:001.8. Во всех актуальных реализациях std::string есть small string optimization. Для маленьких, в том числе строк нулевого размера, аллокации в куче не будет.
nekipelov
17.03.2016 16:05+1Конечно выделения памяти не будет, строка вообще пустая, поэтому я написал "Он будет пытаться". Это означает, отработает совсем другая ветка кода.
monah_tuk
19.03.2016 05:09Если мне не изменяет память, то libstdc++ который шёл в комплекте GCC до версии 5.x было не SSO, а COW. Да собственно, Саттер подтверждает. А это покрывает достаточно популярные 4.8 и 4.9.
GraD_Kh
17.03.2016 15:53+41.10. Не используйте vector там, где можно было бы обойтись list или deque
Для современных декстопов не очень актуальный совет, за счет последовательного расположения в памяти вектор, даже с учетом изменений может быть быстре листа: Тыцnekipelov
17.03.2016 16:37Повторюсь, что совет появился как раз из-за исправления с vector на что-либо другое. Если количество элементов мало, то обычно нет разницы, какой контейнер. Если же оно большое, например 1 000 000, может быть deque будет все же эффективней?
И надо думать не только о том, какое количество вставок сейчас. А еще и на много лет вперед, когда проект будут поддерживать совсем другие люди.GraD_Kh
17.03.2016 16:56+1Все зависит от конкретных цифр и надо не гадать, а делать бенчмарки: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
Вывод: нет однозначно лучшего контейнера, даже с учетом операций вставки в произвольное место.
arabesc
17.03.2016 16:49-1std::vector vec;
for(size_t i = 0; i < vec.size(); ++i)
Потому что в данном случае он дешев. Это будет эквивалентно следующему коду:
size_t size = vec.size();
for(size_t i = 0; i < size; ++i)
Да ладно, с чего вдруг эквивалентно, когда есть семантическая разница?
/offtopic с оформелнием кода в цитатах какой-то ад
Halt
17.03.2016 17:57+2Дополнительные условия внутри цикла или же вычисления, влияющие на счетчик цикла, приведут к невозможности развернуть цикл.
Разворачиванием циклов компилятор занимается самостоятельно. Ему следует помочь только тем, чтобы это можно было сделать. Также небольшие циклы желательно объединять в один. Но при наличии условий или большого тела цикла, наоборот, бывает лучше разбить на несколько циклов, чтобы хотя бы один из них был развернут компилятором.
Я просто оставлю это здесь: http://llvm.org/docs/Vectorizers.html
The Loop Vectorizer is able to “flatten” the IF statement in the code and generate a single stream of instructions. The Loop Vectorizer supports any control flow in the innermost loop. The innermost loop may contain complex nesting of IFs, ELSEs and even GOTOs.
int foo(int *A, int *B, int n) { unsigned sum = 0; for (int i = 0; i < n; ++i) if (A[i] > B[i]) sum += A[i] + 5; return sum; }
В статье очень много сомнительных мест, которые просто напросто дезинформируют читателя.
xanm
17.03.2016 18:27Интересно а в рамках какого проекта вы столкнулись с рассмотрением кода LinuxDC++/StrongDC++ ?
MacIn
18.03.2016 00:23Временные объекты создают, к примеру, вот таким кодом:
std::string s1, s2, s3;
…
std::string s = s1 + s2 + s3;
Это действительно проблема и в последних стандартах языка? Операция — то очень часто используемая. В языках, где строковый тип встроен, вполне может быть оптимизация такого случая вида "слей-ка мне в одну N строк, вот они".FoxCanFly
18.03.2016 01:41Стандарт об этом ничего не говорит и не должен, но компиляторы вольны оптимизировать это как считают нужным (std::string не "встроенный", но тем не менее для классов стандартной библиотеки компиляторы зачастую применяют особые оптимизации)
qw1
18.03.2016 13:20STLPort склеивает строки лениво.
Конкатенация строк возвращает некоторый объект, который тоже умеет складываться со строкой.
И только в момент вызова оператораoperator string()происходит выделение буфера и склейка.
tangro
18.03.2016 13:01+7Обложили бедного автора по-всякому, потому что в С++ какой тезис не двинь, как окажется, что бывают случаи\стандарты\компиляторы\железо\процессоры\память\алгоритмы, где это не выполняется :)
atd
А можно поподробнее? А то я всю жизнь считал, что Foo* foo1 и Foo& foo2 это одно и то же, за исключением того, что foo2 не надо явно разыменовывать, а адрес оно будет в любом случае читать. Ну и джентльменского соглашения о том, что в foo2 мне не собираются подсовывать nullptr. (хотя и могут)
nekipelov
Не думаю, что в программировании применимы джентльменские соглашения. Если указатель может указывать на null, рано или поздно он будет туда указывать. Если деструктор может сгенерировать исключение, рано или поздно это произойдет. Если обработчик сигнала не AS-Safe, рано или поздно это приведет к dead-lock. Поэтому указатели используют там, где нужен именно указатель. И обкладывают проверками.
atd
а вот эту часть проясните:
msvc, gcc и шланг сгенерят идентичный код с чтением указателя. или я пьян?
nekipelov
Код идентичный. Разница в необходимости проверок.
Gorthauer87
На си вот нет ссылок, но там тоже не всегда же проверки нужны.
midday
Погодите, я кучу раз натыкался на невалидные ссылки.
nekipelov
Если постараться, в C++, как и в других низкоуровневых языках, можно сделать все, что угодно. Однако ссылку даже нельзя проверить на валидность, т.к. это уже UB.
midday
Ну что стараться =) в большой компании это неизбежно. Если вы работаете над большим проектом и кроме вас в его кишках ковыряется 50+ человек, то тут и стараться не надо. Оно появляется постоянно… люди глупы по своей сути и склонны ошибаться. Да с сылкой — самые сложные баги, хрен поймешь что произошло.
MichaelBorisov
Указатель тоже в общем случае нельзя проверить на валидность. Можно сравнить его с 0, но кроме 0, есть и другие невалидные значения указателя, которые проверить нельзя.
anonymous
vanxant
Какая разница, что вы думаете насчет джентльменских соглашений? Конкретно то, о чем пишет atd — это undefined behavior по стандарту языка.
vanxant
Правильно абсолютно считаете. Автор плохо знает С++ и архитектуру процессоров. Технически это абсолютно одно и то же.
Разница в том, что указатель может быть нулл, а ссылка не может. Ну то есть можно сознательно прострелить себе ногу и превратить нуллптр в ссылку, но это UB.
В контексте оптимизации все верно, ссылку, в отличие от указателя не нужно каждый раз проверять.
Только это все из серии "вы можете хранить целые числа в типе double, но зачем"? Разные инструменты для разных задач.
nekipelov
Автор достаточно хорошо знает, просто невнимательно прочитал комментарий.
dyadyaSerezha
Если бы автор знал С++ достаточно хорошо, то не написал бы: «Ссылка непосредственно указывает на объект, а указатель содержит адрес, который нужно прочитать».
MichaelBorisov
Указатель тоже не всегда нужно каждый раз проверять. Более того, сравнение с null — это проверка только на один из видов невалидного указателя. Бывают еще ненулевые, но тем не менее невалидные указатели, которые вы никакими проверками не обнаружите.
anonymous