(Это не программирование игры само по себе, но я уверен, что если бы я спросил об этом на ТАК, мне сказали бы не преждевременно оптимизировать, хотя история говорит нам, что каждая большая игра заканчивает тем, что беспокоится об этих вещах.)
Существует ли документ, в котором обобщены различия в производительности и, в частности, в использовании памяти между различными реализациями стандартной библиотеки C ++? Детали некоторых реализаций защищены NDA, но сравнение между даже STLport против libstdc ++ против libc ++ против MSVC / Dinkumware (против EASTL?) Кажется очень полезным.
В частности, я ищу ответы на такие вопросы, как:
- Сколько накладных расходов памяти связано со стандартными контейнерами?
- Какие контейнеры, если они есть, выполняют динамическое распределение, просто будучи объявленными?
- Делает ли std :: string копирование при записи? Оптимизация коротких строк? Канаты?
- Использует ли std :: deque кольцевой буфер или это дерьмо?
deque
всегда было реализовано в STL с вектором.Ответы:
В случае, если вы не найдете такой диаграммы сравнения, альтернативой является добавление собственного распределителя в рассматриваемые классы STL и добавление некоторой регистрации.
Реализация, которую я тестировал (VC 8.0), не использует выделение памяти, просто объявляя строку / вектор / deque, но для него есть список и отображение. Строка имеет короткую строковую оптимизацию, так как добавление 3 символов не вызывает выделения. Вывод добавляется под кодом.
На данный момент VC8 и STLPort 5.2 протестированы, вот сравнение (включено в тест: строка, вектор, deque, list, map)
Выходная строка VC8 / вектор / deque / list / map:
STLPort 5.2. вывод скомпилирован с VC8
Результаты EASTL , нет доступной deque
источник
std::string
не делает копирование при записи. Раньше CoW был оптимизацией, но как только несколько потоков входят в изображение, это выходит за рамки пессимизации - это может замедлить код из-за огромных факторов. Это так плохо, что стандарт C ++ 0x активно запрещает это как стратегию реализации. Не только это, но вседозволенностьstd::string
изменчивых итераторов и ссылок на символы означает, что «запись» дляstd::string
влечет за собой почти каждую операцию.Я полагаю, что оптимизация коротких строк составляет около 6 символов или что-то в этом регионе. Канаты не допускаются -
std::string
должны хранить непрерывную память дляc_str()
функции. Технически, вы могли бы поддерживать непрерывную нить и веревку в одном классе, но никто никогда не делал этого. Более того, из того, что я знаю о веревках, сделать их поточнобезопасными для манипуляции было бы невероятно медленно - возможно, так же плохо или хуже, чем CoW.Ни один контейнер не выполняет выделение памяти, будучи объявленным в современных STL. Контейнеры на основе узлов, такие как list и map, использовали для этого, но теперь они имеют встроенную конечную оптимизацию и не нуждаются в ней. Обычно выполняется оптимизация, называемая «swaptimization», когда вы меняете местами пустой контейнер. Рассмотреть возможность:
Конечно, в C ++ 0x это избыточно, но в C ++ 03 тогда, когда это обычно используется, если MahVariable выделяет память при объявлении, тогда это снижает эффективность. Я точно знаю, что это было использовано для более быстрого перераспределения контейнеров, таких как
vector
в MSVC9 STL, что избавило от необходимости копировать элементы.deque
использует что-то, что называется развернутым связанным списком. Это в основном список массивов, обычно в узле фиксированного размера. Таким образом, для большинства применений он сохраняет преимущества как смежного доступа к структурам данных, так и удаления амортизированного O (1), а также возможность добавления как к передней, так и к задней части, и лучшей аннулирования итераторов, чемvector
.deque
никогда не может быть реализовано вектором из-за его алгоритмической сложности и гарантий недействительности итераторов.Сколько накладных расходов памяти связано? Ну, честно говоря, это немного бесполезный вопрос. Контейнеры STL спроектированы так, чтобы быть эффективными, и если бы вы копировали их функциональные возможности, вы либо получили бы что-то, что работает хуже, либо снова в том же месте. Зная их базовые структуры данных, вы можете узнать, какие накладные расходы памяти они используют, дают или отбирают, и это будет только больше, чем по уважительной причине, такой как оптимизация небольших строк.
источник
std::string
раньше. Для этого вам не нужно использовать новейшие и лучшие реализации STL. msdn.microsoft.com/en-us/library/22a9t119.aspx говорит: «Если элемент вставлен спереди, все ссылки остаются действительными». Не уверен, как вы собираетесь реализовать это с циклическим буфером, так как вам нужно будет изменить размер, когда он будет заполнен.Если это действительно ваш вопрос (который, безусловно, нет тому, что вы сказали в тексте вашего фактического вопроса, который закончился 4 вопросами, ни один из которых не спрашивал, где вы можете найти ресурс), тогда ответ будет простым:
Там нет ни одного.
Большинству программистов на C ++ не нужно сильно беспокоиться о накладных расходах стандартных библиотечных структур, о производительности их кеша (что очень любом случае зависит от компилятора) или подобных вещах. Не говоря уже о том, что вы обычно не выбираете стандартную реализацию библиотеки; вы используете то, что поставляется с вашим компилятором. Так что, даже если он делает некоторые неприятные вещи, варианты альтернатив ограничены.
Конечно, есть программисты, которым не безразличны подобные вещи. Но все они давным-давно клялись в использовании стандартной библиотеки.
Итак, у вас есть одна группа программистов, которым просто все равно. И еще одна группа программистов, которым было бы все равно, если бы они ее использовали, но, поскольку они ею не пользуются, им все равно. Поскольку никто не заботится об этом, нет никакой реальной информации об этом. Здесь и там есть неофициальные участки информации (в Effective C ++ есть раздел, посвященный реализациям std :: string и огромным различиям между ними), но они не являются исчерпывающими. И, конечно, ничего не обновлялось.
источник