Почему выделение памяти в куче НАМНОГО медленнее, чем в стеке?

Question

Мне говорили это много раз. Но я не знаю, ПОЧЕМУ ... Какие дополнительные затраты связаны с выделением памяти из кучи? Это связано с аппаратным обеспечением? Это связано с циклами процессора? Так много догадок, но нет точных ответов ... Может кто-нибудь дать мне какую-нибудь разработку?

Как сказал «раскрутить», структура данных Heap сложнее, чем Stack. И, на мой взгляд, некоторое пространство памяти выделяется потоку как его стеку, когда он начинает работать, в то время как куча используется всеми потоками в процессе. Эта парадигма требует некоторого дополнительного механизма для управления использованием общей кучи каждым потоком, такого как сборка мусора. Я прав в этом?

Answer 1

Поскольку куча является гораздо более сложной структурой данных, чем стек.

Для многих архитектур выделение памяти в стеке - это просто вопрос изменения указателя стека, т.е. это одна инструкция. Выделение памяти в куче включает в себя поиск достаточно большого блока, его разбиение и управление «бухгалтерским учетом», который позволяет использовать такие вещи, как free() в другом порядке.

Память, выделенная в стеке, гарантированно освобождается при выходе из области (как правило, из функции), и невозможно освободить только часть из нее.

Answer 2

В своем редактировании, где вы повторяете ответ раскрутки, вы упоминаете «структуру данных кучи». Будьте очень осторожны, так как структура данных, известная как heap , не имеет отношения к динамическому распределению памяти. Чтобы быть очень ясным, я буду использовать более терминологию языкового адвоката бесплатный магазин .

Как уже указывалось, для выделения стека требуется увеличение указателя, который обычно имеет выделенный регистр на большинстве архитектур, а освобождение требует одинакового объема работы. Распределение стека также ограничено определенной функцией. Это делает их гораздо более подходящими кандидатами для оптимизации компилятора, например, для предварительного вычисления общего пространства, необходимого в стеке, и выполнения одного приращения для всего кадра стека. Аналогично, стек имеет лучшую гарантированную локальность данных. Вершина стека почти всегда гарантированно находится внутри строки кэша, и, как я уже говорил, указатель стека обычно хранится в регистре. Оптимизация компиляторов на некоторых архитектурах может даже полностью исключить выделения в стеке путем повторного использования аргументов из предыдущих кадров стека, которые передаются в качестве аргументов вызываемым функциям в более глубоких кадрах стека. Аналогично, переменные, выделенные из стека, часто можно преобразовать в регистры, избегая при этом выделения.

Напротив, бесплатный магазин намного более сложный. Я даже не собираюсь рассказывать о системах сбора мусора, поскольку это совершенно другая тема, и этот вопрос был задан о языке Си. Обычно выделения и освобождения из свободного хранилища включают несколько различных структур данных, таких как свободный список или пул блоков. Эти структуры данных и бухгалтерия также требуют памяти, и, таким образом, это пространство теряется. Кроме того, бухгалтерские записи часто смешиваются с распределениями и, таким образом, нарушают локальность данных других распределений. Распределение из свободного хранилища может включать запрос базовой операционной системы на дополнительную память процесса, как правило, из какой-либо формы распределителя slab.

Для простого сравнения и использования jemalloc-2.2.5 и чисел из sloccount в качестве эталона реализация jemalloc содержит более 8 800 строк исходного кода на языке C и еще более 700 строк тестового кода. Это должно дать вам хорошее представление о разнице в сложности между бесплатным распределением хранилища и выделением стека: тысячи строк кода на языке C против одной инструкции.

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

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

В современных системах стеки часто относительно невелики по сравнению со свободным хранилищем, поэтому в конечном итоге бесплатный склад занимает больше места и, таким образом, решает более сложную проблему. Кроме того, из-за ограничений размеров стеков свободное хранилище обычно используется для больших выделений, это несоответствие между необходимостью обрабатывать как очень большие, так и очень маленькие выделения также усложняет работу свободного хранилища. Обычно выделение стека невелико, порядка нескольких килобайт или менее, а общий размер стека составляет всего несколько мегабайт. Свободному хранилищу обычно дается всего остального пространства процесса в программе. На современных машинах это может быть несколько сотен гигабайт, и нередко размеры свободного хранилища могут варьироваться от нескольких байтов, таких как короткая строка символов, до мегабайт или даже гигабайт произвольных данных. Это означает, что распределителям свободных хранилищ приходится иметь дело с управлением виртуальной памятью базовой операционной системы. Распределение стеков по существу встроено в компьютерное оборудование.

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

• dlmalloc - malloc Дуга Ли, историческая справочная реализация malloc, используемая в GNU C ++ в определенный момент времени
• phkmalloc - реализация malloc во FreeBSD, написанная Poul-Henning Kamp, автором веб-кэша Varnish
• tcmalloc - Malloc для кэширования потоков, реализованный некоторыми разработчиками Google
• jemalloc - реализация malloc Джейсона Эвана для FreeBSD (преемник phkmalloc)

Вот несколько дополнительных ссылок с описаниями реализации tcmalloc:

• http://jamesgolick.com/2013/5/15/memory-allocators-101.html
• http://jamesgolick.com/2013/5/19/how-tcmalloc-works.html

Answer 3

Основное различие между стеком и кучей состоит в том, что элементы в стеке не могут быть удалены не по порядку. Если вы добавляете элементы A, B, C в стек, вы не можете удалить B, не удалив сначала C. Это означает, что добавление нового элемента в стек всегда означает добавление его в end стека, что является очень простой операцией. Вы просто перемещаете указатель, указывающий на конец стека.

С другой стороны, в куче вы можете удалять предметы не по порядку. И до тех пор, пока вы не перемещаете другие элементы в памяти (как это делают некоторые кучи мусора), ваша куча имеет «дыру» в середине. То есть если вы добавляете A, B, C в кучу и удаляете B, ваша куча в памяти выглядит следующим образом: A _ C, где _ - блок неиспользованной (свободной) памяти. Если вы добавите новый элемент D сейчас, распределитель должен найти непрерывное свободное пространство, достаточно большое для размещения D. В зависимости от того, сколько в вашей памяти непрерывных свободных пространств, это может быть дорогостоящей операцией. И это почти всегда дороже, чем просто перемещение указателя «последнего элемента» в стеке.