recolectores - Compactación de la implementación del recolector de basura en C++ 0x
recolectores de basura particulares (3)
Estoy implementando un recolector de basura compacto para mi uso personal en C ++ 0x, y tengo una pregunta. Obviamente, la mecánica del colector depende de los objetos en movimiento, y me he estado preguntando cómo implementar esto en términos de los tipos de punteros inteligentes que lo apuntan. He estado pensando en un puntero a puntero en el tipo de puntero en sí, o, el recolector mantiene una lista de punteros que apuntan a cada objeto para que puedan modificarse, eliminando la necesidad de una doble de-ref al acceder el puntero pero agregando algo de sobrecarga adicional durante la recolección y sobrecarga de memoria adicional. ¿Cuál es la mejor manera de ir aquí?
Editar: Mi principal preocupación es la rápida asignación y acceso. No me preocupan las colecciones u otro tipo de mantenimiento particularmente eficientes, porque eso no es realmente para lo que está diseñado el GC.
Esta es una pregunta bastante sencilla, así que aquí hay una respuesta directa:
Mark-and-sweep (y, ocasionalmente, mark-and-compact para evitar la fragmentación del montón) es el más rápido cuando se trata de la asignación y el acceso (evitando las dobles referencias). También es muy fácil de implementar. Dado que no le preocupa el impacto en el rendimiento de la recopilación (el marcado y barrido tiende a congelar el proceso de forma no determinista), este debería ser el camino a seguir.
Detalles de implementación encontrados en:
No hay nada sencillo sobre el injerto en GC extra a C ++, por no hablar de un algoritmo de compactación. No está claro exactamente qué intentas hacer y cómo interactuará con el resto del código C ++.
De hecho, escribí un gc en C ++ que funciona con el código existente de C ++ y tenía un compactador en una etapa (aunque lo eliminé porque era demasiado lento). Pero hay muchos problemas semánticos desagradables. Le mencioné a Bjarne hace solo unas semanas que C ++ carece del operador requerido para hacerlo correctamente y la situación es que es poco probable que exista porque tiene una utilidad limitada.
Lo que realmente necesita es un operador "re-diríjame". Lo que sucede es que realmente no mueves objetos alrededor. Solo usa mmap para cambiar la dirección del objeto. Esto es mucho más rápido y, en efecto, está utilizando las características de VM para proporcionar identificadores.
Sin esta facilidad, tiene que tener una forma de realizar un movimiento superpuesto de un objeto, lo que no puede hacer en C ++ de manera eficiente: primero tendría que pasar a un objeto temporal. En C, es mucho más fácil, puedes usar memmove . En algún momento, todos los indicadores hacia o hacia los objetos movidos deben ajustarse.
El uso de manejadores no resuelve este problema, solo reduce el problema de los objetos de tamaño arbitrario a los de tamaño constante: estos son más fáciles de administrar en una matriz, pero existe el mismo problema: usted tiene que administrar el almacenamiento. Si elimina un montón de identificadores de la matriz aleatoriamente ... todavía tiene un problema con la fragmentación.
Así que no te molestes con las asas, no funcionan.
Esto es lo que hice en Félix: llamas new(shape, collector) T(args) . Aquí, la shape es un descriptor del tipo, que incluye una lista de desplazamientos que contienen punteros (GC) y la dirección de una rutina para finalizar el objeto (de forma predeterminada, llama al destructor).
También contiene una bandera que memmove si el objeto se puede mover con memmove . Si el objeto es grande o está inmóvil, es asignado por malloc . Si el objeto es pequeño y móvil, se asigna en una arena, siempre que haya espacio en la arena.
La arena se compacta moviendo todos los objetos en ella y utilizando la información de forma para ajustar globalmente todos los punteros hacia o dentro de estos objetos. La compactación se puede hacer de forma incremental.
La desventaja para un programador de C ++ es la necesidad de construir un objeto de shape correcta para pasar. Esto no me molesta porque estoy implementando un lenguaje que puede generar la información de forma automáticamente.
Ahora: el punto clave es: para realizar la compactación, debe usar un colector preciso. La compactación no puede funcionar con un coleccionista conservador. Esto es muy importante. Está bien permitir algunas fugas si ve un valor que parece un puntero pero que es un entero: no se recopilará algún objeto, pero esto no suele ser un gran problema. Pero para la compactación, tiene que ajustar los punteros, pero es mejor que no cambie ese número entero: por lo que debe saber con seguridad cuándo es un puntero, por lo que su recopilador debe ser preciso: la forma debe ser conocida.
En Ocaml esto es relativamente simple: todo es un puntero o un entero y el bit bajo se usa en el tiempo de ejecución para indicar. Los objetos a los que se apunta tienen un código que indica el tipo, y solo hay algunos tipos: un escalar (no escanearlo) o un agregado (escanearlo, solo contiene números enteros o punteros).
Una generación de viveros le dará el mejor rendimiento de asignación posible porque es solo un golpe de puntero.
Puede implementar actualizaciones de puntero sin usar doble direccionamiento indirecto usando técnicas como una pila sombra, pero esto será lento y muy propenso a errores si está escribiendo este código C ++ a mano.