Publish @Zeux: Еще раз о выстрелах в ногу и STL

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

Там необходимо ненулевое количество букаф чтобы описать ситуацию, ценителям рекомендуется не скроллить сразу до TL;DR.
Очевидные выводы, разумеется – никому не верить, кроме профайлера, и не бояться лезть в кишки чужого кода, каким “стандартным” бы он ни был. Пишите о неочевидных!


People in this conversation:
Simon Kozlov Add
Engineer at ROBLOX (www.roblox.com), previously at Microsoft. And ClosedCircles was my idea.
Arseny Kapoulkine (Zeux) Add
CREAT Studios, Saber3D, Sperasoft (EA Sports – FIFA). Currently making kids happy at ROBLOX. http://zeuxcg.org/
Ruslan Abdikeev (aruslan) Add
http://aruslan.livejournal.com/tag/pnl
Coding for the food at Google.
Alexandr Poltavsky Add

Zeux: @All
А у меня свежая история про STL! Из разряда “хотели как лучше, а получилось как обычно”.
У нас тут есть килограммы legacy кода которые генерируют геометрию кубиков (и не только).
И есть глобальный флажок, bevels – если он включен, то кубики генерируются со скругленными уголками (надеюсь, Эппл нас не засудит!) – это не 12 треугольников на кубик как привыкли а больше. Если выключен – то, соответственно, просто 12 треугольников на кубик.
Этот флажок можно самому ставить, ну и мы его ставим автоматом в зависимости от того насколько у юзера плохое железо.
И вот – сюрприз! – замеры скорости показали
Что bevels “on” (в пару раз больше геометрии) генерирует структуру из 7к кубиков за 240 мсек
А bevels “off” – за 9.5 секунд O_o
Расследование показало, что тормозит код, который заполняет std::vector<> вершинками.
Код написан в следующем стиле – для каждого кубика зовем функцию, которая делает вектору много push_back.
Чтобы не делать много reallocations (типа, один кубик – это от 24 вершин, 24 push_back = несколько reallocs), кто-то поставил туда reserve, выглядящий вот так:
vector.reserve(vector.size() + 24);
а потом генерация геометрии – либо ровно 24 вершины (bevels off), либо больше (bevels: on – константа 24 в reserve не учитывает bevels, ну и ладно).
Оказывается…
Что vector::reserve(count) устанавливает capacity ровно в count, если ему вообще нужно ее менять.
Т.е. каждый следующий reserve() делает realloc, если reserve(24) а потом 24x push_back
Однако! Если bevels таки включены, то reserve-то на 24 а push_back-ов больше
Поэтому reallocs в основном возникают в push_back
Который умеет растить вектор в 1.5 раза, и квадратичной зависимости скорости не возникает.
Напоследок отмечу, что поведение reserve() одинаковое в MSVC 2008 и в gcc 4.2 (iPad); про остальные платформы не знаю, стандарт такое поведение не навязывает
(наверное это правильно, иначе вектор было бы невозможно заресайзить до точного размера, кроме как сконструировав новый)

Alexandr Poltavsky: reply @Zeux
интересно, а просто массив использовать можно было бы? или использование вектора там как-то имеет смысл?
а вообще замечательный пример на тему недокументированных аллокаций… наверное память всегда надо выводить в входные параметры

Zeux: reply @Alexandr Poltavsky
Размер заранее неизвестен. Т.е. задача выглядит так – есть куча разных шейпов, иногда это кубики с bevels, иногда кубики с форсированно включенными bevels вне зависимости от настроек, иногда сферы, иногда меши итп – надо все это безобразие слить в один VB.
Дальше варианта два – два прохода по данным (подсчет и заполнение) или вектор.
У нас уже есть новый код который очень сильно отличается от старого, и в числе прочего использует два прохода чтобы заполнять прямо VB без вектора и копирований, но он пока поддерживает далеко не все типы шейпов к сожалению.
Зато работает почти в 50 раз быстрее, ыыы (это не связано с векторами, или скажем так связано далеко не только с векторами)

Alexandr Poltavsky: reply @Zeux
понял, спасибо
в таком случае действительно страховаться от такого практически невозможно… даже если снабдить вектор нашим аллокатором

aruslan: reply @Zeux
TD;LR vector.reserve(vector.size() + 24); – это $#^@* и насморк, линейно растить – за такое надо убивать медленно и линейно.

Zeux: reply @aruslan
Отмечу что vector.resize(vector.size() + 24) работает прекрасно.
Т.е. утверждение про reserve сходу неочевидно, я вот не знал деталей реализации на память (в смысле когда reserve видишь в профайлере то понятно что внутрь нужно заглянуть, а когда нет то фиг его знает что оно делает!)

Zeux: reply @Zeux
Особенно приятно что если “починить” код, исправив 24 на значение, зависящее от bevels, то квадратичная скорость будет всегда!

Simon Kozlov: reply @Zeux
Прикольно, я еще не видел, чтобы стреляли в ногу через reserve

This happened on #programming