Cómo implementar un montón de memoria

Question

no estaba muy seguro de cómo expresar el título, pero la pregunta es:

He oído hablar de los programadores de la asignación de una gran parte de memoria contigua al inicio de un programa y luego repartirlo según sea necesario. Esto está en contraste con simplemente ir al sistema operativo cada vez que se necesita memoria. He oído que esto sería más rápido porque evitaría el costo de pedir continuamente al sistema operativo bloques de memoria contiguos.

Creo que la JVM hace justamente esto, manteniendo su propia sección de memoria y luego asignando objetos a partir de eso.

Mi pregunta es, ¿cómo implementaría esto realmente?

Gracias, dragonwrenn

Answer 1

La mayoría de los compiladores C y C++ ya proporcionan un administrador de memoria de montón como parte de la biblioteca estándar, por lo que no necesita hacer nada para evitar golpear el sistema operativo con cada solicitud.

Si desea mejorar el rendimiento, hay una serie de asignadores mejorados a los que puede simplemente vincular e ir. p.ej. Hoard, que se menciona en una respuesta ahora eliminada (que en realidad era bastante buena, wheaties, ¿por qué la eliminaste?).

Si desea escribir su propio administrador del montón como un ejercicio de aprendizaje, aquí están las cosas básicas que necesita para hacer:

• Solicitud de un gran bloque de memoria desde el sistema operativo
• Mantener una lista enlazada de los bloques libres
• Cuando una solicitud de asignación entra en juego:
  • buscar en la lista para un bloque que es lo suficientemente grande para el tamaño solicitado además de algunas variables de teneduría de libros almacenados junto.
  • dividen a un suficiente trozo grande del bloque de la solicitud actual, poner el resto de vuelta en la lista libre
  • si no hay un bloque es lo suficientemente grande, volver al sistema operativo y pedir otro trozo grande
• Cuando una solicitud de cancelación de asignación viene en
  • leer el encabezado para averiguar el tamaño
  • añadir el bloque que ha quedado libre en la lista libre
  • opcionalmente, ver si la memoria inmediatamente fol mugido también aparece en la lista libre, y combinar los dos bloques adyacentes en uno mayor, uno (llamado coalescencia del montón)

Answer 2

asignar un trozo de memoria al comienzo del programa lo suficientemente grande como para sostener su necesidad. Luego debe anular el nuevo y/o malloc, eliminar y/o devolver la memoria desde/a este búfer.

Al implementar este tipo de solución, necesita escribir su propio asignador (para obtener el origen del fragmento) y puede terminar usando más de un asignador, que a menudo es la razón por la que asigna un grupo de memoria en primer lugar.

El asignador de memoria predeterminado es un buen asignador general, pero no es el mejor para todas las necesidades de asignación. Por ejemplo, si sabe que va a asignar una gran cantidad de objetos para un tamaño particular, puede definir un asignador que asigna un búfer de tamaño fijo y preasignar más de uno para obtener cierta eficiencia.

Answer 3

Aquí es el clásico asignador, y uno de los mejores para uso no multiproceso:

http://g.oswego.edu/dl/html/malloc.html

Usted puede aprender mucho de la lectura de la explicación de su diseño.

Dicho esto, a menos que su programa tenga patrones de asignación realmente inusuales, probablemente sea una muy mala idea escribir su propio asignador o usar uno personalizado. Especialmente si intenta reemplazar el sistema malloc, se corre el riesgo de que todo tipo de errores y problemas de compatibilidad de diferentes bibliotecas (o funciones de biblioteca estándar) se vinculen a la "versión incorrecta de malloc".

Si necesita una asignación especializada para algunas tareas específicas, puede hacerlo sin reemplazar malloc. Recomiendo buscar GNU obstack y grupos de objetos para objetos de tamaño fijo. Estos abarcan la mayoría de los casos en que la asignación especializada podría tener una utilidad práctica real.

Answer 4

1. Sí, tanto stdlib heap como OS heap/virtual memory son bastante problemáticos. Las llamadas al sistema operativo son realmente lentas, y stdlib es más rápido, pero todavía tiene algunos bloqueos y comprobaciones "innecesarios" 0 , y agrega una sobrecarga significativa a los bloques asignados (es decir, cierta memoria se usa para administración, además de lo que asigna).
2. En muchos casos es posible evitar completamente la asignación dinámica, mediante el uso de estructuras estáticas en su lugar. Por ejemplo, a veces es mejor (más seguro, etc.) definir un buffer estático de 64k para el nombre de archivo unicode, que definir un puntero/std: string y asignarlo dinámicamente a .
3. Cuando el programa tiene que asignar muchas instancias de la misma estructura, es mucho más rápido para asignar bloques de memoria grandes y luego simplemente almacenar las instancias allí (secuencialmente o usando una lista enlazada de nodos libres) - C++ tiene un "colocación nueva" para eso.
4. En muchos casos, cuando se trabaja con objetos de tamaño variable, el conjunto de tamaños posibles es muy limitado (por ejemplo, algo así como 4 + 2 * (1..256)), por lo que es posible usar grupos como [3] sin tener que recolectar basura, llenar las lagunas, etc.
5. Es común que un asignador personalizado para tareas específicas sea mucho más rápido que uno (s) de la biblioteca estándar, e incluso más rápido que la velocidad optimizada, pero implementaciones demasiado universales.
6. CPUs modernos/sistemas operativos compatibles con "grandes páginas", que pueden mejorar significativamente la velocidad de acceso a memoria cuando se trabaja explícitamente con grandes bloques - ver http://7-max.com/

Answer 5

IBM developerWorks tiene un buen artículo sobre la gestión de memoria, con una extensa sección de recursos para lecturas adicionales: Inside memory management.

Wikipedia también tiene buena información: C dynamic memory allocation, Memory management.