¿Qué hace que un Esquema basado en el montón sea más lento que un Esquema basado en la pila?

Question

Estoy desarrollando un compilador para un lenguaje similar a Scheme, y estoy leyendo la tesis de Dybvig. En él, dice que logró la mayor parte de su ganancia de rendimiento al asignar marcos de llamadas en la pila en lugar de en el montón. Hay varios trucos que deben hacerse para hacer que esto funcione en presencia de cierres y continuaciones.

Mi pregunta es de dónde viene esta ganancia de rendimiento? ¿Es puramente porque ponemos menos tensión en el recolector de basura?

Dicho de otra manera: suponiendo que tenemos una cantidad infinita de memoria, ¿la pila de marcos de llamadas asignados seguiría siendo más rápida que los marcos de llamadas asignados?

Answer 1

Creo que Eli respondió su pregunta, así que voy a pegar aquí su comentario y obtener crédito por ello :).

Eli Barzilay escribe:

(a) tratar con el montón toma más tiempo, ya que requiere el análisis, se (no es lineal como la pila); (b) Prácticamente todas las arquitecturas de CPU ponen énfasis adicional en hacer que el acceso a la pila sea lo más rápido posible, y no así en el montón.

A esto, agregaría agitar a mano en general sobre la localidad de caché. Es decir, una pila mantiene toda la acción en una parte muy pequeña de la memoria, que permanecerá casi definitivamente en la memoria caché.

Answer 2

Appel escribió un paper alegando que la asignación del montón puede ser más rápida que la asignación de la pila. Matemáticamente es correcto, pero ignora cómo los procesadores modernos se adaptan al código en ejecución que usa una pila (localidad de caché, instrucciones de pila eficiente, etc.) y que los accesos de montón tienen más indirecciones (mal en las CPU modernas).