¿Por qué necesitamos un montón si todo se puede hacer de manera mucho más eficiente en la pila?

24

En realidad, esto está algo relacionado con la pregunta que hice ayer acerca de por qué tanto un Stack como un Heap son necesarios en las aplicaciones que usamos hoy (y por qué no podemos simplemente usar un Heap en lugar de ambos, para tener un estándar singular para ir).

Sin embargo, muchas de las respuestas indicaron que una pila es insustituible debido al hecho de que es cientos (o miles) de veces más rápido que intentar asignar / hacer referencia al montón. Sé que hay un problema con la asignación dinámica de almacenamiento si eliminamos el montón, pero ¿no hay una forma de evitar esto, o tal vez, una forma de mejorar la pila para que pueda manejar la asignación dinámica de memoria?

Templario oscuro
fuente
44
Dos extractos de su pregunta anterior: "el inconveniente más importante es que tiene un espacio limitado, por lo que mantener objetos grandes en él o tratar de usarlo para objetos de larga duración son malas ideas" y "las pilas son extremadamente eficientes estructura para administrar datos que obedecen las reglas LIFO (último en entrar, primero en salir) ".
Cascabel
2
Su premisa es defectuosa: no todo se puede hacer de manera mucho más eficiente en la pila. Esto no es una contradicción con las respuestas que recibió: que lo que se puede hacer en la pila se puede hacer mucho más rápido allí.
Ingo
... suponiendo que su hardware tenga una pila o direccionamiento relativo a la pila.
Ritch Melton
3
Estoy convencido. Yo digo que lo hagas.
JeffO

Respuestas:

25

El problema con las pilas es que no puedes "liberar" memoria a menos que esté encima de la pila. Por ejemplo, supongamos que asignó 3 cosas de diferentes tamaños:

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

La pila tendría aen la parte inferior, ben el medio y cen la parte superior. Esto se vuelve problemático si queremos liberar b:

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

La solución consiste en mover todos los datos después by cambiar si es así para que vengan después a. Esto funciona, pero requerirá 5000000 copias en este caso, algo que será mucho más lento que un montón.

Por eso tenemos un montón. Si bien la asignación puede ser más lenta que una pila ( O(log n)vs O(1)), los montones permiten que la memoria en una ubicación arbitraria sea rápida O(log n), en comparación con la de una pilaO(n)

Pubby
fuente
44
Relacionado con esto, Facebook no elimina el contenido de su disco cuando le pide que lo elimine, solo elimina el puntero. Evidentemente, la sobrecarga de tratar de desfragmentar o tratar de encontrar la brecha equivalente en el disco lleva demasiado tiempo a la velocidad con la que escriben datos, por lo que simplemente agregan todo en la marca de agua más alta del disco.
Paul Tomblin
Bueno, los discos de Facebook pueden verse como un montón. Y estoy bastante seguro de que tienen algún tipo de recolección de basura para estos discos.
deadalnix
2
@deadalnix En realidad, ese es un ejemplo de uso de una gran pila en lugar del montón que normalmente se usa para grandes cantidades de memoria. Sin embargo, Facebook es un caso especial. Los datos se agregan mucho más rápido de lo que se eliminan, por lo que la desasignación no hace una diferencia significativa en la tasa de crecimiento: puede incluir deliberadamente pérdidas de memoria en el diseño para obtener esa asignación O (1).
Tom Clarkson
77
@PaulTomblin La razón principal por la que FB no elimina el contenido es para que puedan
extraerlo
55
Facebook doesn't remove content from its disk when you ask it to remove it, it just removes the pointer to it- Que es esencialmente lo que sucede cuando haces una eliminación ordinaria de un archivo en cualquier sistema operativo.
Robert Harvey
5

La pila es por subproceso, el montón es todo el proceso

Si tengo 100 subprocesos todos los elementos de trabajo de procesamiento que pongo en una cola, ¿exactamente dónde asigno los elementos de trabajo para que cualquiera de los 100 subprocesos pueda verlos?

También hay otros tipos de memoria.

Por ejemplo, archivos mapeados en memoria, memoria compartida, E / S mapeadas (modo kernel). El argumento de la eficiencia es algo discutible en estas situaciones.

JBRWilkinson
fuente
4

Una pila es una estructura LIFO (último en entrar, primero en salir), en la parte superior de la cual se mantiene un puntero de referencia (generalmente soportado por hardware). Dicho esto, todo lo que intente asignar en la pila en lugar del montón debería ser una variable local en cada función, en la parte superior de esta pila. Por lo tanto, la razón principal en contra de una pila es que su rutina main () necesitaría preasignar todas las estructuras de datos que utiliza su programa (que están destinadas a estar disponibles durante toda la duración de su programa) con anticipación, ya que todas las estructuras de datos asignadas dentro de las llamadas a funciones eventualmente se eliminarán cuando esas llamadas a funciones regresen y sus marcos o registros de activación salgan de la pila.

Alex
fuente
3
LIFO, no FIFO.
Pubby
a veces también llamado FILO;)
enone
3

Las pilas funcionan muy bien para las asignaciones de memoria que obedecen las reglas Last in First out (LIFO), es decir, libera la memoria en el orden inverso exacto en que la asigna. LIFO es un patrón de asignación de memoria muy común, quizás el más común. Pero no es el único patrón, o incluso el único patrón común. Para escribir un programa eficiente que pueda abordar una amplia variedad de problemas, tenemos que tener en cuenta los patrones menos comunes, incluso si esto significa una infraestructura más compleja.

Si puedo obtener todos los meta para un párrafo: eres un principiante, como principiante valoras la simplicidad y las reglas en blanco y negro. Sin embargo, como principiante, solo tiene una vista de mirilla del rango de problemas y limitaciones que los programas de computadora deben tener en cuenta. Está ingresando a una tecnología que ha estado en desarrollo activo durante 75 años. No hay nada de malo en preguntar por qué las cosas son como son, pero la respuesta generalmente será "Sí, probamos el método simple y directo hace 50 años, y resultó que no funcionó muy bien para clases enteras de problemas, así que tuvimos que hacer algo más complicado ". A medida que avanza la tecnología, la simplicidad generalmente debe dar paso a la eficiencia y la flexibilidad.

Charles E. Grant
fuente
0

Para otro ejemplo, cierres. Si apila pop, entonces puede perder el registro de activación de su cierre. Entonces, si desea que esa función anónima y sus datos persistan, debe almacenarla en otro lugar que no sea la pila de tiempo de ejecución.

luego
fuente
0

Entre muchas otras razones para asignar el almacenamiento dinámico.

Si desea pasar la dirección de un objeto a un programa de llamada, no debe pasar la dirección de una variable de la pila, ya que el almacenamiento de la pila será reutilizado y posiblemente sobrescrito por la siguiente función llamada. Debe obtener el almacenamiento requerido usando malloc () para asegurarse de que no se sobrescriba con llamadas a funciones posteriores.

Puede pasar las direcciones de los elementos de la pila de su función a las funciones que llame, porque puede garantizar que existirán hasta que su programa "regrese ()". Pero tan pronto como su función regrese, todo el almacenamiento de la pila estará disponible.

James Anderson
fuente