Почему распределение памяти в куче MUCH медленнее, чем на стеке?

Ответ 1

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

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

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

Ответ 2

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

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

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

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

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

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

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

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

• dlmalloc - Doug Lea malloc, историческая ссылка malloc, используемая в GNU С++ в один момент времени.
• phkmalloc- реализация FreeBSD malloc, написанная автором Poul-Henning Kamp веб-кэша Varnish.
• tcmalloc - Thread-Caching Malloc, реализованный некоторыми разработчиками Google
• jemalloc - реализация Jason Evan malloc для FreeBSD (преемник phkmalloc)

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

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

Ответ 3

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

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