que - Cómo implementar la recolección de basura en C++

limpiar buffer en c++

Question

Vi una publicación acerca de implementar GC en C y algunas personas dijeron que es imposible hacerlo porque C tiene un tipeo débil. Quiero saber cómo implementar GC en C ++.

Quiero una idea general sobre cómo hacerlo. ¡Muchas gracias!

Esta es una pregunta de entrevista de Bloomberg que me contó mi amigo. Lo hizo mal en ese momento. Queremos saber sus ideas sobre esto.

Answer 1

C no es C ++, pero ambos tienen los mismos problemas "de tipo débil". Sin embargo, no son los tipos de letra implícitos los que causan un problema, sino la tendencia a "cometer errores" (subvirtiendo el sistema de tipos), especialmente en las bibliotecas de estructuras de datos.

Hay recolectores de basura para C y / o C ++. El coleccionista conservador de Boehm es probablemente el mejor conocido. Es conservador en eso, si ve un patrón de bits que se parece a un puntero a algún objeto, no recoge ese objeto. Ese valor podría ser algún otro tipo de valor por completo, por lo que el objeto podría ser recolectado, pero "conservador" significa jugar seguro.

Incluso un coleccionista conservador puede ser engañado, sin embargo, si usa punteros calculados. Hay una estructura de datos, por ejemplo, donde cada nodo de lista tiene un campo que proporciona la diferencia entre las direcciones de nodo siguiente y anterior. La idea es proporcionar un comportamiento de lista de doble enlace con un solo enlace por nodo, a expensas de iteradores más complejos. Como en la mayoría de los nodos no hay ningún puntero explícito, es posible que se recopilen incorrectamente.

Por supuesto, este es un caso especial muy excepcional.

Más importante aún: puede tener destructores confiables o recolección de basura, no ambos. Cuando se recoge un ciclo de basura, el recolector no puede decidir a qué destructor llamar primero.

Dado que el patrón RAII es generalizado en C ++, y que se basa en destructores, existe un conflicto entre IMO. Puede haber excepciones válidas, pero mi opinión es que si quieres recolección de basura, debes usar un lenguaje que está diseñado desde cero para la recolección de basura (Java, C #, ...).

Answer 2

El reclamo que viste es falso; el colector Boehm admite C y C ++. Sugiero leer la documentación del recopilador de Boehm (especialmente esta página ) para obtener una buena visión general de cómo se puede escribir un recolector de basura en C o C ++.

Answer 3

Mire en el colector de basura Boehm .

Answer 4

Puede usar punteros inteligentes o crear su propio objeto contenedor que rastreará referencias y manejará la asignación de memoria, etc. Probablemente sean preferibles los punteros inteligentes. Muchas veces puede evitar la asignación dinámica de montones por completo.

Por ejemplo:

char* pCharArray = new char[128];
// do some stuff with characters
delete [] pCharArray;

El peligro con lo anterior es que si algo tira entre el nuevo y el eliminar su eliminación no se ejecutará. Algo como lo anterior podría reemplazarse fácilmente con un código más seguro de "recolección de basura" :

std::vector<char> charArray;
// do some stuff with characters

Bloomberg tiene preguntas de entrevista notoriamente irrelevantes desde el punto de vista de la codificación práctica. Sin embargo, al igual que la mayoría de los entrevistadores, están preocupados principalmente por cómo piensas y tus habilidades de comunicación que la solución real.

Answer 5

Puede leer sobre la estructura shared_ptr .

Implementa un simple recolector de basura que cuenta la referencia .

Si desea un recolector de basura real, puede sobrecargar al nuevo operador.

Crea una estructura similar a shared_ptr, llámala Object.

Esto envolverá el nuevo objeto creado. Ahora con la sobrecarga de sus operadores, puede controlar el GC.

Todo lo que necesitas hacer ahora es simplemente implementar uno de los muchos algoritmos GC

Answer 6

La recolección de basura en C y C ++ son temas difíciles por varias razones:

1. Los punteros pueden ser encasillados a enteros y viceversa. Esto significa que podría tener un bloque de memoria al que solo se puede acceder tomando un entero, encasillado en un puntero y luego desreferenciando. Un recolector de basura debe tener cuidado de no pensar que un bloque es inalcanzable cuando de hecho todavía se puede alcanzar.

2. Los punteros no son opacos. A muchos recolectores de basura, como los recolectores stop-and-copy, les gusta mover bloques de memoria o compactarlos para ahorrar espacio. Como puede ver explícitamente los valores del puntero en C y C ++, puede ser difícil implementarlo correctamente. Debería asegurarse de que si alguien estaba haciendo algo complicado con la conversión de tipos a enteros, actualizara correctamente el entero si moviera un bloque de memoria.

3. La administración de la memoria se puede hacer de forma explícita. Cualquier recolector de basura tendrá que tener en cuenta que el usuario puede liberar bloques de memoria explícitamente en cualquier momento.

4. En C ++, hay una separación entre asignación / desasignación y construcción / destrucción de objetos. Se puede asignar un bloque de memoria con suficiente espacio para contener un objeto sin que realmente se construya ningún objeto allí. Un buen recolector de basura debería saber, cuando recupera memoria, si llama o no al destructor para detectar cualquier objeto que pueda haber asignado allí. Esto es especialmente cierto para los contenedores de bibliotecas estándar, que a menudo usan std::allocator para usar este truco por razones de eficiencia.

5. La memoria se puede asignar desde diferentes áreas. C y C ++ pueden obtener memoria del freestore incorporado (malloc / free o new / delete), o del SO a través de mmap u otras llamadas al sistema, y, en el caso de C ++, de get_temporary_buffer o get_temporary_buffer . Los programas también pueden obtener memoria de alguna biblioteca de terceros. Un buen recolector de basura debe ser capaz de rastrear las referencias a la memoria en estos otros grupos y (posiblemente) debería ser responsable de su limpieza.

6. Los punteros pueden señalar en el medio de objetos o matrices. En muchos lenguajes recolectados como basura, las referencias de objetos siempre apuntan al inicio del objeto. En C y C ++, los punteros pueden apuntar al centro de las matrices, y en C ++ a la mitad de los objetos (si se usa herencia múltiple). Esto puede complicar enormemente la lógica para detectar lo que todavía es alcanzable.

Entonces, en resumen, es extremadamente difícil construir un recolector de basura para C o C ++. La mayoría de las bibliotecas que hacen recolección de basura en C y C ++ son extremadamente conservadoras en su enfoque y son técnicamente incorrectas: suponen que, por ejemplo, no tomará un puntero, lo convertirá en un número entero, lo escribirá en el disco y luego cargará vuelve en algún momento posterior. También suponen que cualquier valor en la memoria del tamaño de un puntero podría ser un puntero, por lo que a veces se niegan a liberar la memoria inalcanzable porque hay una posibilidad distinta de cero de que haya un puntero a ella.

Como otros han señalado, Boehm GC sí hace recolección de basura para C y C ++, pero está sujeto a las restricciones mencionadas anteriormente.

Curiosamente, C ++ 11 incluye algunas funciones nuevas de la biblioteca que le permiten al programador marcar las regiones de la memoria como alcanzables e inalcanzables en previsión de futuros esfuerzos de recolección de basura. En el futuro, es posible construir un buen recolector de basura C ++ 11 con este tipo de información. Mientras tanto, tendrás que tener mucho cuidado de no romper ninguna de las reglas anteriores.