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
Там необходимо ненулевое количество букаф чтобы описать ситуацию, ценителям рекомендуется не скроллить сразу до 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