sistemas - ¿Por qué la asignación de memoria en el montón MUCHO más lento que en la pila?

siguiente ajuste sistemas operativos (3)

En su edición, donde reafirma la respuesta de desenrollar, menciona la "estructura de datos del montón". Tenga mucho cuidado ya que la estructura de datos conocida como un heap no tiene relación con la asignación de memoria dinámica. Para ser muy claro, usaré la terminología de abogado de idioma de la tienda gratuita .

Como ya se ha señalado, la asignación de pila requiere incrementar un puntero, que normalmente tiene un registro dedicado en la mayoría de las arquitecturas y la desasignación requiere la misma cantidad de trabajo. Las asignaciones de pila también tienen un alcance para una función particular. Esto los hace candidatos mucho mejores para las optimizaciones del compilador, como precomputar el espacio total necesario en la pila y hacer un solo incremento para un marco de pila completo. Del mismo modo, la pila tiene una localidad de datos mejor garantizada. La parte superior de la pila casi siempre está garantizada dentro de una línea de caché, y como ya mencioné, el puntero de pila generalmente se almacena en un registro. La optimización de los compiladores en algunas arquitecturas puede incluso eliminar las asignaciones en la pila mediante la reutilización de argumentos de los marcos de pila anteriores que se pasan como argumentos a las funciones llamadas en los marcos de pila más profundos. Del mismo modo, las variables asignadas a la pila a menudo pueden promoverse a registros que eviten las asignaciones.

Por el contrario, la tienda gratuita es mucho más compleja. Ni siquiera voy a empezar a cubrir los sistemas de recolección de basura, ya que ese es un tema totalmente diferente, y esta pregunta se hizo sobre el lenguaje C. Normalmente, las asignaciones y desasignaciones de una tienda gratuita involucran varias estructuras de datos diferentes, como una lista libre o grupo de bloques. Estas estructuras de datos y contabilidad también requieren memoria y, por lo tanto, ese espacio se desperdicia. Además, los registros contables a menudo se entremezclan con las asignaciones y, por lo tanto, perjudican a la localidad de datos de otras asignaciones. Las asignaciones de la tienda gratuita pueden implicar solicitar al sistema operativo subyacente más memoria de proceso típicamente de alguna forma de asignador de planchón.

Para una comparación simple, y usando jemalloc-2.2.5 y números de sloccount como referencia, la implementación de jemalloc contiene más de 8,800 líneas de código fuente en el lenguaje C y otras más de 700 líneas de código de prueba. Esto debería darle una buena idea de la diferencia de complejidad entre la asignación gratuita de la tienda y la asignación de la pila: miles de líneas de código C frente a una sola instrucción.

Además, dado que las asignaciones de almacenamiento gratuito no están limitadas a un alcance léxico único, se debe rastrear el tiempo de vida de cada asignación. Del mismo modo, estas asignaciones se pueden pasar a través de subprocesos y, por lo tanto, los problemas de sincronización de subprocesos entran en el espacio del problema. Otro gran problema para la asignación gratuita de la tienda es la fragmentación. La fragmentación causa muchos problemas:

La fragmentación daña la ubicación de los datos.
La fragmentación desperdicia memoria.
La fragmentación hace que el trabajo de encontrar espacio libre para grandes asignaciones sea más difícil.

En los sistemas modernos, las pilas son a menudo relativamente pequeñas en comparación con la tienda gratuita, por lo que, en última instancia, la tienda gratuita gestiona más espacio y, de este modo, se enfrenta a un problema más difícil. Además, debido a las limitaciones en el tamaño de las pilas, la tienda gratuita se utiliza generalmente para asignaciones más grandes, esta discrepancia entre tener que manejar asignaciones muy grandes y muy pequeñas también dificulta el trabajo de la tienda gratuita. Normalmente, las asignaciones de pila son pequeñas del orden de algunos kilobytes o menos, y el tamaño total de la pila es de solo unos pocos megabytes. La tienda gratuita generalmente recibe el resto del espacio de proceso en un programa. En las máquinas modernas, puede ser de varios cientos de gigabytes, y no es raro que las asignaciones de las tiendas gratuitas varíen de unos pocos bytes, como una breve cadena de caracteres a megabytes o incluso gigabytes de datos arbitrarios. Esto significa que los asignadores de tiendas libres tienen que lidiar con la administración de memoria virtual del sistema operativo subyacente. La asignación de la pila está esencialmente integrada en el hardware de la computadora.

Si realmente quieres aprender sobre la asignación gratuita de tiendas, recomiendo leer algunos de los muchos artículos y artículos publicados sobre varias implementaciones de malloc o incluso leer el código. Aquí hay algunos enlaces para que comiences:

dlmalloc - dlmalloc Doug Lea, una implementación histórica de malloc de referencia utilizada en GNU C ++ en un momento dado
phkmalloc - Implementación FreeBSD de malloc escrito por Poul-Henning Kamp autor de la memoria caché web de Varnish
tcmalloc - Thread-Caching Malloc implementado por algunos desarrolladores de Google
jemalloc - Implementación malloc de Jason Evan para FreeBSD (sucesor de phkmalloc)

Aquí hay algunos enlaces adicionales con descripciones de la implementación de tcmalloc:

Me lo han dicho muchas veces. Pero no sé POR QUÉ ... ¿Qué costo adicional implica la asignación de memoria del montón? ¿Está relacionado con el hardware? Está relacionado con ciclos de CPU? Tantas conjeturas pero sin respuestas exactas ... ¿Podría alguien darme alguna explicación?

Tal como dijo "unwind", la estructura de datos de Heap es más complicada que Stack. Y, en mi opinión, parte del espacio de memoria se asigna a un hilo como su Pila cuando comienza a ejecutarse, mientras que el montón es compartido por todos los hilos dentro de un proceso. Este paradigma requiere algún mecanismo adicional para gestionar el uso de cada subproceso del montón compartido, como Garbage Collection. Estoy en lo cierto en esto?

La principal diferencia entre una pila y un montón es que los elementos en una pila no se pueden eliminar fuera de servicio. Si agrega los elementos A, B, C a una pila, no puede eliminar B sin eliminar C primero. Esto significa que agregar un nuevo elemento a una pila siempre significa agregarlo al final de la pila, que es una operación muy simple. Simplemente mueve el puntero que apunta al final de la pila.

En un montón, por otro lado, puede eliminar elementos fuera de servicio. Y siempre y cuando no mueva los otros elementos después en la memoria (como algunos montones recogidos de basura), su montón tiene un "agujero" en el medio. Es decir, si agrega A, B, C a un montón y elimina B, su montón se ve así en la memoria: A _ C donde _ es un bloque de memoria no utilizada (libre). Si agrega un nuevo elemento D ahora, el asignador debe encontrar un espacio libre continuo lo suficientemente grande como para caber en D. Dependiendo de la cantidad de espacios libres continuos que haya en su memoria, esto puede ser una operación costosa. Y casi siempre es más caro que simplemente mover el puntero de "último elemento" de una pila.

Porque el montón es una estructura de datos mucho más complicada que la pila.

Para muchas arquitecturas, asignar memoria a la pila es solo cuestión de cambiar el puntero de la pila, es decir, es una instrucción. La asignación de memoria en el montón implica buscar un bloque lo suficientemente grande, dividirlo y administrar la "contabilidad" que permite cosas como free() en un orden diferente.

La memoria asignada en la pila está garantizada para ser desasignada cuando el alcance (generalmente la función) sale, y no es posible desasignar solo parte de ella.