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

8 minutos de lectura

¿Por que la asignacion de memoria en el monton es
smwikipedia

Me han dicho esto muchas veces. Pero no sé POR QUÉ… ¿Qué costo adicional implica la asignación de memoria desde el montón? ¿Está relacionado con el hardware? ¿Está relacionado con los ciclos de la CPU? Tantas conjeturas pero ninguna respuesta exacta… ¿Podría alguien darme alguna explicación?

Tal como dijo “desenrollar”, la estructura de datos Heap es más complicada que Stack. Y, en mi opinión, se asigna algo de espacio de memoria a un subproceso como su pila cuando comienza a ejecutarse, mientras que el montón lo comparten todos los subprocesos dentro de un proceso. Este paradigma requiere algún mecanismo adicional para administrar el uso de cada subproceso del montón compartido, como la recolección de elementos no utilizados. ¿Tengo razón en esto?

  • Consulte stackoverflow.com/questions/161053/…, se trata de C++ pero el concepto es el mismo.

    – kennytm

    15 de febrero de 2010 a las 9:40

¿Por que la asignacion de memoria en el monton es
relajarse

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

Para muchas arquitecturas, asignar memoria en 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.

Se garantiza que la memoria asignada en la pila se desasignará cuando el alcance (normalmente la función) finalice, y no es posible desasignar solo una parte.

  • La última frase es un poco confusa. En lugar de decir “se pierde todo a la vez”, diría que se garantiza que se liberará en el orden inverso al que se asignó.

    – Laurence Gonsalves

    15 de febrero de 2010 a las 9:53

1647573251 928 ¿Por que la asignacion de memoria en el monton es
b4mano

En su edición, donde reafirma la respuesta de relajarse, menciona la “estructura de datos del montón”. Tenga mucho cuidado ya que la estructura de datos conocida como montón no tiene relación con la asignación de memoria dinámica. Para ser muy claro, utilizaré la terminología más lingüística de abogado de tienda gratis.

Como ya se ha señalado, la asignación de pilas 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 se limitan a una función particular. Esto los convierte en candidatos mucho mejores para las optimizaciones del compilador, como calcular previamente el espacio total necesario en la pila y hacer un solo incremento para un marco de pila completo. Asimismo, la pila tiene mejor localidad de datos garantizada. Casi siempre se garantiza que la parte superior de la pila está dentro de una línea de caché y, como ya mencioné, el puntero de la pila generalmente se almacena en un registro. La optimización de compiladores en algunas arquitecturas puede incluso eliminar asignaciones por completo en la pila al reutilizar argumentos de marcos de pila anteriores que se pasan como argumentos a funciones llamadas en marcos de pila más profundos. Del mismo modo, las variables asignadas a la pila a menudo se pueden promover a registros evitando también las asignaciones.

Por el contrario, la tienda gratuita es mucho mas complejo. Ni siquiera voy a comenzar a cubrir los sistemas de recolección de basura, ya que ese es un tema completamente diferente, y esta pregunta se hizo sobre el lenguaje C. Por lo general, las asignaciones y desasignaciones de una tienda gratuita implican varias estructuras de datos diferentes, como una lista gratuita o un grupo de bloques. Estas estructuras de datos y la 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, dañan la ubicación de los datos de otras asignaciones. Las asignaciones de la tienda gratuita pueden implicar pedirle al sistema operativo subyacente más memoria de proceso, generalmente de alguna forma de asignador de losa.

Para una comparación sencilla, 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 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 en complejidad entre la asignación gratuita de almacenamiento y la asignación de pila: miles de líneas de código C versus una sola instrucción.

Además, dado que las asignaciones de tiendas gratuitas no se limitan a un solo ámbito léxico, se debe realizar un seguimiento de la vida útil de cada asignación. Del mismo modo, estas asignaciones pueden pasar a través de subprocesos y, por lo tanto, los problemas de sincronización de subprocesos ingresan al espacio del problema. Otro gran problema para la asignación gratuita de tiendas es la fragmentación. La fragmentación causa muchos problemas:

  • La fragmentación daña la localidad de los datos.
  • La fragmentación desperdicia memoria.
  • La fragmentación dificulta el trabajo de encontrar espacio libre para grandes asignaciones.

En los sistemas modernos, las pilas suelen ser relativamente pequeñas en comparación con la tienda gratuita, por lo que, en última instancia, la tienda gratuita administra más espacio y, por lo tanto, aborda un problema más difícil. Además, debido a las limitaciones en el tamaño de las pilas, la tienda gratuita generalmente se usa para asignaciones más grandes, esta discrepancia entre tener que manejar asignaciones muy grandes y muy pequeñas también hace que el trabajo de la tienda gratuita sea más difícil. Por lo general, las asignaciones de pila son pequeñas, del orden de unos pocos kilobytes o menos, y el tamaño total de la pila es de solo unos pocos megabytes. A la tienda gratuita generalmente se le da la todo el resto del espacio del proceso en un programa En las máquinas modernas, esto puede ser de varios cientos de gigabytes, y no es raro que las asignaciones de tiendas gratuitas varíen en tamaño desde unos pocos bytes, como una cadena corta de caracteres, hasta megabytes o incluso gigabytes de datos arbitrarios. Esto significa que los asignadores de almacenamiento gratuito tienen que lidiar con la administración de memoria virtual del sistema operativo subyacente. La asignación de pilas está esencialmente integrada en el hardware de la computadora.

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

  • dlmalloc – Malloc de Doug Lea, una implementación de malloc de referencia histórica utilizada en GNU C++ en un momento dado
  • phkmalloc – Implementación FreeBSD de malloc escrita por Poul-Henning Kamp, autor de la caché web 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:

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

En un montón por otro lado, usted lata eliminar artículos fuera de servicio. Y siempre que no mueva los otros elementos después en la memoria (como lo hacen algunos montones 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 tiene que encontrar un espacio libre continuo lo suficientemente grande como para que quepa D. Dependiendo de cuántos espacios libres continuos haya en su memoria, esta puede ser una operación costosa. Y casi siempre es más costoso que simplemente mover el puntero del “último elemento” de una pila.

Creación de datos en el área de la pila: simplemente mueva el puntero de la pila Creación de datos en el área de la cabeza: busque un área en el grupo de memoria que satisfaga el requisito dado (puede usar el primer ajuste, el mejor ajuste o el peor ajuste). Después de encontrar el almacén del área la información (contabilidad)

Eliminación en la pila: la eliminación en la pila es fácil. Simplemente mueva el puntero de la pila hacia abajo. Eliminación en el área del montón: encuentre dónde se almacena el elemento en el montón (usando la contabilidad) y combine dos bloques libres adyacentes si es necesario;

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad