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

Ответ 1

Распределители имеют тенденцию быть довольно сложными и часто значительно различаются в том, как они реализованы.

Вы не можете описать их с точки зрения одной общей структуры данных или алгоритма, но есть некоторые общие темы:

• Память берется из системы в больших кусках - часто мегабайт за раз.
• Эти куски затем разбиваются на различные мелкие куски при выполнении распределений. Не точно такой же размер, как вы выделяете, но обычно в определенных диапазонах (200-250 байт, 251-500 байт и т.д.). Иногда это многоуровневое, где у вас будет дополнительный слой "средних кусков", который приходит перед вашими фактическими запросами.
• Контроль того, какой "большой кусок", чтобы сломать кусок, - очень сложная и важная вещь, - это сильно влияет на фрагментацию памяти.
• Для каждого из этих диапазонов поддерживаются один или несколько бесплатных пулов ( "бесплатный список", "пул памяти", "список просмотра" ). Иногда даже поточно-локальные пулы. Это может значительно ускорить шаблон выделения/деаллокации многих объектов аналогичного размера.
• Большие распределения обрабатываются немного по-другому, чтобы не тратить много ОЗУ и не собираться так сильно, если вообще.

Если вы хотите проверить какой-то исходный код, jemalloc является современным высокопроизводительным распределителем и должен быть репрезентативным по сложности других распространенных. TCMalloc - еще один распространенный универсальный распределитель, и их веб-сайт входит во все детали реализации gory. Intel Блоки для построения потоков имеет распределитель, созданный специально для высоких concurrency.

Можно заметить одно интересное различие между Windows и * nix. В * nix распределитель имеет очень низкий уровень контроля над адресным пространством, которое использует приложение. В Windows у вас в основном есть конечный, медленный распределитель VirtualAlloc, чтобы скомпилировать ваш собственный распределитель.

Это приводит к * nix-совместимым распределителям, которые обычно предоставляют вам реализацию malloc/free, где предполагается, что вы будете использовать только один распределитель для всего (иначе они будут попирать друг друга), в то время как Windows- специальные распределители предоставляют дополнительные функции, оставляя только malloc/free и могут использоваться в гармонии (например, вы можете использовать HeapCreate для создания частных куч, которые могут работать вместе с другими). ​​

На практике эта торговля гибкостью дает * nix allocators небольшую ногу по производительности. Очень редко можно увидеть, что приложение намеренно использует множественные кучи в Windows - в основном это случайно из-за разных DLL, использующих разные временные ряды, каждый из которых имеет свой собственный malloc/free, и может вызвать много головных болей, если вы не прилежно следя за тем, из какой кучи пришла память.

Ответ 2

Примечание. Следующий ответ предполагает, что вы используете типичную современную систему с виртуальной памятью. Стандарты C и С++ не требуют виртуальной памяти; поэтому, конечно, вы не можете полагаться на такие предположения на аппаратное обеспечение без этой функции (например, у графических процессоров обычно нет этой функции, а также не очень мало аппаратных средств, таких как PIC).

Это зависит от платформы, которую вы используете. Кучи могут быть очень сложными животными; они не используют только одну структуру данных; и нет "стандартной" структуры данных. Даже там, где находится код кучи, в зависимости от платформы. Например, код кучи обычно предоставляется блоками C Runtime on Unix; но обычно предоставляется операционной системой Windows.

• Да, это распространено на машинах Unix; из-за того, как работают * nix базовые API и модель памяти. В принципе, стандартный API для возврата памяти в операционную систему на этих системах позволяет только вернуть память на "границу" между тем, где выделена пользовательская память, и "дырой" между пользовательской памятью и системными средствами, такими как стек. (В рассматриваемом API brk или sbrk). Вместо того, чтобы возвращать память в операционную систему, многие кучи только пытаются повторно использовать память, которая больше не используется самой программой, и не пытайтесь вернуть память в систему. Это реже встречается в Windows, поскольку его эквивалент sbrk (VirtualAlloc) не имеет этого ограничения. (Но, как и sbrk, он очень дорог и имеет оговорки, например, только выделение блоков размера страницы и выравнивания по страницам. Таким образом, кучи пытаются вызвать либо как можно реже)
• Это звучит как "блок-распределитель", который делит память на куски фиксированного размера, а затем просто возвращает один из свободных фрагментов. Для моего (хотя и ограниченного) понимания Windows 'RtlHeap поддерживает ряд структур данных, подобных этому для разных известных размеров блоков. (Например, у него будет один для блоков размером 16, например) RtlHeap вызывает эти "списки просмотра".
• Я действительно не знаю конкретной структуры, которая хорошо справляется с этим случаем. Большие блоки являются проблематичными для большинства систем распределения, поскольку они вызывают фрагментацию адресного пространства.

Лучшая ссылка, которую я нашел, обсуждая общие стратегии распределения, используемые на основных платформах, - это книга Защищенное кодирование на C и С++, автор Robert Seacord. Вся глава 4 посвящена структурам данных кучи (и проблемам, возникающим при неправильном использовании упомянутых систем кучи).