Зачем нам куча, если в стеке все можно сделать намного эффективнее?

24

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

Однако во многих ответах указывалось, что стек незаменим из-за того, что во много сотен (или тысяч) раз быстрее, чем попытка выделить / сослаться на кучу. Я знаю, что есть проблема с динамическим распределением памяти, если мы покончили с кучей, но нет ли способа обойти это или, возможно, способ улучшить стек, чтобы он мог обрабатывать динамическое распределение памяти?

Темный тамплиер
источник
4
Два отрывка из вашего предыдущего вопроса: «самый главный недостаток в том, что он имеет ограниченное пространство, и поэтому держать в нем крупные объекты или пытаться использовать его для долгоживущих объектов - плохие идеи», а «стеки чрезвычайно эффективны структура для управления данными, которая подчиняется правилам LIFO (последний пришел первым вышел).
Каскабель
2
Ваша предпосылка ошибочна - не все может быть сделано намного более эффективно в стеке. Это не противоречит полученным вами ответам - что то, что можно сделать в стеке, можно сделать гораздо быстрее.
Инго
... при условии, что ваше оборудование имеет стек или относительную к стеку адресацию.
Ритч Мелтон
3
Я убеждена. Я говорю, сделай это.
Джефф

Ответы:

25

Проблема со стеками заключается в том, что вы не можете «освободить» память, если она не находится на вершине стека. Например, скажем, вы выделили 3 вещи разных размеров:

a = allocate(2000000); // 2000000 bytes
b = allocate(1);
c = allocate(5000000);

Стек будет располагаться aвнизу, bпосередине и cсверху. Это становится проблематичным, если мы хотим освободить b:

free(b); // b is not on top! We have to wait until c is freed!

Обходной путь - переместить все данные после bи сдвинуть, если это так, после a. Это работает, но в этом случае потребуется 5000000 копий - что будет намного медленнее, чем куча.

Вот почему у нас куча. Хотя выделение может быть медленнее, чем стек ( O(log n)vs O(1)), кучи позволяют быстро освобождать память в произвольном месте - O(log n)по сравнению со стекомO(n)

Pubby
источник
4
С этим связано то, что Facebook не удаляет контент со своего диска, когда вы просите его удалить его, он просто удаляет указатель на него. Очевидно, что при дефрагментации или попытке найти эквивалентный пробел на диске слишком много времени занимает скорость записи данных, поэтому они просто добавляют все в верхнюю отметку диска.
Пол Томблин
Ну, диски Facebook можно рассматривать как кучу. И я почти уверен, что у них есть какая-то сборка мусора для этих дисков.
Deadalnix
2
@deadalnix На самом деле это пример использования огромного стека вместо кучи, которая обычно используется для больших объемов памяти. Facebook - это особый случай. Данные добавляются намного быстрее, чем они удаляются, так что освобождение не имеет существенного значения для скорости роста - вы можете сознательно включать утечки памяти в проект, чтобы получить такое распределение O (1).
Том Кларксон
7
@PaulTomblin Основная причина, по которой FB не удаляет контент, заключается в том, что они могут добывать его для своей выгоды ...
quant_dev
5
Facebook doesn't remove content from its disk when you ask it to remove it, it just removes the pointer to it- По сути, это то, что происходит, когда вы делаете обычное удаление файла в любой операционной системе.
Роберт Харви
5

Стек для каждого потока, куча для всего процесса

Если все 100 рабочих потоков обрабатывают все рабочие элементы, которые я помещаю в очередь, то где именно я могу разместить рабочие элементы таким образом, чтобы любой из 100 потоков мог их видеть?

Есть и другие виды памяти, тоже

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

JBRWilkinson
источник
4

Стек - это структура LIFO («последний пришел - первым вышел»), в верхней части которой хранится ссылочный указатель (обычно поддерживаемый аппаратными средствами). Сказав это, все, что вы пытаетесь выделить в стеке вместо кучи, должно быть локальной переменной в каждой функции, находящейся наверху этого стека. Итак, основная причина для стека состоит в том, что вашей подпрограмме main () нужно было бы заранее выделить все структуры данных, которые ваша программа использует (которые предназначены для использования в течение всей продолжительности вашей программы) заблаговременно, так как все структуры данных распределены вызовы функций в конечном итоге будут удалены, когда эти вызовы функций вернутся, а их кадры или записи активации будут вытеснены из стека.

Alex
источник
3
ЛИФО, а не ФИФО.
Пабби
иногда также называется FILO;)
oenone
3

Стеки отлично работают для распределения памяти, которое соответствует правилам «первым пришел - первым обслужен» (LIFO), то есть вы освобождаете память в том же порядке, в котором вы ее выделяете. LIFO - это очень распространенный, возможно, самый распространенный шаблон распределения памяти. Но это не единственный шаблон или даже единственный общий шаблон. Чтобы написать эффективную программу, которая может решать широкий спектр задач, мы должны учитывать менее распространенные модели, даже если это означает более сложную инфраструктуру.

Если я могу получить все мета для абзаца: вы новичок, как новичок вы цените простоту и черно-белые правила. Тем не менее, как новичок, у вас есть только взгляд из ряда проблем и ограничений, которые должны быть учтены компьютерными программами. Вы вводите технологию, которая активно развивается уже 75 лет. Нет ничего плохого в том, чтобы спросить, почему все так, как есть, но ответ, как правило, будет таким: «Да, мы попробовали простой, прямой метод 50 лет назад, и оказалось, что он не очень хорошо работает для целых классов». проблем, поэтому нам пришлось сделать что-то более сложное ". По мере развития технологии простота обычно должна уступать эффективности и гибкости.

Чарльз Э. Грант
источник
0

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

скоро
источник
0

Среди многих других причин для выделения кучи памяти.

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

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

Джеймс Андерсон
источник