Что делает Схему на основе кучи более медленной, чем Схема на основе стека?

Question

Я разрабатываю компилятор для языка, похожего на Scheme, и читаю диссертацию Дибвига. В нем он говорит, что добился большей части своего прироста производительности, выделяя кадры вызовов в стеке, а не в куче. Есть несколько трюков, которые нужно сделать, чтобы реально сделать эту работу при наличии замыканий и продолжений.

Мой вопрос: откуда взялась эта производительность? Это только потому, что мы меньше загружаем сборщик мусора?

Другими словами: при условии, что у нас бесконечный объем памяти, будет ли стек выделенных кадров вызовов по-прежнему быстрее, чем выделенные кадры вызовов?

Answer 1

Я думаю, что Илай ответил на ваш вопрос, поэтому я собираюсь вставить его комментарий сюда и получить кредит за него:).

Эли Барзилай пишет:

(a) работа с кучей занимает больше времени, так как требует ее сканирования (она не линейная, как стек); (б) практически все архитектуры процессоров делают особый акцент на максимально быстром доступе к стеку, а не на куче.

К этому я бы добавил общие пометки о местонахождении кэша. То есть стек хранит все действия в очень маленькой части памяти, которая почти наверняка останется в кэше.

Answer 2

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