Надеюсь вам понравилась статья про работу с памятью на консолях, где каждый ездил на том велосипеде, который сам же и придумал, попробую рассказать про зоопарк теперь уже стандартных библиотек. Стандартных в отдельной студии или конторе, потому что у соседней будет свой стандартный стандарт. Забавно что любовь прикрутить очередную погремушку к своему велосипеду становится тем сильнее, чем становится крупнее контора, поэтому приходя в игровую студию есть очень немаленький шанс, что стандартный STL у неё нестандартный, обёрнут или вовсе запрещён религией кодстайлом.
EA, Facebook, Google, Adobe, LLVM и рядок компаний поменьше тратят человеко-десятилетия в поисках ответа на главый вопрос жизни, Вселенной и всего такого «почему std:: это медленно, непредсказуемо и жрёт память». По аналогии с прошлой статьей вам не потребуется знать стандарт наизусть, а будет достаточно понимать, что такое указатель, чем вектор отличается от дерева и почему промах в кеше это дорого, а дальше я пройдусь по разным стандартным библиотекам и про каждую немного расскажу, что это, зачем оно появилось и где об него можно больно удариться, потому что про вот этот последний пункт обычно забывают "продаваны" и прочие студийные еванглелисты, когда расказывают какое там всё красивое, легкое и с++двадцатое.
EASTL и её best practices
Начнём с главного экспоната и самой стандартной из всех стандартных игровых STL. EASTL это альтернативная реализация от Electronic Arts, выросшая в те времена, когда даже у компиляторов STL был разного и зачастую сомнительного качества, а собирать игру надо было под десяток платформ сразу. Живёт она в основном там, где есть жёсткий бюджет памяти и кадра вроде консолей, мини-движков и всякого embedded-подобного и околоигрового кода. Главная её ценность это даже не скорость сама по себе (хотя она действительно быстрая и некоторые стандартные алгоритмы написаны быстрее свои STL аналогов), а контроль над аллокациями и одинаково предсказуемое поведение на всех платформах. (https://github.com/electronicarts/EASTL)
Одинаковость тоже характерная черта этой либы, но даже это не гарантирует, что у вас будет одинаковое поведение прям везде, но в большинстве случаев будет.
Чтобы этого добиться, EASTL переосмыслила несколько базовых вещей и теперь аллокатор тут полноправный гражданин, а не шаблонный довесок как в стандарте, и свой аллокатор теперь сделать легко и приятно. Добавились контейнеры с фиксированной ёмкостью, которые держат память прямо в объекте и вообще не ходят в кучу. Вообщем большинство идей, к которой комитет добрел только к С++17, здесь жили с 2000 лохматого года.
// fixed_vector: 64 элемента живут прямо в объекте, аллокаций в кучу ноль eastl::fixed_vector<Entity, 64, /*overflow=*/false> entities;
К библиотеке прилагается сборник EASTL Best Practices, который хорош тем, что это не очередные рекламные призывы, а выстраданные «делай так, а вот так не делай» правила, и многие советы про фиксированные ёмкости и избегание скрытых аллокаций полезны и за пределами самой EASTL. Чего делать точно не стоит, так это тащить всё это в обычный прикладной или серверный код, где нет проблем с памятью и важна совместимость с экосистемой std::.
А брать EASTL ради смутного ощущения «это же быстрее» в проект, который и так прекрасно живёт на стандарте, значит заплатить годом интеграции и переучиванием команды за выигрыш, которого вы, скорее всего, даже не почуствуете. Будет больно, поэтому три раза подумайте.
С такой же проблемой аллокаций на стеке мучаются разработчики компиляторов вроде LLVM с его SmallVector, DenseMap, StringMap и их родней. Формально это код самого компилятора, но идеи универсальны для любого места, где живут миллионы мелких короткоживущих контейнеров, и LLVM спроектировал всё именно под это. SmallVector<T, N> держит первые N элементов прямо в себе, а DenseMap это хеш-таблица с открытой адресацией, которая лежит плотным куском и потому хорошо дружит с кешем.
// первые 8 элементов на стеке, аллокация только при переполнении llvm::SmallVector<Instruction*, 8> worklist;
Подвох у этой красоты и быстроты ровно и тот же, что и EASTL и тащить зависимость от целого LLVM ради пары контейнеров это явный перебор, а притащить вам придется примерно треть хедеров LLVM, поэтому лучше взять отдельную реализацию той же идеи. Почитать подробнее можно тут и тут.
Folly
Folly это большой open-source набор библиотек от книга-лицо конторы со своими контейнерами, строками, асинхронщиной и утилитами. Всё заточенно под высоконагруженные сервисы, где экономия на аллокациях и промахах кеша умножается на гигантский масштаб применения, и поэтому здесь живут одни из самых быстрых хеш-таблиц folly::F14, а также очень быстрые универсальные строки fbstring, переалоцируемые контейнерыfbvector и невесомые small_vector.
Логика у всего зоопарка одна: «этого у нас миллиарды штук, оптимизируем хвосты распределений и не ходим в память», но беда в том, что Folly сама по себе тяжёлая в сборке и в зависимостях заточена под свою инфраструктуру, так что тянуть её примерно половину ради одного контейнера, Ну это получится как покупать камаз, чтобы возить пакет молока, ну то есть можно, грузовики они такие... в хозяйстве всегда пригодятся.
Еще стоит почитать доклад Николаса Ормрода с CppCon 2016 про folly::fbstring, это, наверное, лучший способ понять почему марковчане похоронили плюсовые строки и написали 8! (восемь) своих. Главная идея folly::fbstring в том, что «строка» это три разные структуры данных, притворяющиеся одним типом, и какая из них работает прямо сейчас, зависит исключительно от длины.
Сам объект занимает 24 байта на 64-битной системе и эти 24 байта это union, который в зависимости от категории трактуется то как массив символов прямо внутри объекта, или как структура из указателя, размера и ёмкости. Категория хранится в двух старших битах последнего байта объекта, который этот байт совпадает со старшим байтом поля capacity, а реальные ёмкости строк никогда не дорастают до значений, где задействованы эти два бита, так что их можно бесплатно занять под тег.
24 байта объекта fbstring (little-endian, 64 bit): small: [ c0 c1 c2 ... c22 | spare ] // строка прямо тут, 0 аллокаций └─ (23 - size); при полном заполнении = 0 = '\0' medium/ [ char* data | size_t size | size_t capacity ] large: └─ 2 старших бита = тег категории
Первый режим это короткие строки, та самая SSO (small string optimization) пока строка влезает в 23 байта, остаток свободной ёмкости хранится в последнем байте, и когда строка заполнена под завязку (все 23 символа заняты), этот остаток равен нулю, а ноль это по совместительству нуль-терминатор. То есть один и тот же байт работает и счётчиком свободного места, и завершающим символом C-строки, и за счёт этого в 24 байта удаётся впихнуть честные 23 символа плюс терминатор терминального байта.
Второй режим это средние строки, примерно от 24 до 255 байт. Тут уже не обойтись без кучи, поэтому символы лежат в обычном буфере, выделенном аллокатором, и владеет им строка единолично. Копирование такой строки это честное жадное копирование.
Еще один момент, про который многие забывают, это что Folly очень плотно дружит с jemalloc и не стесняется этим пользоваться. Вместо того чтобы вслепую запрашивать ровно size байт, она спрашивает у аллокатора, сколько он реально готов отдать под этот запрос, и забирает всю фактическую ёмкость, а при росте пытается расширить блок на месте через xallocx, чтобы не копировать данные туда-сюда. Это одна из причин, почему fbstring ощутимо выигрывает именно в связке с jemalloc и почему вне этой связки часть преимуществ испаряется.
fbstring (24 байта, режим medium: 24..255 символов) ┌───────────────────┬───────────────┬───────────────────────┐ │ char* data │ size_t size │ size_t capacity │ └─────────┬─────────┴───────────────┴───────────────────────┘ │ ▲ │ единоличное владение │ забрали ВСЮ фактическую │ (eager copy при копировании) │ ёмкость, а не ровно size ▼ │ куча (буфер от jemalloc) │ ┌──────────────────────────────┬─────────┴──────────┐ │ 'H''e''l''l''o' ... '\0' │ свободный хвост │ └──────────────────────────────┴────────────────────┘ │◄────── запросили size ──────►│ │ │◄────── получили usable size (jemalloc) ──────────►│
Третий режим включается на супер длинных строках от 256 байт, когда начинается возня с copy-on-write, потому что доля таких строк составляет обычно меньше 5%, но они могут занимать до 25% памяти строк. Перед самими символами в куче лежит маленький служебный заголовок с атомарным счётчиком ссылок, и копирование такой строки не копирует символы, а увеличивает счётчик на единицу.
Реальное копирование откладывается до первой мутации и как только кто-то собирается изменить разделяемый буфер, строка уже делает собственную копию и дальше её меняет. Логика здесь, что короткие строки это имена, ключи и токены, их миллионы и аллокация на каждую убьёт всё, а длинные строки копировать дорого, поэтому их выгоднее шарить по ссылке.
Рост строки без переезда данных ──────────────────────────────── надо больше места: fbstring ──── xallocx(расширить на месте) ───► jemalloc │ ┌─────────────────────────────────┤ ▼ ▼ получилось расширить не вышло (соседний тот же буфер, data НЕ блок занят) → честная меняется, копирования нет новая аллокация + копия * вне jemalloc этих фокусов (usable size, xallocx) нет — и часть преимущества fbstring просто испаряется
Расплата за красоту прячется именно в третьем режиме, сopy-on-write хорош в однопоточном мире, но в многопоточном атомарный инкремент и декремент счётчика ссылок на каждое копирование и уничтожение это синхронизация на ровном месте, и для потоков она частенько обходится дороже, чем если бы просто скопировали буфер и забыли.
Поэтому COW для строк в современном C++ считается скорее антипаттерном (стандарт его в std::string фактически запретил начиная с C++11), и сам fbstring со временем оброс оговорками и надо смотреть не выстрелит ли такая реализация в ногу при синхронизациях.
Boost и flat_map
Все вы знаете Boost и его евангелиста на хабре @antoshkka это огромный, я бы даже сказал вселенского масштаба, полигон новых идей, откуда лучшее со временем уезжает в стандарт, там есть экзотический ассоциативный контейнер flat_map. У него интерфейс как у std::map, но внутри отсортированный вектор, поэтому он лежит одним плотным куском в памяти, и бинарный не прыгает по узлам красно-чёрного дерева как в обычной. Это оказалось настолько очевидно полезно, что только в C++23 оно доехало до стандарта как std::flat_map, и тут стоит сказать спасибо авторам Boost, потому что огромная часть полезного из него рано или поздно становится стандартной.
boost::container::flat_map<int, Value> m; // внутри отсортированный вектор
Хорош этот контейнер там, где словарь читается часто, а меняется редко, т.е. разного рода конфиги, справочники, lookup-таблицы. А вот при постоянном потоке вставок и удалений в середину он начинает проигрывать, потому что вставка это O(N) сдвиг хвоста, и ссылки с итераторами на элементы после неё нестабильны.
Zmeya и сериализуемые контейнеры
Zmeya это библиотека stl-подобных контейнеров, спроектированных так, чтобы их можно было сохранить одним блобом и потом пользоваться без распаковки. Внутри вместо указателей лежат относительные смещения, поэтому блоб можно положить по любому адресу, и он остаётся валидным.
Применяют это чудо для загрузки ассетов, уровней и конфигов. И можно сохранить структуру в файл, а при старте просто отобразить его в память и сразу работать без сериализации вообще, это ровно та старая модель из 90-х «запеки уровень в архив и положи в память по адресу», только у нас теперь не уровень, а его кусочек. Хотя я видел, как умельцы и нехилые уровни по 10-15 мегабайт умудрялись скормить змее, и вроде даже работало.
struct Monster { zm::String name; zm::Array<int32_t> loot; // id предметов zm::Pointer<Monster> next; // ссылка на соседа по уровню }; struct Level { zm::String title; zm::Array<Monster> monsters; zm::HashMap<zm::String, int32_t> spawnPoints; };
Дальше идёт этап сборки: тут работает BlobBuilder, который выделяет объекты внутри будущего блоба, раскладывает данные и сам проставляет правильные смещения, так что уже не нужно вручную считать байты.
// Сборка блоба выполняется один раз, на билдферме zm::BlobBuilder builder; zm::BlobPtr<Level> level = builder.allocate<Level>(); builder.copyTo(level->title, "Catacombs"); // массив на 2 монстра zm::BlobPtr<zm::Array<Monster>> monsters = builder.allocateArray(level->monsters, 2); builder.copyTo(monsters[0].name, "Skeleton"); builder.copyTo(monsters[0].loot, { 101, 102 }); builder.copyTo(monsters[1].name, "Ghoul"); builder.copyTo(monsters[1].loot, { 205 }); // относительная ссылка одного объекта блоба на другой monsters[0].nextInWave = &monsters[1]; builder.copyTo(level->spawnPoints, { {"north", 0}, {"south", 1} }); // на выходе просто плоский кусок памяти, который можно записать в файл std::vector<char> bytes = builder.finalize<std::vector<char>>(); writeFile("catacombs.level", bytes);
А вот ради чего всё затевалось. Собственно загрузка, в которой нет ни парсинга, ни обхода дерева объектов, ни фикса указателей и можно просто смапить файл в память по какому угодно адресу, и скастовать начало буфера к корневой структуре. После чего можно пользоваться, как будто объект всё это время жил в обычной куче. Ну красота же?!!
// Загрузка — фактически бесплатная std::vector<char> bytes = readFile("catacombs.level"); const Level* level = reinterpret_cast<const Level*>(bytes.data()); // никаких new, никакого разбора — просто читаем printf("Level: %s\n", level->title.c_str()); for (const Monster& m : level->monsters) { printf(" %s, loot count = %zu\n", m.name.c_str(), m.loot.size()); } const Monster* second = level->monsters[0].nextInWave.get(); int spawn = level->spawnPoints["north"];
Один минус... всё это работает только в одну сторону, на чтение. Блоб неизменяемый, его контейнеры рассчитаны на то, что собраются данные один раз на этапе билда, а в рантайме только читаешь. Как только нужно динамически добавлять монстров, менять размер массива или дописывать ключи в хеш-таблицу, вся выгода мгновенной загрузки исчезает, потому что относительные смещения не рассчитаны на перекладывание данных в живом блобе. Поэтому Zmeya и подобные ей штуки (FlatBuffers, Cap'n Proto) хороши именно для read-only данных.
Stlab и value-oriented данные
Stlab от Adobe больше про целое направление (VOP, value-oriented programming), которое характерно именно для адобоваримого софта. Основной единицей тут становится значение, которое свободно копируется, сравнивается и перемещается, а не объект с идентичностью и кучей ссылок на соседей. Т.е. прежде чем притащить их идеи к себе, вам сначала надо научиться "немножко" думть в другой парадигме разработки.
На этой отдельной филосовии построен весь их софт. Как я сказал выше, значение теперь есть объект, и меньше указателей значит проще разместить данные плотно, проще рассуждать о владении и не плодить случайные аллокации и shared_ptr. Чтобы понять, против чего вообще борется value-oriented programming, надо посмотреть, как ту же задачу решают «классически». Допустим, у нас есть набор разнородных объектов, которые надо нарисовать, и ООП-разработчик скорее заведет базовый класс с виртуальным методом и сложит наследников в вектор указателей.
// Классика: базовый класс + виртуальные методы struct Shape { virtual ~Shape() = default; virtual void draw(std::ostream&) const = 0; }; struct Circle : Shape { void draw(std::ostream& o) const override { o << "circle"; } }; // и контейнер из указателей на кучу std::vector<std::shared_ptr<Shape>> document;
С этого момента у нас в коде поселяются указатели и разделяемое владение, но каждый объект живёт в случайном месте кучи и копирование вектора копирует указатели, а не объекты, и теперь мы получим два вектора, которые делят одно и то же изменяемое состояние. Ещё Circle обязан заранее знать, что он Shape, то есть тип данных намертво сцеплен с иерархией, в которой его собираются использовать.
VOP позволяет спрятать полиморфизм и объекту не обязательно наследоваться от чего-то, чтобы быть «рисуемым» и достаточно, чтобы для него существовала свободная функция draw. А спрятать разнотипные объекты за единым интерфейсом можно через type erasure, обернув их в обычный тип-значение.
// VOP: object_t это ЗНАЧЕНИЕ, его копируют как int, без всякого наследования class object_t { public: template <typename T> // принимает ЛЮБОЙ тип, у которого есть draw(T, os) object_t(T x) : self_(std::make_shared<model<T>>(std::move(x))) {} friend void draw(const object_t& x, std::ostream& out) { x.self_->draw_(out); // диспетчеризация спрятана внутри } private: struct concept_t { virtual ~concept_t() = default; virtual void draw_(std::ostream&) const = 0; }; template <typename T> struct model final : concept_t { model(T x) : data_(std::move(x)) {} void draw_(std::ostream& out) const override { draw(data_, out); } T data_; }; std::shared_ptr<const concept_t> self_; // обратите внимание: const };
Фокус в том, что object_t ведёт себя как простое значение, а вся возня с виртуальными вызовами спрятана внутри и пользователя не касается. Теперь это не вектор указателей, а вектор значений, и его можно положить в другой контейнер, и не обязательно вектор, вообще куда угодно разделив владение.
using objects_t = std::vector<object_t>; objects_t objects; objects.emplace_back(Circle{}); objects.emplace_back(42); // int рисуемый, если для int есть draw() objects.emplace_back(std::string{"hi"}); objects.emplace_back(objects); // дети это просто значение
Раз object_t это значение, то и история изменений делается тривиально и чтобы запомнить состояние для undo, достаточно скопировать вектор в стек версий, без ручной возни с тем, кто кому владеет и когда удалять.
using history_t = std::vector<document_t>; void commit(history_t& h) { h.push_back(h.back()); } // снимок текущего состояния void undo(history_t& h) { h.pop_back(); } // откат objects_t& current(history_t& h) { return h.back(); }
Возникает резонный вопрос "а копировать-то весь вектор на каждый чих не дорого ли"? Вот тут и выходит на сцену то, ради чего Adobe вообще построила вокруг этого свою стандартную библиотеку. В Stlab для этого есть готовый stlab::copy_on_write<T>, который снаружи ведёт себя как обычное значение, а внутри держит разделяемый неизменяемый буфер и реально копирует данные только в момент первой записи.
Заметьте, в object_t выше указатель именно shared_ptr<const concept_t> и внутренность неизменяема, поэтому копии могут безопасно делить её сколько угодно, а копирование документа это просто инкремент счётчиков ссылок.
Где этот подход применять не стоит, так это в играх. Вот незадача, а такая красивая идея была. Потому что половина мира у тебя это один-единственный экземпляр объекта, вроде реального «игрока» или стула, или навмеша, на который ссылается другие полмира, и важно, чтобы все видели именно его, а копию. Value семантика блестяще подходит для данных (документы, кадры undo, неизменяемые снапшоты, кисти, мазки и действия).
Народные мудрости и война за байты
Материал «C++ Performance: Common Wisdoms and Common "Wisdoms"» это уже прививка от карго-культа и секты EASTL. Там разбираются расхожие советы по производительности и контейнерам STL против EASTL и показывает, какие из них правда, а какие «мудрость» в кавычках, верная только для конкретного компилятора и давно протухшая. Воспринимать его как чеклист «делай 1-2-3» бессмысленно, потому что главный его посыл ровно обратный, в стиле думай и меряй сам.
Доклад «Classes With Many Fields» Станислава Добровольского заходит с другой стороны и показывает на реальных проектах вроде Chromium, Firefox, LLVM, VLC как сокращают размер класса, когда его экземпляров миллионы. В ход идут переупорядочивание полей, padding, ужатие enum, битовые поля, вынос редких данных в отдельную структуру, та самая война за каждый байт, что когда-то шла на консолях, только теперь её ведут уже браузеры. И ровно так же это бессмысленно для класса, которого в системе три штуки, где экономия будет околонулевая, а читаемость пострадает сильно.
Книги, как же без них
Серия Effective Скотта Мейерса, включая Effective STL, это база в духе «делай так, а так не делай», и More C++ Idioms как каталог приёмов вроде RAII, CRTP и copy-and-swap, многие из которых как раз и живут внутри STL и Boost. Единственная оговорка в том, что Effective STL местами устарела, и читать её надо с поправкой на то, что поменялось в C++11/14/17, иначе можно затащить к себе советы, которые человечество уже сделало ненужными.
З.Ы. Если суммировать всю подборку одной мыслью, то она такая: универсальность стандартного STL это компромисс, за который кто-то платит. Обычно этим кто-то оказываешься ты, а платить приходится временем кадра и иногда своим, числом аллокаций и свободных выходых и предсказуемостью, иногда и отпуска. Каждая секта, ой, стандартная библиотека предлагает светлое будущее, но только церковь «профайлинга своих данных» оказывается достойной внимания, советую не пропускать пятничные мессы.
Всем кто добрался до конца страницы небольшой бонус, я поставил цену курса по Нескучному программированию 100р, меньше степик не дает сделать. Так что, если есть желание обновить свои знания, а может и узнать что-то новое, заходите.
