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

[sim0nsays]

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

Comments

[djuffin]

reverse зовут чтобы стало быстрее. В данном случае кто-то захотел сделать "быстрее" еще до того как стало медленно.

[_winnie]

Обычно в таких случаях лучше аналог std::list >, в каждом векторе заранее выделено константное и неменяющееся количество памяти. (list - не копирует элементы при добавлениях новых). Можно заабюзить 64-битное адресное пространство для этого (TLB - std::list, 4kb memory page - std::vector). std::deque примерно так делает, но не измерял его производительность. В моём STL из g++ (Debian 4.4) один блок в std::deque занимает 512 байт.

[zeux]

В STL из MSVC блок в deque занимает кажется max(16, sizeof(T)) байт, достаточно бесполезный контейнер...

[some41]

deque вполне бы мог быть дефолтным контейнером для большого количества случаев, но, увы, им почти никто не пользуется, поэтому его имплементации часто оставляют желать

[sleepy_drago]

его никто не использует именно потому что они не сделали размер блока параметром. хотя бы компиляции.

[some41]

> vector.reserve(vector.size() + 24); - это $#^@* и насморк
+1
человек, который это пишет, не понимает как работает vector. делать reserve в цикле почти всегда тупо.
если хотелось улучшить, то можно было сделать reserve один раз на estimated_number_of_shapes * average_numer_of_vertices_per_shape или что-то такое. хотя и тут можно налететь, что если аллокировал меньше, чем надо, то при resize оно удвоится и станет огромным. а если бы просто без reserve вставлял, то доросло бы до гораздо меньшего размера.

[zeux]

Разница с reserve на estimated когда не угадали и без reserve очень зависит от везения - если совсем нельзя посчитать заранее то наверное оптимально делать reserve(grow(shape_count * avg_vertices_per_shape)), где grow ведет себя так же как внутренний grow (ну и вообще, были бы отдельно reserve и reserve_exact aka reallocate, где reserve(count) = reallocate(grow(count)), и проблем бы не было...

А иначе да, соглашусь, человек который пишет reserve(size() + 24), не знает как реализован vector::reserve в популярных STL. Опять отмечу что с т.з. формальной разницы между reserve(size() + 24) и resize(size() + 24) в скорости быть не обязано - просто так получилось что reserve() exact, а resize() с grow.

[some41]

> Разница с reserve на estimated когда не угадали и без reserve очень зависит от везения
Именно так. Поэтому лучше хорошая дека.

> не знает как реализован vector::reserve в популярных STL
И как работает push_back в любом stl. Возможно он не ожидал квадрата, но зачем было вообще писать reserve? Что он должен был улучшить? Даже если бы он был не exact, то разницы бы не было со второй итерации цикла. Premature optimization как она есть.

[zeux]

Полагаю, что reserve по инерции - в смысле там есть места где вершин не 24 а пара тысяч, и там reserve более оправдан, ну и тут типа за компанию. А вообще я не знаю, автора уже не найти и не спросить - возможно автор просто не думал.

[cd_riper]

поэтому, видать, мудрый дедушка Кармак и навелосипедил свои классы для таких целей, а не взял STL :)

[kunaifusu]

Че там Кармак, сам Степанов говорит "Да вы охуели чтоли коллекции из СТЛ в живой код пихать?!? О_о". Он же их прописал для прикола, чтобы показать что алгоритмы на чем угодно будут работать.

[sim0nsays]

В том и пойнт, что другой реализацией не спасти - думать надо!

[some41]

При программировании надо думать. Breaking news! :-)