Производительность кстати. Стек-Heap Динамические массивы

Question

В языках программирования, концепции,

книга Šebesta гласит, что (. Девятую изд, 284):

Недостатком фиксированной кучи-динамических массивов является то, что они занимают больше времени, чтобы выделить массив из стека.

Как мы можем проанализировать это утверждение? В чем разница между фиксированными динамическими динамическими и динамическими массивами. Что означает это фиксированное слово?

Answer 1

Выделение памяти из стека очень просто. Вам просто нужно настроить указатель стека. На x64, это одна команда:

sub rsp, size 

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

Re "fixed", так как у меня нет книги, я не знаю, в каком контексте она использует это слово. Вероятно, это означает, что массив не будет перемещаться в кучу после выделения.

Answer 2

Если кучу можно выращивать для размещения каждого нового распределения, то создание массива может быть быстрым. Если куча «фиксирована», нам нужно найти место внутри кучи, и, как объяснил Мехрдад, это требует нетривиальной работы.

Я не совсем разобрать конец фразы, хотя:

Недостатком фиксированной кучи-динамических массивов является то, что они занимают больше времени, чтобы выделить массив из стека.

Вы не выделяете кучную память «из стека».

Answer 3

терминологии исходит из трех ортогональных понятий:

• ли размер массива может измениться после его первоначального распределения, или остается тем же размером навсегда, «фиксированный».
• Где находится массив: стек или куча памяти.
• Если размер распределения определяется во время выполнения «динамический» или время компиляции.

Answer 4

Ответ от ergosys имеет терминологию точно вправо. Вопрос - еще один пример того, почему я ненавижу Себесто.

Во многих современных системах выделение объекта из кучи использует точно такие же инструкции, как выделение из стека: проверка и увеличение указателя кучи. (Это правда, что легче объединить распределения стека, чем комбинировать выделение кучи, но может быть сделано тоже.) Компиляторы, которые выполняют такой вид выделения, включают Glorious Glasgow Haskell Compiler и Standard ML of New Jersey. SML/NJ был развернут в этом состоянии уже более 20 лет, так что вы думаете, что Sebesta, возможно, подобрала его к настоящему времени.

Основная информация: Sebesta overgeneralizing, как обычно.Могут быть причины предпочесть распределение стека, но история намного сложнее, чем кажется, кажется, Sebesta, или Мехрдад описывает в своем ответе. Хорошее место, чтобы начать с понимания более глубокой истории с Andrew Appel's paper about stack allocation.