std :: map узел размещения упаковки?

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

Когда вы вставляете элементы в карту, гарантируется, что существующие итераторы не будут признаны недействительными. Поэтому, если вы вставите элемент «B» между двумя узлами A и C, которые оказываются смежными, и внутри одной и той же выделенной области кучи, вы не сможете переместить их, чтобы освободить место, и B придется поместить в другое место. Я не вижу какой-либо конкретной проблемы с этим, за исключением того, что управление такими сложностями будет раздувать реализацию. Если вы удаляете элементы, итераторы также не могут быть признаны недействительными, что подразумевает, что любое выделение памяти должно зависать, пока все узлы в нем не будут удалены. Вам, вероятно, понадобится свободный список в каждом «набухшем узле» / векторе / что угодно, что вы хотите вызвать - эффективно дублируя, по крайней мере, некоторые из трудоемких операций, которые new / delete в настоящее время делает для вас. *

Answer 3

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

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

Answer 4

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

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

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

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

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

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

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

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

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

Answer 5

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

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