¿Qué es la fragmentación de la memoria?

He escuchado el término "fragmentación de memoria" usado algunas veces en el contexto de la asignación de memoria dinámica de C ++. He encontrado algunas preguntas sobre cómo lidiar con la fragmentación de la memoria, pero no puedo encontrar una pregunta directa que se ocupe de sí misma. Entonces:

• ¿Qué es la fragmentación de la memoria?
• ¿Cómo puedo saber si la fragmentación de la memoria es un problema para mi aplicación? ¿Qué tipo de programa es más probable que sufra?
• ¿Cuáles son buenas formas comunes de lidiar con la fragmentación de la memoria?

También:

• He escuchado que el uso de asignaciones dinámicas puede aumentar la fragmentación de la memoria. ¿Es esto cierto? En el contexto de C ++, entiendo que todos los contenedores estándar (std :: string, std :: vector, etc.) usan asignación de memoria dinámica. Si se usan en un programa (especialmente std :: string), ¿es más probable que la fragmentación de la memoria sea un problema?
• ¿Cómo se puede tratar la fragmentación de memoria en una aplicación STL-heavy?

Imagine que tiene una extensión "grande" (32 bytes) de memoria libre:

----------------------------------
|                                |
----------------------------------

Ahora, asigne algunos de ellos (5 asignaciones):

----------------------------------
|aaaabbccccccddeeee              |
----------------------------------

Ahora, libere las primeras cuatro asignaciones pero no la quinta:

----------------------------------
|              eeee              |
----------------------------------

Ahora, intente asignar 16 bytes. Vaya, no puedo, aunque hay casi el doble de eso gratis.

En los sistemas con memoria virtual, la fragmentación es menos problemática de lo que parece, porque las grandes asignaciones solo deben ser contiguas en el espacio de direcciones virtuales , no en el espacio de direcciones físicas . Entonces, en mi ejemplo, si tuviera memoria virtual con un tamaño de página de 2 bytes, podría hacer mi asignación de 16 bytes sin ningún problema. La memoria física se vería así:

----------------------------------
|ffffffffffffffeeeeff            |
----------------------------------

mientras que la memoria virtual (siendo mucho más grande) podría verse así:

------------------------------------------------------...
|              eeeeffffffffffffffff                   
------------------------------------------------------...

El síntoma clásico de la fragmentación de la memoria es que intenta asignar un bloque grande y no puede, aunque parezca tener suficiente memoria libre. Otra posible consecuencia es la incapacidad del proceso para liberar memoria de vuelta al sistema operativo (porque todavía hay algún objeto en uso en todos los bloques que ha asignado desde el sistema operativo, a pesar de que esos bloques ahora están en su mayoría sin usar).

Las tácticas para evitar la fragmentación de la memoria en C ++ funcionan mediante la asignación de objetos de diferentes áreas de acuerdo con su tamaño y / o su vida útil esperada. Entonces, si va a crear muchos objetos y destruirlos todos juntos más adelante, asígnelos desde un grupo de memoria. Cualquier otra asignación que haga entre ellos no será del grupo, por lo tanto, no se ubicará entre ellos en la memoria, por lo que la memoria no se fragmentará como resultado.

Por lo general, no necesita preocuparse demasiado, a menos que su programa sea de larga duración y haga muchas asignaciones y liberaciones. Es cuando tienes mezclas de objetos de vida corta y larga que estás en mayor riesgo, pero aun así mallocharás todo lo posible para ayudarte. Básicamente, ignórelo hasta que su programa tenga fallas de asignación o inesperadamente haga que el sistema se quede sin memoria (¡atrape esto en las pruebas, de preferencia!).

Las bibliotecas estándar no son peores que cualquier otra cosa que asigne memoria, y todos los contenedores estándar tienen un Allocparámetro de plantilla que puede usar para ajustar su estrategia de asignación si es absolutamente necesario.

¿Qué es la fragmentación de la memoria?

La fragmentación de la memoria es cuando la mayor parte de su memoria se asigna en una gran cantidad de bloques o fragmentos no contiguos, dejando un buen porcentaje de su memoria total sin asignar, pero inutilizable para la mayoría de los escenarios típicos. Esto da como resultado excepciones de memoria insuficiente o errores de asignación (es decir, malloc devuelve nulo).

La forma más fácil de pensar en esto es imaginar que tiene una gran pared vacía en la que necesita colocar imágenes de diferentes tamaños . Cada imagen ocupa un cierto tamaño y obviamente no se puede dividir en pedazos más pequeños para que encaje. Necesita un lugar vacío en la pared, el tamaño de la imagen, o no puede colocarlo. Ahora, si comienza a colgar cuadros en la pared y no tiene cuidado sobre cómo organizarlos, pronto terminará con una pared que está parcialmente cubierta de cuadros y, aunque tenga espacios vacíos, la mayoría de los cuadros nuevos no encajarán porque son más grandes que los lugares disponibles. Todavía puede colgar cuadros realmente pequeños, pero la mayoría no encajan. Entonces tendrá que reorganizar (compactar) los que ya están en la pared para dejar espacio para más ...

Ahora, imagine que la pared es su memoria (montón) y las imágenes son objetos ... Eso es fragmentación de la memoria ...

¿Cómo puedo saber si la fragmentación de la memoria es un problema para mi aplicación? ¿Qué tipo de programa es más probable que sufra?

Una señal reveladora de que puede estar lidiando con la fragmentación de la memoria es si obtiene muchos errores de asignación, especialmente cuando el porcentaje de memoria utilizada es alto, pero aún no ha utilizado toda la memoria, por lo que técnicamente debería tener mucho espacio para los objetos que intenta asignar.

Cuando la memoria está muy fragmentada, las asignaciones de memoria probablemente tomarán más tiempo porque el asignador de memoria tiene que hacer más trabajo para encontrar un espacio adecuado para el nuevo objeto. Si a su vez tiene muchas asignaciones de memoria (lo que probablemente hace desde que terminó con la fragmentación de la memoria), el tiempo de asignación puede incluso causar retrasos notables.

¿Cuáles son buenas formas comunes de lidiar con la fragmentación de la memoria?

Use un buen algoritmo para asignar memoria. En lugar de asignar memoria para muchos objetos pequeños, preasigne memoria para una matriz contigua de esos objetos más pequeños. A veces, ser un poco derrochador al asignar memoria puede ser muy útil para el rendimiento y puede ahorrarle la molestia de tener que lidiar con la fragmentación de la memoria.

La fragmentación de la memoria es el mismo concepto que la fragmentación del disco: se refiere al espacio que se desperdicia porque las áreas en uso no están lo suficientemente juntas.

Supongamos, por ejemplo, un juguete simple que tiene diez bytes de memoria:

 |   |   |   |   |   |   |   |   |   |   |
   0   1   2   3   4   5   6   7   8   9

Ahora asignemos tres bloques de tres bytes, nombre A, B y C:

 | A | A | A | B | B | B | C | C | C |   |
   0   1   2   3   4   5   6   7   8   9

Ahora desasigne el bloque B:

 | A | A | A |   |   |   | C | C | C |   |
   0   1   2   3   4   5   6   7   8   9

¿Qué sucede si intentamos asignar un bloque D de cuatro bytes? Bueno, tenemos cuatro bytes de memoria libre, pero no tenemos cuatro bytes contiguos de memoria libre, ¡así que no podemos asignar D! Este es un uso ineficiente de la memoria, porque deberíamos haber podido almacenar D, pero no pudimos. Y no podemos mover C para hacer espacio, porque muy probablemente algunas variables en nuestro programa apuntan a C, y no podemos encontrar y cambiar automáticamente todos estos valores.

¿Cómo sabes que es un problema? Bueno, la señal más importante es que el tamaño de la memoria virtual de su programa es considerablemente mayor que la cantidad de memoria que está utilizando realmente. En un ejemplo del mundo real, tendría muchos más de diez bytes de memoria, por lo que D solo se asignaría comenzando un byte 9, y los bytes 3-5 permanecerían sin usar a menos que luego asigne algo de tres bytes de longitud o menos.

En este ejemplo, 3 bytes no es mucho desperdicio, pero considere un caso más patológico donde dos asignaciones de un par de bytes están, por ejemplo, separadas por diez megabytes en memoria, y necesita asignar un bloque de 10 megabytes de tamaño + 1 byte. Tienes que ir a pedirle al sistema operativo más de diez megabytes de memoria virtual para hacer eso, a pesar de que solo te falta un byte de tener suficiente espacio.

¿Cómo lo evitas? Los peores casos tienden a surgir cuando crea y destruye objetos pequeños con frecuencia, ya que eso tiende a producir un efecto de "queso suizo" con muchos objetos pequeños separados por muchos agujeros pequeños, lo que hace imposible asignar objetos más grandes en esos agujeros. Cuando sepa que va a hacer esto, una estrategia efectiva es preasignar un bloque grande de memoria como un grupo para sus objetos pequeños, y luego administrar manualmente la creación de los objetos pequeños dentro de ese bloque, en lugar de permitir el asignador predeterminado lo maneja.

En general, cuantas menos asignaciones haga, menos probable es que la memoria se fragmente. Sin embargo, STL trata esto con bastante eficacia. Si tiene una cadena que está utilizando la totalidad de su asignación actual y le agrega un carácter, no simplemente se reasigna a su longitud actual más uno, duplica su longitud. Esta es una variación de la estrategia de "grupo de pequeñas asignaciones frecuentes". La cadena está tomando una gran cantidad de memoria para que pueda lidiar eficientemente con pequeños aumentos repetidos de tamaño sin realizar pequeñas reasignaciones repetidas. De hecho, todos los contenedores STL hacen este tipo de cosas, por lo que generalmente no tendrá que preocuparse demasiado por la fragmentación causada por la reasignación automática de los contenedores STL.

Aunque, por supuesto, los contenedores STL no agrupan la memoria entre ellos, por lo que si va a crear muchos contenedores pequeños (en lugar de algunos contenedores que cambian de tamaño con frecuencia), es posible que deba preocuparse por evitar la fragmentación de la misma manera que sería para cualquier objeto pequeño creado con frecuencia, STL o no.

• ¿Qué es la fragmentación de la memoria?

La fragmentación de la memoria es el problema de que la memoria se vuelva inutilizable aunque esté teóricamente disponible. Hay dos tipos de fragmentación: la fragmentación interna es la memoria que se asigna pero que no se puede usar (por ejemplo, cuando la memoria se asigna en fragmentos de 8 bytes pero el programa repetidamente realiza alicaciones individuales cuando solo necesita 4 bytes). La fragmentación externa es el problema de que la memoria libre se divida en muchos fragmentos pequeños, por lo que no se pueden cumplir las solicitudes de asignación grandes, aunque hay suficiente memoria libre en general.

• ¿Cómo puedo saber si la fragmentación de la memoria es un problema para mi aplicación? ¿Qué tipo de programa es más probable que sufra?

La fragmentación de la memoria es un problema si su programa usa mucha más memoria del sistema de la que requerirían sus datos reales de paylod (y ha descartado pérdidas de memoria).

• ¿Cuáles son buenas formas comunes de lidiar con la fragmentación de la memoria?

Use un buen asignador de memoria. IIRC, aquellos que usan una estrategia de "mejor ajuste" son generalmente muy superiores para evitar la fragmentación, aunque un poco más lento. Sin embargo, también se ha demostrado que para cualquier estrategia de asignación, existen los peores casos patológicos. Afortunadamente, los patrones de asignación típicos de la mayoría de las aplicaciones son en realidad relativamente benignos para que los asignadores los manejen. Hay un montón de documentos por ahí si está interesado en los detalles:

• Paul R. Wilson, Mark S. Johnstone, Michael Neely y David Boles. Asignación de almacenamiento dinámico: una encuesta y revisión crítica. En las Actas del Taller Internacional de 1995 sobre Gestión de la Memoria, Springer Verlag LNCS, 1995
• Mark S. Johnson, Paul R. Wilson. El problema de la fragmentación de la memoria: ¿resuelto? En ACM SIG-PLAN Notices, volumen 34 No. 3, páginas 26-36, 1999
• MR Garey, RL Graham y JD Ullman. Análisis del peor caso de algoritmos de asignación de memoria. En el cuarto simposio anual de ACM sobre la teoría de la informática, 1972

Actualización:
Google TCMalloc: Malloc de almacenamiento en caché de subprocesos
Se ha descubierto que es bastante bueno para manejar la fragmentación en un proceso de larga ejecución.

He estado desarrollando una aplicación de servidor que tenía problemas con la fragmentación de la memoria en HP-UX 11.23 / 11.31 ia64.

Se veía así. Hubo un proceso que hizo asignaciones de memoria y desasignaciones y se ejecutó durante días. Y a pesar de que no hubo pérdidas de memoria, el consumo de memoria del proceso siguió aumentando.

Sobre mi experiencia En HP-UX es muy fácil encontrar la fragmentación de la memoria usando HP-UX gdb. Establece un punto de interrupción y cuando lo golpea ejecuta este comando: info heapy ve todas las asignaciones de memoria para el proceso y el tamaño total del montón. Luego, continúa con su programa y, algún tiempo después, vuelve a alcanzar el punto de quiebre. Lo haces de nuevo info heap. Si el tamaño total del almacenamiento dinámico es mayor pero el número y el tamaño de las asignaciones separadas son iguales, es probable que tenga problemas de asignación de memoria. Si es necesario, verifique esto algunas veces.

Mi forma de mejorar la situación fue esta. Después de hacer un análisis con HP-UX gdb, vi que los problemas de memoria eran causados ​​por el hecho de que solía std::vectoralmacenar algunos tipos de información de una base de datos. std::vectorrequiere que sus datos se mantengan en un bloque. Tenía algunos contenedores basados ​​en losstd::vector . Estos contenedores fueron recreados regularmente. A menudo hubo situaciones en las que se agregaron nuevos registros a la base de datos y luego se recrearon los contenedores. Y dado que los contenedores recreados eran más grandes, no encajaban en los bloques de memoria libre disponibles y el tiempo de ejecución solicitó un nuevo bloque más grande del sistema operativo. Como resultado, aunque no hubo pérdidas de memoria, el consumo de memoria del proceso aumentó. Mejoré la situación cuando cambié los contenedores. En lugar de std::vectorempezar a usarstd::deque que tiene una forma diferente de asignar memoria para datos.

Sé que una de las formas de evitar la fragmentación de la memoria en HP-UX es usar el Asignador de bloques pequeños o MallocNextGen. En RedHat Linux, el asignador predeterminado parece manejar bastante bien la asignación de muchos bloques pequeños. En Windows existe Low-fragmentation Heapy aborda el problema del gran número de pequeñas asignaciones.

Tengo entendido que en una aplicación STL pesada primero tiene que identificar los problemas. Los asignadores de memoria (como en libc) realmente manejan el problema de muchas asignaciones pequeñas, lo cual es típico para std::string(por ejemplo, en mi aplicación de servidor hay muchas cadenas STL, pero como veo al ejecutarlas info heapno están causando ningún problema). Mi impresión es que debe evitar las grandes asignaciones frecuentes. Lamentablemente, hay situaciones en las que no puede evitarlas y tiene que cambiar su código. Como digo en mi caso, mejoré la situación cuando cambié a std::deque. Si identifica la fragmentación de su memoria, podría ser posible hablar de ella con mayor precisión.

La fragmentación de la memoria es más probable cuando asigna y desasigna muchos objetos de diferentes tamaños. Supongamos que tiene el siguiente diseño en la memoria:

obj1 (10kb) | obj2(20kb) | obj3(5kb) | unused space (100kb)

Ahora, cuando obj2se libera, tiene 120 kb de memoria no utilizada, pero no puede asignar un bloque completo de 120 kb, porque la memoria está fragmentada.

Las técnicas comunes para evitar ese efecto incluyen amortiguadores de anillo y agrupaciones de objetos . En el contexto de la STL, métodos como std::vector::reserve()pueden ayudar.

Una respuesta muy detallada sobre la fragmentación de la memoria se puede encontrar aquí.

http://library.softwareverify.com/memory-fragmentation-your-worst-nightmare/

Esta es la culminación de 11 años de respuestas de fragmentación de memoria que he estado proporcionando a personas que me hacen preguntas sobre fragmentación de memoria en softwareverify.com

¿Qué es la fragmentación de la memoria?

Cuando su aplicación utiliza memoria dinámica, asigna y libera fragmentos de memoria. Al principio, todo el espacio de memoria de su aplicación es un bloque contiguo de memoria libre. Sin embargo, cuando asigna bloques libres y de diferente tamaño, la memoria comienza a fragmentarse , es decir, en lugar de un gran bloque libre contiguo y varios bloques contiguos asignados, habrá un bloque asignado y uno libre mezclado. Como los bloques libres tienen un tamaño limitado, es difícil reutilizarlos. Por ejemplo, puede tener 1000 bytes de memoria libre, pero no puede asignar memoria para un bloque de 100 bytes, porque todos los bloques libres tienen como máximo 50 bytes de longitud.

Otra fuente de fragmentación inevitable, pero menos problemática, es que en la mayoría de las arquitecturas, las direcciones de memoria deben estar alineadas con los límites de bytes de 2, 4, 8, etc. (es decir, las direcciones deben ser múltiplos de 2, 4, 8, etc.) Esto significa que incluso si tiene, por ejemplo, una estructura que contiene 3 charcampos, su estructura puede tener un tamaño de 12 en lugar de 3, debido al hecho de que cada campo está alineado con un límite de 4 bytes.

¿Cómo puedo saber si la fragmentación de la memoria es un problema para mi aplicación? ¿Qué tipo de programa es más probable que sufra?

La respuesta obvia es que obtienes una excepción de falta de memoria.

Aparentemente, no hay una buena forma portátil de detectar fragmentación de memoria en aplicaciones C ++. Vea esta respuesta para más detalles.

¿Cuáles son buenas formas comunes de lidiar con la fragmentación de la memoria?

Es difícil en C ++, ya que usa direcciones de memoria directas en punteros y no tiene control sobre quién hace referencia a una dirección de memoria específica. Por lo tanto, reorganizar los bloques de memoria asignados (como lo hace el recolector de basura Java) no es una opción.

Un asignador personalizado puede ayudar administrando la asignación de objetos pequeños en una porción de memoria más grande y reutilizando las ranuras libres dentro de esa porción.

Esta es una versión súper simplificada para tontos.

A medida que los objetos se crean en la memoria, se agregan al final de la parte utilizada en la memoria.

Si se elimina un objeto que no está al final de la porción de memoria utilizada, lo que significa que este objeto estaba entre otros 2 objetos, creará un "agujero".

Esto es lo que se llama fragmentación.

Cuando desea agregar un elemento en el montón, lo que sucede es que la computadora tiene que hacer una búsqueda de espacio para ajustarse a ese elemento. Es por eso que las asignaciones dinámicas cuando no se realizan en un grupo de memoria o con un asignador agrupado pueden "ralentizar" las cosas. Para una aplicación STL pesada si está haciendo subprocesos múltiples, existe el asignador Hoard o la versión TBB Intel .

Ahora, cuando la memoria está fragmentada, pueden ocurrir dos cosas:

1. Tendrá que haber más búsquedas para encontrar un buen espacio para pegar objetos "grandes". Es decir, con muchos objetos pequeños dispersos sobre la búsqueda de una buena porción de memoria podría ser difícil en ciertas condiciones (estos son extremos).
2. La memoria no es una entidad fácil de leer. Los procesadores están limitados a cuánto pueden contener y dónde. Lo hacen intercambiando páginas si un elemento que necesitan es un lugar pero las direcciones actuales son otro. Si constantemente tiene que intercambiar páginas, el procesamiento puede ralentizarse (nuevamente, escenarios extremos en los que esto afecta el rendimiento). Consulte esta publicación en la memoria virtual .

La fragmentación de la memoria se produce porque se solicitan bloques de memoria de diferentes tamaños. Considere un búfer de 100 bytes. Solicitas dos caracteres, luego un número entero. Ahora libera los dos caracteres, luego solicita un nuevo entero, pero ese entero no puede caber en el espacio de los dos caracteres. Esa memoria no se puede reutilizar porque no está en un bloque contiguo lo suficientemente grande como para reasignarla. Además de eso, ha invocado una gran cantidad de gastos generales de asignación para sus caracteres.

Esencialmente, la memoria solo viene en bloques de cierto tamaño en la mayoría de los sistemas. Una vez que divide estos bloques, no se pueden volver a unir hasta que se libere todo el bloque. Esto puede llevar a bloques enteros en uso cuando en realidad solo una pequeña parte del bloque está en uso.

La forma principal de reducir la fragmentación del montón es hacer asignaciones más grandes y menos frecuentes. En el extremo, puede usar un montón administrado que sea capaz de mover objetos, al menos, dentro de su propio código. Esto elimina completamente el problema, desde una perspectiva de memoria, de todos modos. Obviamente, mover objetos y tal tiene un costo. En realidad, solo tiene un problema si asigna cantidades muy pequeñas del montón a menudo. Usar contenedores contiguos (vector, cadena, etc.) y asignar en la pila tanto como sea humanamente posible (siempre es una buena idea para el rendimiento) es la mejor manera de reducirlo. Esto también aumenta la coherencia de caché, lo que hace que su aplicación se ejecute más rápido.

Lo que debe recordar es que en un sistema de escritorio x86 de 32 bits, tiene una memoria completa de 2 GB, que se divide en "páginas" de 4KB (bastante seguro de que el tamaño de página es el mismo en todos los sistemas x86). Tendrá que invocar alguna fragmentación omgwtfbbq para tener un problema. La fragmentación es realmente un problema del pasado, ya que los montones modernos son excesivamente grandes para la gran mayoría de las aplicaciones, y hay una prevalencia de sistemas que son capaces de resistirlo, como los montones administrados.

¿Qué tipo de programa es más probable que sufra?

Un buen (= horroroso) ejemplo de los problemas asociados con la fragmentación de la memoria fue el desarrollo y lanzamiento de "Elemental: War of Magic" , un juego de computadora de Stardock .

El juego fue construido para 32 bits / 2 GB de memoria y tuvo que hacer mucha optimización en la gestión de memoria para que el juego funcionara dentro de esos 2 GB de memoria. Como la "optimización" condujo a una asignación y desasignación constantes, con el tiempo se produjo una fragmentación de la memoria de almacenamiento dinámico y el juego se bloqueó cada vez .

Hay una entrevista de "historia de guerra" en YouTube.