C++ велосипедостроение для профессионалов
Классы, которые люди самостоятельно пишут, а потом копируют из одного проекта в другой, хотя они уже есть в стандартных библиотеках, в простонародье называются велосипедами. Первый вопрос, который возникает при встрече с таким «велосипедом» — зачем люди переписывают что-то заново? Вариантов может быть несколько.
- Некоторые делают это для самообучения: берут класс стандартной библиотеки, пишут его сами с нуля, сравнивают то, что получилось, с тем, что есть в стандартной библиотеке — в процессе узнают для себя что-то новое.
- Некоторые проекты имеют особое требования к коду. В embedded-разработке принято работать без RTTI и без exception, поэтому части стандартной библиотеки, которые используют RTTI и exception, необходимо переписать без них.
- Редко, но бывает, когда велосипед пишут, потому что могут написать лучше, чем в стандартной библиотеке. Как правило, такие нововведения рано или поздно попадают в стандартную библиотеку.
- Другим только кажется, что они могут написать лучше, и таких людей больше. Но в процессе они обучаются, выясняют для себя что-то новое и что-то интересное открывают.
- Могут быть другие причины.
Сегодня мы не будем говорить о том, что велосипеды — это плохо, это не обязательно так. Мы поговорим о том, что действительно плохо:
- бездумно переносить устаревшие технологии 20–30-летней давности в современные проекты;
- пользоваться «вредными» бенчмарками и оптимизациями.
А также затронем «вредные» советы, обсудим новейшие практики программирования (C++ 11 и позднее), подумаем, что делать с «идеальным» велосипедом.
О спикере: Антон Полухин (@antoshkka) сотрудник компании Яндекс, активный разработчик библиотек Boost, автор TypeIndex, DLL, Stacktrace, Maintainer Boost Any, Conversion, LexicalСast, Variant, сопредседатель Национальной рабочей группы по стандартизации С++. Всё это вместе значит, что Антон ежедневно видит очень много кода, как опенсорсного, так и коммерческого, и очень хорошо знает, как часто разработчики изобретают велосипеды.
Итак, тема — велосипеды. С какого класса начнем? Правильно — со строки.
std: string
string: C++98
Представьте себе, что на дворе глубокое средневековье, люди в латах скачут на лошадях. Вы — разработчик стандартной библиотеки, и единственный стандарт, который есть, это С++ 98. Вам надо написать свою строчку.
class string {
char* data;
size_t size;
size_t capacity;
// ...
};
Вы начнете писать что-то очень простое без всяких шаблонов. У вас будет указатель на динамический проаллоцированный кусок памяти (data), переменная size, которая хранит количество символов в проаллоцированном куске памяти, и переменная capacity, которая задает размер этого динамического куска памяти.
class string {
char* data;
// ...
public:
string(const string& s)
:data(s. clone()) // new + memmove
{}
// ...
string(const char* s); // new + memmove
};
Для вашего класса строки вы напишите конструктор копирования и конструктор от массива символов. Оба они будут динамически аллоцировать кусок памяти, перемещать туда символы. Здесь написано new + memmove, но на самом деле там могут быть быть небольшие вариации типа malloc, memcpy, смысл остается тем же.
Так как вы — хороший разработчик стандартной библиотеки, вас интересует, насколько хорошо такой класс строки будет работать. Вы открываете пользовательский код, смотрите популярные рецепты и находите что-то наподобие примера ниже, где создается map от строки и int, и туда вставляется пара.
std::map m;
m.insert(
std::pair("Hello!", 1)
);
И тут вы понимаете, что дела плохи — медленно, очень медленно.
У вас есть знакомый Вася, который тоже разрабатывает стандартную библиотеку и у него класс строки работает быстрее. Где именно теряется производительность:
- Cначала вызывается конструктор строки от массива символов — это вызов new и memmove (
string("Hello!")). - Потом вызывается конструктор пары, т. е. будет вызван copy-конструктор строки. Это еще один вызов new и еще один вызов memmove (
make_pair(string("Hello!"), 1)). - Потом эта пара вставляется в map. Копируется пара и ее содержимое — еще один вызов new и memmove (
m.insert(make_pair(string("Hello!"), 1))). - После этого временный объект пары и временный объект строки будут удалены.
Получается весьма печальная картина — 3 вызова new, 3 вызова memmove, пара вызовов delete, и все это жутко медленно. Вас раздражает, что у Васи быстрее, и вы начинаете думать, как сделать лучше.
string: COW
Тут вы либо сами придумываете, либо где-то читаете о технологии Copy-On-Write (COW). Она позволяет эффективнее работать с временными объектами. Большая часть потерь была за счет того, что создаются временные объекты, которые никак не модифицируются: их просто создали, что-то из них скопировали и тут же уничтожили.
std::map m;
m.insert(
std::pair("Hello!", 1) // копии которые не надо копировать
); // копии которые не надо копировать
По технологии Copy-On-Write вместо того, чтобы строка уникально владела динамическим объектом, который создан в куче, можно сделать так, чтобы несколько строк одновременно ссылались на динамический объект. Тогда в этом динамическом объекте будет счетчик ссылок — сколько одновременно строчек работает с ним. Код будет выглядеть так:
class string_impl {
char* data;
size_t size;
size_t capacity;
size_t use_count; // <===
// ...
};
Вы напишете class string_impl (можно написать его получше) и добавите use_count, т. е. счетчик ссылок — сколько строчек ссылается одновременно на динамический объект. Еще вы поменяете конструктор копирования, теперь он будет брать указатель на динамический объект от входной строки и увеличивать счетчик ссылок.
class string {
string_impl*impl;
public:
string(const string& s)
:impl(s.impl)
{
++impl->use_count;
}
};
Немного придется повозиться с неконстантными функциями, которые потенциально меняют строчку. Если две строки владеют динамическим объектом, и одна из них начнет менять его, то другая увидит изменения. Это побочный эффект, которым пользователи будут недовольны, ведь они сначала работали с одной строчкой, а потом она внезапно поменялась.
Нужно добавить проверку: если мы уникально владеем динамическим объектом, то есть счетчик ссылок равен 1, то мы можем делать с ним все, что угодно. Если счетчик ссылок не равен 1, мы должны вызвать new и memmove, создать еще один динамический объект и скопировать туда данные из старого объекта.
class string {
string_impl*impl;
public:
char& operator[](size_t i) {
if (impl->use_count > 1)
*this = clone();
}
return impl->data[i];
}
};
Деструктор тоже изменится. Он будет уменьшать счетчик ссылок и смотреть: если мы — последний владелец динамического объекта, тогда его нужно удалить.
class string {
string_impl*impl;
public:
~string() {
--impl->use_count;
if (!impl->use_count) {
delete impl;
}
}
};
Производительность вставки в std: map
В конструкторе от массива символов ничего лучше не стало, по-прежнему new и memmove. Зато дальше вызовется конструктор копирования строки при создании пары, который теперь не вызывает ни new, ни memmove. Когда пара будет вставляться в map, опять будет вызван конструктор копирования строки, который опять-таки не вызывает new и memmove.
Все деструкторы временных объектов тоже не вызовут delete — красота!
Итого, COW более чем в 2 раза ускоряет код в C++98.
Если сейчас мне кто-то скажет, что знает технологию, которая увеличивает производительность моего кода в 2–3 раза, я буду использовать ее везде.
В 90-е года многие библиотеки так делали. Например, есть библиотека QT, где COW присутствует практически во всех базовых классах.
Но технологии не стоят на месте. Наступают 2000-е года, появляются процессоры с Hyper-threading и многоядерные процессоры, причем не только серверные, но и пользовательские:
- Hyper-threading в процессорах Pentium 4.
- 2-ядерный процессор Opteron архитектуры AMD64, предназначенный для серверов.
- Pentium D x86–64 — первый 2-ядерный процессором для персональных компьютеров.
Теперь у каждого пользователя может быть более, чем 1 ядро. И наша строка уже плохо работает, потому что у нас общий счетчик ссылок.
Например, есть два потока, в них по строке, которые ссылаются на общий динамический объект. Если потоки работают со строками и одновременно решают их удалить, получается, что мы из двух потоков будем пытаться одновременно менять динамический счетчик ссылок use_count. Это приведет к тому, что либо возникнет утечка памяти, либо приложение аварийно завершится.
string: COW MT fixes
Чтобы это исправить, вводим атомарную переменную — сделаем вид, что в C++ 98 есть std: atomic. Теперь наш класс выглядит так:
class string_impl {
char* data;
size_t size;
size_t capacity;
atomic use_count; //<=== Fixed
// ...
};
Все работает — замечательно! Почти…
Теперь у нас и конструктор копирования, и деструктор имеет в себе атомарную инструкцию , что не очень хорошо. Неконстантные методы превращаются в жуткое безобразие, потому что появляются граничные условия, которые редко возникают, но которые мы обязаны обрабатывать.
class string {
string_impl*impl;
public:
char& operator[](size_t i) {
if (impl->use_count > 1) { // atomic
string cloned = clone(); // new + memmove + atomic —
swap(*this, cloned);
// atomic in ~string for cloned; delete in ~string if other thread released the string
} // ...
}
};
Например, два потока владеют строчками. Эти строчки ссылаются на один и тот же динамический объект. Один поток решает поменять строку. Строка смотрит, что она неуникально владеет динамическим объектом и начинает объект клонировать. В этот момент второй поток говорит, что строчка ему больше не нужна и вызывает ее деструктор.
А первый поток все еще клонирует, вызывает new, memmove. Он закончил свои дела и вдруг понимает, что у него две строки, а нужна ему одна.
Придется еще предусмотреть логику и на такое, а это дополнительные проверки, возможно, дополнительный лишний вызов new и memmove, и опять много атомарных операций, что плохо.
Atomic
На X86 не атомарный инкремент — простое увеличение integer на единицу занимает один такт процессора [1]. Если сделать эту операцию атомарной, то она будет занимать от 5 до 20 тактов, если только одно ядро делает атомарную инструкцию и если это ядро последнее меняло атомарную переменную [2]. Если ядро не последним меняло атомарную переменную, то в районе 40 тактов.
Итого, такое решение в 5–40 раз медленнее только за счет того, что использована атомарная переменная. Дальше хуже.
Если несколько ядер одновременно работают с атомарной переменной, например, три ядра одновременно хотят сделать инкремент атомарной переменной, у нас будет ядро-счастливчик, которое начнет делать атомарный инкремент, остальные два ядра будут ждать от 5 до 40 тактов, пока ядро не закончит все свои действия.
Тут появляется второе ядро-счастливчик, которое начинает делать атомарную операцию, т. к. не оно последнее меняло атомарную переменную, это займет 40 тактов. Третье ядро все еще ждет. Чем больше ядер одновременно пытаются сделать атомарную операцию над одной и той же переменной, тем дольше последнее ядро будет ждать.
Так выглядит график ожидания последнего ядра:
В этом примере 16 ядер и последнее ядро ждет в районе 600 тактов. Это простой самого несчастливого ядра. Если просуммировать простои, то получится картина простоя получится квадратичная.
На 16 ядрах примерно 6000 тактов ушло в никуда.
Существуют системы, содержащие более 90 ядер, и если все они 90 ядер решат одновременно работать с одной и той же атомарной переменной, все будет очень печально.
COW более чем в 2 раза ускоряет код в C++98. Все равно Copy-On-Write быстрее и все тут.
С++11
В C++11 появляются rvalue reference, что позволяет писать специальные классы и специальные методы, которые работают с временными объектами.
Например, move-конструктор для строки одинаково хорошо работает, если строка COW и если строка самая обычная базовая из средневековья, где динамически аллоцируется объект, и только одна строка им владеет.
string::string(string&& s) {
swap(*this, s);
}
Что здесь происходит? На вход приходит объект s. Он временный, мы знаем, что компиллятор его скоро удалит, что больше им никто пользоваться не будет, и мы можем забрать у него ресурсы. С ним можно делать вообще все, что угодно, — главное, чтобы для него потом можно было вызвать деструктор.
Забрали ресурсы. Мы — пустая строка, нам пришла строка с результатом, делаем swap. Теперь мы строка с результатом, а временная строка без всяких ресурсов — пустая.
Посмотрим, как это работает на нашем примере, если у нас строка без COW.
std::map m;
m.insert(
std::pair("Hello!", 1) // string("Hello!")
);
Создается строка от массива символов «Hello». Тут new и memmove — так же, как с COW.
Дальше — лучше. При копировании строки в пару у нас вызовется move-конструктор строки (pair(string&&, int)). Пара видит, что строка временная, и забирает ресурсы из временного объекта. New и memmove не будет.
При вставке пары в map, map видит, что пара у нас тоже временный объект (m.insert(pair&&)). Map вызовет move-конструктор для пары, пара вызовет move-конструктор для своего содержимого, move-конструктор для строки.
Без new и memmove строка перекочует внутрь map: 1 вызов new и 1 вызов memmove — так же, как с COW, но без атомарных операций.
Хорошо, а если мы хотим копировать строчку? Мы все разумные люди, и хотим копировать строчку, как правило, если мы хотим ее менять.
Без COW мы скопировали строчку, сразу вызывался new и memmove. Мы можем менять строчку и делать все, что угодно.
Если у нас COW строка:
- создаем новый объект строки с атомарным инкрементом общего счетчика ссылок;
- одну из этих строчек начинаем менять;
- строчка атомарно посмотрит, что мы не уникально владеем строкой, вызовет new, memmove, проведет дополнительные проверки, чтобы внезапно второй поток не уничтожил эту строчку, что у нас нужное количество строчек и т. д.
Результат тот же, что и без COW, но, как минимум, пара лишних атомарных операций появляется.
char& operator[](size_t i) {
if (impl->use_count > 1) { // atomic
string cloned = clone(); // atomic—
swap(*this, cloned); // atomic in ~string for cloned
}
return impl->data[i];
}
Неконстантные методы по-прежнему ужасны. Если мы хотим пройтись по нашей строке (первым десяти символам в строке), используя индексы, с COW строкой — это 10 атомарных операций над одной и той же атомарной переменной. Если два потока одновременно проходятся по одной и той же строке — большая беда.
В итоге COW-конструктор имеет атомарные операторы, деструктор, скорее всего, будет вызывать атомарные инструкции — везде много атомарных инструкций, которые нам не нужны. Мы их не просили, и это против правил C++. Мы платим за то, чем не пользуемся.
Начиная с C++11 COW строчки запрещены в стандарте. Там наложены специальные условия на строчку, что COW реализовать невозможно. Все современные имплементации стандартных библиотек не имеют COW строк.
COW устарел, осторожнее с его использованием.
Аккуратнее используйте COW в новых проектах. Не доверяйте статьям, которым больше 10 лет, перепроверяйте их. COW не показывает таких хороших результатов, как 20 лет назад.
Случаи, где COW все еще жжет
Если вы имели COW строчку и всем своим пользователям говорили: «У нас COW строка — она идеально все копирует, у нас все замечательно, у нас везде COW», пользователи могли заточиться под это, и писать код с учетом того, что ваши классы используют COW.
Например, пользователь мог написать класс bimap — это класс, который умеет искать как по ключу, так и по значению.
// COW legacy
class bimap {
std::map str_to_int;
std::map int_to_str;
public:
void insert(string s, int i) {
str_to_int.insert(make_pair(s, i));
int_to_str.insert(make_pair(i, std::move(s)));
}
Он мог написать его через два std: map, каждая из которых имеет строчку. Здесь строчка COW, пользователь об этом знает, как и то, что в map две копии строки. Пользователь знает, что они динамически будут ссылаться на один и тот же объект памяти, и что это эффективно по памяти. Если здесь COW строчку поменять на обычную, затраты по памяти увеличатся вдвое.
// COW legacy fix
class bimap {
std::map str_to_int;
std::map int_to_str;
public:
void insert(string s, int i) {
auto it = str_to_int.insert(make_pair(std::move(s), i));
int_to_str.insert(make_pair(i, *it.first)));
}
В C++17 это можно поправить, например, как в примере выше, заменив одну из строчек на string_view. По памяти получится точно также, но уберутся атомарные операции и код станет немного быстрее.
Одна оптимизация для string
Получается, что к той древней строчке 98 года, которая уникально владела динамическим объектом, мы добавили move-конструктор, и все — это идеальная строка? Ничего лучше сделать нельзя?
Вот что придумали люди. Они посмотрели на один из первых наших примеров, где создается map от строки и int, и туда вставляется пара, долго качали головой и говорили, как все плохо:
— Тут вызывается new и memmove. За new может стоять системный вызов и атомарные операции, а у нас еще нет C++14, где компилятор умеет оптимизировать new. Все очень плохо — давайте сделаем что-нибудь получше!
Люди придумали, как можно, не меняя размер строки — переменной std: string — хранить в ней символы, не аллоцируя динамически память. Они посмотрели на самый первый класс строки:
—У нас здесь указатель на 64-битной платформе — это 8 байт, у нас size тоже на 64-битной платформе — это опять 8 байт. Это 16 байт — в них можно сохранить 15 символов! Что, если пользоваться этими двумя переменными не как переменной-указателем и переменной size, а прямо поверх них располагать данные.
class string {
size_t capacity;
union {
struct no_small_buffer_t {
char* data;
size_t size;
} no_small_buffer;
struct small_buffer_t {
char data[sizeof(no_small_buffer_t)];
}small_buffer;
}impl;
}
Теперь внутри строки в примере выше находится union. Первая часть — это указатель на data и переменная size_t. Вторая часть union — структура — содержит data (маленький буфер размером с char* и size_t). В него влезает примерно 16 байт.
Если сapacity = 0 — это значит, что мы память динамически не аллоцировали и нам надо идти в impl small_buffer_t, и в data будет лежать наша строчка без динамической аллокации.
Если сapacity ≠ 0, значит, мы динамически где-то проаллоцировали память, и нужно идти в impl no_small_buffer_t. Там есть указатель на динамически проаллоцированный кусок памяти и переменная size.
Конечно, в примере немного упрощенный вариант. Некоторые стандартные библиотеки, например Boost, умеют хранить 22 символа и вдобавок терминирующий 0 без динамических аллокаций, не увеличивая размер строки. Все современные стандартные библиотеки используют этот трюк. Это называется Small String Optimization.
Эта штука хороша, во-первых, на пустых строчках. Они теперь гарантированно не аллоцируют память, и гарантированно вызов метода c_str () теперь не будет аллоцировать память.
Я знаю компании, которые переписывали std: string, потому что у них пустая строка динамически аллоцировала память. Не надо этого больше делать.
Во-вторых, например, наш «Hello!» влезет без динамической аллокации. Если в строчках хранятся логины пользователей, их имена и фамилии отдельно от имен, какие-то идентификаторы, города, страны, названия валют — как правило, все влезет в строчку без динамических аллокаций.
Но люди посмотрели и опять подумали, что медленно. Начиная с C++17, компилятор умеет оптимизировать memmove, его альтернативу — ту, которая находится в строке, на этапе компиляции. Но и этого показалось мало. В C++17 есть Guaranteed copy elision, который гарантирует, что в ряде случаев вообще никаких копирований и memmove не будет. Просто в map каким-то чудом образуется эта строчка без промежуточных переменных.
— Пока все выглядит как реклама велосипедов на самом деле. Например, COW в GCC был до 2015 года, до выхода 5.1. Значит, нужно было писать велосипеды?
— Больше-то не нужно!
— Как? Например, все говорят, что классная штука Small String Optimization. Но, допустим, когда строка выделяется динамически, size и capacity можно засунуть в тот же самый буфер, в котором лежит строка. Тогда строка будет всего 8 байт. И если у меня в объекте много строк, это будет выгоднее?
— У меня реальный случай из практики. Замена COW-строки на строку со Small String Optimization ускорила проект на 7–15%, потому что большую часть времени мы работаем почему-то с маленькими строчками, которые в std: string влезают. Поэтому становится быстрее.
Можно ли использовать строчку, которая будет динамически в памяти хранить size и capacity? Можно. Тут подключатся проблемы с оптимизатором. Видя, что у нас указатель на какой-то участок памяти, он не сможет лучше оптимизировать эти переменные. Оптимизатор не сможет делать эвристики, основанные на size и capacity. Если же size и capacity расположены на стеке и оптимизатор видит это, он сможет делать на этом эвристики и лучше оптимизировать код.
— С широкими юникодными строками эта оптимизация хуже работает?
— Да, хуже. Но количество байтов, которое есть в small_buffer, все то же.
Разработка без оглядки на готовые решения. std: variant
На примере std: variant рассмотрим, что бывает, если люди пытаются велосипедостроительствовать, не заглядывая в чужие решения.
В C++17 принят класс std: variant — это умный union, который помнит, что он хранит. Мы можем написать std: variant
union {
T0 v0;
T1 v1;
T2 v2;
// ...
};
int t_index;
Если теперь попытаться записать туда вектор, std: variant посмотрит, что он хранит в себе строчку в данный момент, а не вектор, вызовет delete для строки, на месте строки сконструирует вектор и в какой-то момент обновит t_index.
Класс приняли в C++17, и люди по всему миру сразу кинулись его писать заново, переписывать, велосипедостроительствовать.
template
class variant {
// ...
std::tuple data;
};
Выше — реальный код из опенсорсного проекта, видите в нем ошибку? Здесь вместо union получился struct.
Ниже — код из коммерческого проекта:
variant& operator=(const U& value) {
if (&value == this) {
return *this;
}
destroy(); // data->~Ti()
construct_value(value); // new (data) Tj(value);
t_index = get_index_from_type(); // t_index = j;
return *this;
}
Здесь ошибка гораздо хуже и во многих имплементациях variant она присутствует. Здесь будут большие проблемы с исключениями.
Например, у нас variant, который хранит в себе std: string и мы пытаемся записать в него вектор. В строчке destroy вызовется delete для строки. С этого момента variant пустой, он ничего не хранит.
Потом на месте строки мы пытаемся создать вектор. Вектор передался по константной ссылке и мы вынуждены его копировать. Вызываем placement new и пытаемся скопировать вектор. Вектор — класс большой, в нем могут храниться пользовательские данные, которые при копировании могут кидать исключения. Допустим, мы кинули исключение. Оно выйдет из текущего блока, вызывая деструкторы всех локальных переменных, и выйдет в блок выше. Там исключение тоже вызовет деструкторы всех локальных переменных. Дойдет до того блока, где был объявлен сам variant и вызовет деструктор варианта.
variant& operator=(const U& value) {
if (&value == this) {
return *this;
}
destroy(); // data->~Ti()
construct_value(value); // throw; ...
// ...
// ~variant() {
// data->~Ti() // Oops!!!
Деструктор варианта смотрит, что у него записано в переменной index, которая еще не обновлена. В ней записано std: string, т. е. variant думает, что у него есть строка, которую надо удалить. А на самом деле на этом месте уже ничего нет, строка уже удалена. В этот момент вся ваша программа аварийно завершится.
Чтобы этого избежать, достаточно открыть интерфейс стандартной библиотеки и посмотреть, что std: variant имеет функцию valueless_by_exception, удивиться, что это такое, и посмотреть, зачем оно нужно. Можно открыть исходники Boost — там 2/3 кода посвящено этой проблеме.
Я говорю это все к тому, чтобы вы и все ваши подчиненные смотрели, как написаны велосипеды у других людей, во избежание таких печальных последствий. Это очень популярная ошибка. Она везде проскакивает.
Я привожу пример только variant, но в многих других классах есть подобное. Люди переписывают, думают, что что-то лишнее, не заглядывают в чужой код, и это приводит к катастрофическим последствиям.
Пожалуйста, смотрите в код, который вы переписываете или придумываете
заново. Такой подход значительно упростит вашу жизнь.
FORCE_INLINE
Самое время попрыгать по больным мозолям.
Можно найти проекты, где все методы помечены как FORCE_INLINE — буквально весь проект вдоль и поперек на гигабайты кода. У людей спрашиваешь:
— Зачем вы все пометили FORCE_INLINE?— Мы написали маленький бенчмарк, проверили — с FORCE_INLINE быстрее. Мы написали и здесь маленький бенчмарк — проверили, с FORCE_INLINE быстрее. Мы протестировали все маленькими бенчмарками и везде с FORCE_INLINE быстрее — мы FORCE_INLINE запихнули во весь проект.
— Вы неправильно делали бенчмарк.
И с этого момента с людьми очень сложно спорить, потому что у них есть бенчмарк, а ты написать такой бенчмарк не можешь.
У процессора есть не только кеш данных
Современные процессоры — очень сложные устройства. Никто не знает до конца, как они устроены, даже разработчики процессоров.
«Большинство современных микропроцессоров для компьютеров и серверов имеют как минимум три независимых кеша: кеш инструкций для ускорения загрузки машинного кода, кеш данных для ускорения чтения и записи данных и буфер ассоциативной трансляции (TLB) для ускорения трансляции виртуальных (логических) адресов в физические, как для инструкций, так и для данных» [1].
Современный процессор не может выполнять вашу программу прямо с диска или прямо с оперативной памяти. Прежде, чем он начнет выполнять программу, он должен подтянуть ее в кеш инструкции. Только оттуда процессор может выполнять инструкции.
Некоторые процессоры имеют хитрый кеш инструкций, который делает дополнительную обработку команд, которые в него попадают. Но кеш инструкций — маленький, в него помещается мало кода. Если вы используете компилятор, который действительно делает FORCE_INLINE, когда вы его просите сделать FORCE_INLINE, у вас увеличивается объем вашего бинарного кода.
Представьте, что на рисунке выше ваша программа. Зеленым отмечено то, что поместилось в кеш. Это еще дополнительно ваш hot path — то место, где ваша программа тратит основное количество времени. Сейчас оно все поместилось в кеш процессора, в кеше инструкций простоя не будет.
Если вы добавите FORCE_INLINE, по бенчмаркам все будет замечательно, но код перестанет помещаться в кеш инструкций.
Когда вы дойдете до красной строчки, процессор скажет: «У меня нет инструкций новых, я должен подождать, пока они подтянутся из памяти». Если это где-то в цикле, он будет постоянно перещелкивать какие-то инструкции, подтягивать их себе из памяти в кеш. Это медленно.
Чтобы ваш бенчмарк правильно отражал реальное положение дел, он должен учитывать все 3 кеша — данных, инструкций и адресов. Для этого бенчмарк должен:
- в бинарном виде занимать столько же, сколько ваш production код;
- иметь приблизительно такое же количество функций и переходов, как ваш production код;
- вызывать методы так же, как ваш production код.
Другими словами, написать такой бенчмарк невозможно. Можно протестировать только ваш production код.
Если вы добавили FORCE_INLINE и ваш production код не стал лучше — лучше убрать FORCE_INLINE. Современные компиляторы умеют инлайнить. 10 лет назад они не умели этого делать хорошо, и FORCE_INLINE действительно в некоторых случаях помогал, например, на GCC. Сейчас нет.
Я говорю, что FORCE_INLINE — плохо, стоит отказаться от него в большинстве случаев, хотя иногда он может быть полезен.
Однако, разработчики компиляторов умные люди. Они видят, что пользователи пишут везде FORCE_INLINE и программы становится медленнее. Поэтому современные компиляторы имеют разные эвристики на игнорирование FORCE_INLINE. Некоторые компиляторы просто считают строчки внутри функции — если ваша функция длиннее трех строчек кода, FORCE_INLINE будет проигнорирован.
Ходит легенда, что есть компилятор, где люди очень сильно озаботились FORCE_INLINE, он их так достал, что они придумали следующую эвристику:
Если пользователь помечает FORCE_INLINE функцию, которую гарантированно не надо делать FORCE_INLINE, компилятор это запоминает и считает, сколько раз такое произошло. Если превышено некое пороговое значение, компилятор у себя выставляет галочку: «Пользователь не знает, что такое FORCE_INLINE и использует его не там, где нужно — игнорировать все FORCE_INLINE от пользователя».
Если вы вдруг написали программу, добавили туда десяток FORCE_INLINE и все стало замечательно быстрее, возможно, что вы пользуетесь этим компилятором. Смотрите ассемблерный код, если вам действительно нужно, чтобы что-то встраивалось, чтобы FORCE_INLINE в этом месте действительно был. Я сам удивлялся тому, что в ряде случаев компиляторы тихо игнорируют FORCE_INLINE.
И наоборот, компилятор может тихо игнорировать ваше «не инлайнить». Он подумает: «Ты не знаешь, что делаешь, написал не инлайнить, но я лучше знаю — я заинлайню».
Cлучай из практики
Я знаю очень умного программиста, который писал имплементацию B-Tree. Все было сделано на С++, на шаблонах, везде perfect forwarding, без всяких динамический аллокаций — просто идеально. Когда этот код стали проверять на одном из Performance Analyze, выяснилось, что исполнение не достаточно быстрое из-за того, что большую часть времени занимает ожидание инструкций в кеше инструкций.
Программист подумал, чуть упростил B-tree, убрал perfect forwarding, заменил его везде на константные ссылки, потому что B-tree никак не менял данные, которые ему приходили, убрал пару шаблонов, сделал код чуть компактнее, добавил noexcept, что тоже уменьшает объем бинарного кода.
В итоге код стал работать в 2 раза быстрее. Алгоритм не меняли — все то же самое, но код стал работать быстрее.
Если не верите мне, что FORCE_INLINE плохо, то рекомендую посмотреть лекции (1, 2) разработчика Clang Чендлера Каррута. Он говорит о том же, что и я, но короче, быстрее и на английском.
От «вредных» бенчмарков переходим к «вредным» советам.
Aliasing
Редко, когда разработка идет под одну платформу. Чаще бывает, что когда-то давным-давно разрабатывали под одну платформу, а теперь — под несколько.
Обычно, если компания начинается, как маленький стартап, она может выбрать себе одну платформу, под которую у нее уже есть заказчики. Постепенно компания растет, код становится популярнее, и приходит мысль портировать его на другие платформы.
Но в момент, когда люди начинают портировать на GCC, программа перестает работать: все компилируется, но тесты не проходят, программа выдает какой-то неадекватный вывод. Люди лезут на Stack Overflow или на другие ресурсы, посвященные программированию, задают этот вопрос и получают ответ:
— Добавьте волшебную опцию компилятора -fno-strict-aliasing и у вас все заработает.
И действительно — все начинает работать.
Объясню на примере, что делает эта опция (с именем функции я здесь не заморачивался).
bar qwe(foo& f, const bar& b) {
f += b;
return b * b;
}
Функция qwe принимает в себя две переменные: foo по ссылке, bar по константной ссылке. Это два разных типа данных. Внутри тела функции к f прибавляется значение b и выводится квадрат от b.
Ниже немного ассемблерного псевдокода, который скомпилирует компилятор, если подсунуть опцию -fno-strict-aliasing.
bar qwe(foo& f, const bar& b) {
// load b
// load f
f += b;
// load b
return b * b;
}
Компилятор:
- подгрузит в регистр значение переменной b,
- подгрузит в регистр значение переменной f,
- произведет операцию f += b,
- запишет значение f в память,
- подгрузит значение b опять в память,
- выполнит b2.
Тут большинство людей задаются вопросом, зачем мы второй раз подгружали b в регистр, она же уже в регистре.
А потому, что добавили опцию -fno-strict-aliasing. Она говорит компилятору о том, что два типа данных, абсолютно разных, никак друг с другом не пересекающихся, все равно могут находиться в одной и той же ячейке памяти. Исходя из этого компилятор начинает генерировать код.
Когда вы делаете f += b, компилятор думает, что возможно f и b находятся в одной и той же ячейке памяти, и запись в f меняет значение b. И это во всем вашем проекте — добавили опцию, во всем проекте код стал генерироваться хуже.
По разным замерам (например, этому и этому), в зависимости от кода и оптимизации, это дает от 5% до 30% просадки производительности. Все очень зависит от ваше
