Std:: map distribution node упаковка?

Я заметил, что реализация std:: map Visual Studio (2010) выделяет новый единый блок памяти для каждого node в его красно-черном дереве. То есть для каждого элемента карты один новый блок необработанной памяти будет выделяться через operator new ... malloc с помощью схемы распределения по умолчанию для std:: map реализации Visual Studio STL.

Это кажется мне немного расточительным: не имеет смысла выделять узлы в блоках "(small) n", так же как реализация std::vector чрезмерно распределяется на рост?

Итак, я хотел бы пояснить следующие моменты:

Является ли мое утверждение о схеме распределения по умолчанию действительно правильным?
Выполняют ли все "STL-реализации" std:: map таким образом?
Есть ли что-нибудь в std, препятствующее реализации std:: map от размещения его узлов в блоках памяти вместо размещения нового блока памяти (через его распределитель) для каждого node? (Гарантии сложности и т.д.)?

Примечание: речь идет не о преждевременной оптимизации. Если его о оптимизации, то о том, есть ли у приложения проблемы с (фрагментацией памяти памяти std::), существуют ли альтернативы использованию настраиваемого распределителя, который использует пул памяти? Этот вопрос касается не о пользовательских распределителях, а о том, как реализация карты использует свой распределитель. (Или, надеюсь, это так.)

Ответ 1

Ваше утверждение верно для большинства реализаций std:: map.

Насколько я знаю, в стандарте нет ничего, что предотвращало бы использование карты схемы распределения, такой как вы описываете. Однако вы можете получить то, что вы описали, с помощью специального распределителя, но принудительная схема на всех картах может быть расточительной. Поскольку карта не имеет априорных знаний о том, как она будет использоваться, некоторые шаблоны использования могут предотвратить дезадаптацию в основном неиспользуемых блоков. Например, скажем, что блоки были выделены для 4 узлов за раз, но конкретная карта заполнена 40 узлами, а затем удалены 30 узлов, оставив наихудший случай одного node слева на блок, поскольку карта не может аннулировать указатели/ссылки/итераторы к последнему node.

Ответ 2

Когда вы вставляете элементы в карту, это гарантирует, что существующие итераторы не будут аннулированы. Поэтому, если вы вставляете элемент "B" между двумя узлами A и C, которые бывают смежными и внутри одной и той же выделенной области кучи, вы не можете перетасовывать их, чтобы освободить место, а B нужно будет поместить в другое место. Я не вижу в этом каких-либо особых проблем, за исключением того, что управление такими сложностями приведет к разбуханию реализации. Если вы удаляете элементы, то итераторы не могут быть признаны недействительными, что означает, что любое распределение памяти должно зависать до тех пор, пока все узлы в нем не будут стерты. Возможно, вам понадобится freelist в каждом "раздутом node" /vector/whatever -you-want-to-call-it - эффективно дублируя, по крайней мере, некоторые из трудоемких операций, которые в настоящее время делают для вас новый/удалить.

Ответ 3

Я совершенно уверен, что я никогда не видел реализацию std::map, которая пыталась объединить несколько узлов в один блок распределения. По крайней мере, я не могу думать о причине, по которой он не может работать, но я думаю, что большинство разработчиков считают это ненужным и оставляют оптимизацию распределения памяти в распределителе, а не беспокоиться об этом в самом map.

По общему признанию, большинство пользовательских распределителей написаны, чтобы лучше справляться с распределением большого количества небольших блоков. Вероятно, вы могли бы сделать большую часть такой оптимизации ненужной, написав map (и, конечно же, set, multiset и multimap), чтобы вместо этого использовать более крупные распределения. OTOH, учитывая, что распределители для оптимизации распределения небольших блоков легко/общедоступны/широко доступны, вероятно, не так много мотивации для изменения реализации map.

Ответ 4

Я думаю, что единственное, что вы не можете сделать, это аннулировать итераторы, которые вам могут понадобиться, если вам нужно перераспределить ваше хранилище. Сказав это, я видел реализации, используя один отсортированный массив объектов, завернутый в интерфейс std:: map. Конечно, это было сделано по определенной причине.

Фактически, вы можете просто создать экземпляр своей std:: map с помощью пользовательского распределителя, который найдет память для новых узлов специальным, не расточительным образом.

Ответ 5

Это кажется мне немного расточительным. Разве не было бы смысла выделять узлы в блоках "(малых) n", так же, как реализация std::vector переопределяется при росте

Интересно, я вижу это совершенно по-другому. Я считаю, что это уместно, и это не пугает память. По крайней мере, с defaul STL-распределителями в Windows (MS VS 2008), HP-UX (gcc с STLport) и Linux (gcc без STLport). Важно то, что эти распределители действительно заботятся о фрагментации памяти, и, похоже, они справляются с этим вопросом довольно хорошо. Например, найдите Low-fragmentation Heap в Windows или SBA (Малый блок-распределитель) на HP-UX. Я имею в виду, что частое распределение и освобождение памяти только для одного node одновременно не должно приводить к фрагментации памяти. Я тестировал std::map сам в одной из моих программ, и он действительно не вызывал фрагментации памяти с этими распределителями.

Является ли мое утверждение о дефолте правильно ли схема размещения?

У меня есть MS VisualStudio 2008, и его std:: map ведет себя одинаково. В HP-UX я использую gcc с STLport и без него, и похоже, что их STL-карты имеют тот же подход к распределению памяти для узлов в std::map.

есть что-нибудь в std предотвращение реализации std:: map от ввода его узлов в блоки памяти вместо выделения нового блок памяти (через его распределитель) для каждого node?

Начните с настройки распределителя по умолчанию на вашей платформе, если это возможно. Здесь полезно процитировать Дуглас Лиа, который является автором DL- Malloc

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

Однако вскоре я понял, что здание специальный распределитель для каждого нового класса которые, как правило, были динамически распределенный и широко используемый, не был хорошая стратегия при создании видов поддержка общего назначения классы, которые я писал в то время. (С 1986 по 1991 год я был основной автор libg++, GNU С++ библиотеки.) Более широкое решение было необходимо - написать распределитель, который был достаточно хорош при нормальных С++ и C так, чтобы программисты не были соблазн написать специальную распределители, за исключением особо условия.

Или, как чуть более сложная идея, вы даже можете попробовать протестировать свое приложение с помощью распределителя Hoard. Я имею в виду просто проверить ваше приложение и посмотреть, есть ли какая-либо польза от производительности или фрагментации.