c++ - Cómo detectar ciclos al usar shared_ptr
garbage-collection shared-ptr (10)
shared_ptr es un puntero inteligente de recuento de referencia en la biblioteca Boost.
El problema con el conteo de referencias es que no puede deshacerse de los ciclos. Me pregunto cómo se resolvería esto en C ++.
Por favor, no hay sugerencias como: "no hacer ciclos", o "usar un débil_ptr".
Editar
No me gustan las sugerencias que dicen simplemente usar un valor débil_ptr porque, obviamente, si sabes que crearás un ciclo, entonces no tendrías ningún problema. Tampoco puede saber que tendrá un ciclo en tiempo de compilación si genera shared_ptrs durante el tiempo de ejecución.
Así que, por favor, elimine las respuestas que usan weak_ptr en ellas porque específicamente pedí no tener ese tipo de respuestas ...
Entiendo su disgusto por que me digan con delicadeza el uso de weak_ptr para romper las referencias cíclicas y yo mismo casi siento rabia cuando me dicen que las referencias cíclicas son un mal estilo de programación.
Su pregunta específicamente cómo se ven las referencias cíclicas. La verdad es que en un proyecto complejo, algunos ciclos de referencia son indirectos y difíciles de detectar.
La respuesta es que no debe hacer declaraciones falsas que lo hagan vulnerable a las referencias cíclicas. Lo digo en serio y estoy criticando una práctica muy popular: usar a ciegas shared_ptr para todo.
Debe ser claro en su diseño qué punteros son propietarios y cuáles observadores.
Para propietarios usar shared_ptr
Para los observadores, use debil_ptr: todos ellos, no solo los que usted cree que pueden ser parte de un ciclo.
Si sigues esta práctica, las referencias cíclicas no causarán ningún problema y no debes preocuparte por ellos. Por supuesto, tendrá mucho código para escribir para convertir todos estos puntos débiles a puntos_compliados cuando quiera usarlos. Boost realmente no está a la altura del trabajo.
Es bastante fácil detectar ciclos:
- establece un recuento a un número bastante grande, por ejemplo, 1000 (el tamaño exacto depende de tu aplicación)
- Comience con el pionero en el que está interesado y siga los punteros del mismo.
- Para cada puntero que sigas, disminuye el conteo.
- Si el recuento se reduce a cero antes de llegar al final de la cadena de punteros, tiene un ciclo
Sin embargo, no es muy útil. Y, en general, no es posible resolver el problema del ciclo para los punteros de recuento de recuento, es por eso que se inventaron esquemas alternativos de recolección de basura como la captura de generaciones.
Es probable que necesites una técnica de recolección de basura como Mark y Sweep . La idea de este algoritmo es:
- Mantenga una lista con referencias a todos los bloques de memoria asignados.
- En algún momento se inicia el recolector de basura:
- Primero marca todos los bloques a los que aún puede acceder sin usar la lista de referencia.
- Recorre la lista borrando cada elemento que no se pudo marcar, lo que implica que ya no es posible acceder a él, por lo que no es útil.
Dado que está utilizando shared_ptr cualquier puntero que aún no haya alcanzado debe considerarse como miembro de un ciclo.
Implementación
A continuación describo un ejemplo muy ingenuo de cómo implementar la parte sweep() del algoritmo, pero reset() todos los punteros restantes en el recopilador.
Este código almacena shared_ptr<Cycle_t> punteros. El Collector clase es responsable de realizar un seguimiento de todos los punteros y de eliminarlos cuando se ejecuta sweep() .
#include <vector>
#include <memory>
class Cycle_t;
typedef std::shared_ptr<Cycle_t> Ref_t;
// struct Cycle;
struct Cycle_t {
Ref_t cycle;
Cycle_t() {}
Cycle_t(Ref_t cycle) : cycle(cycle) {}
};
struct collector {
// Note this vector will grow endlessy.
// You should find a way to reuse old links
std::vector<std::weak_ptr<Cycle_t>> memory;
// Allocate a shared pointer keeping
// a weak ref on the memory vector:
inline Ref_t add(Ref_t ref) {
memory.emplace_back(ref);
return ref;
}
inline Ref_t add(Cycle_t value) {
Ref_t ref = std::make_shared<Cycle_t>(value);
return add(ref);
}
inline Ref_t add() {
Ref_t ref = std::make_shared<Cycle_t>();
return add(ref);
}
void sweep() {
// Run a sweep algorithm:
for (auto& ref : memory) {
// If the original shared_ptr still exists:
if (auto ptr = ref.lock()) {
// Reset each pointer contained within it:
ptr->cycle.reset();
// Doing this will trigger a deallocation cascade, since
// the pointer it used to reference will now lose its
// last reference and be deleted by the reference counting
// system.
//
// The `ptr` pointer will not be deletd on the cascade
// because we still have at least the current reference
// to it.
}
// When we leave the loop `ptr` loses its last reference
// and should be deleted.
}
}
};
Puedes usarlo así:
Collector collector;
int main() {
// Build your shared pointers:
{
// Allocate them using the collector:
Ref_t c1 = collector.add();
Ref_t c2 = collector.add(c1);
// Then create the cycle:
c1.get()->cycle = c2;
// A normal block with no cycles:
Ref_t c3 = collector.add();
}
// In another scope:
{
// Note: if you run sweep an you still have an existing
// reference to one of the pointers in the collector
// you will lose it since it will be reset().
collector.sweep();
}
}
Lo probé con Valgrind y no se enumeraron fugas de memoria o bloques "aún accesibles", por lo que probablemente esté funcionando como se esperaba.
Algunas notas sobre esta implementación:
- El vector de memoria crecerá infinitamente, debe usar alguna técnica de asignación de memoria para asegurarse de que no ocupe toda la memoria de trabajo.
- Se puede argumentar que no hay necesidad de utilizar
shared_ptr(que funciona como un GC de conteo de referencias) para implementar dicho recolector de basura, ya que el algoritmo de marca y barrido ya se encargaría del trabajo. - No implementé la función mark () porque complicaría el ejemplo, pero es posible y lo explicaré a continuación.
Finalmente, si está preocupado por (2), este tipo de implementación no es desconocido. CPython (la implementación principal de Python) utiliza una combinación de recuento de referencias y Mark and Sweep, pero principalmente por razones históricas .
Implementando la función mark() :
Para implementar la función mark() necesitará hacer algunas modificaciones:
Sería necesario agregar un bool marked; Cycle_t a Cycle_t , y utilícelo para verificar si el puntero está marcado o no.
Necesitará escribir la función Collector::mark() que se vería así:
void mark(Ref_t root) {
root->marked = true;
// For each other Ref_t stored on root:
for (Ref_t& item : root) {
mark(item);
}
}
Y luego debe modificar la función de sweep() para eliminar la marca si el puntero está marcado o, si no, reset() el puntero:
void sweep() {
// Run a sweep algorithm:
for (auto& ref : memory) {
// If it still exists:
if (auto ptr = ref.lock()) {
// And is marked:
if (ptr->marked) {
ptr->marked = false;
} else {
ptr->cycle.reset();
}
}
}
}
Fue una explicación larga, pero espero que ayude a alguien.
La solución genérica para encontrar un ciclo se puede encontrar aquí:
El mejor algoritmo para probar si una lista vinculada tiene un ciclo
Esto supone que conoce la estructura de los objetos en la lista y puede seguir todos los punteros que contiene cada objeto.
No he encontrado un método mucho mejor que dibujar grandes gráficos UML y buscar ciclos.
Para depurar, utilizo un contador de instancias que va al registro, como este:
template <DWORD id>
class CDbgInstCount
{
public:
#ifdef _DEBUG
CDbgInstCount() { reghelper.Add(id, 1); }
CDbgInstCount(CDbgInstCount const &) { reghelper.Add(id, 1); }
~CDbgInstCount() { reghelper.Add(id, -1); }
#else
#endif
};
Acabo de anular para agregar eso a las clases en cuestión, y echar un vistazo al registro.
(La ID, si se proporciona como, por ejemplo, ''XYZ!'' Se convertirá en una cadena. Desafortunadamente, no puede especificar una constante de cadena como parámetro de plantilla)
Responda a la pregunta anterior, puede probar el puntero intrusivo que puede ayudar a contar cuántas veces se refirió el recurso.
#include <cstdlib>
#include <iostream>
#include <boost/intrusive_ptr.hpp>
class some_resource
{
size_t m_counter;
public:
some_resource(void) :
m_counter(0)
{
std::cout << "Resource created" << std::endl;
}
~some_resource(void)
{
std::cout << "Resource destroyed" << std::endl;
}
size_t refcnt(void)
{
return m_counter;
}
void ref(void)
{
m_counter++;
}
void unref(void)
{
m_counter--;
}
};
void
intrusive_ptr_add_ref(some_resource* r)
{
r->ref();
std::cout << "Resource referenced: " << r->refcnt()
<< std::endl;
}
void
intrusive_ptr_release(some_resource* r)
{
r->unref();
std::cout << "Resource unreferenced: " << r->refcnt()
<< std::endl;
if (r->refcnt() == 0)
delete r;
}
int main(void)
{
boost::intrusive_ptr<some_resource> r(new some_resource);
boost::intrusive_ptr<some_resource> r2(r);
std::cout << "Program exiting" << std::endl;
return EXIT_SUCCESS;
}
Aquí está el resultado devuelto.
Resource created
Resource referenced: 1
Resource referenced: 2
Program exiting
Resource unreferenced: 1
Resource unreferenced: 0
Resource destroyed
*** Program Exit ***
Sé que dijiste "no weak_ptr" pero ¿por qué no? Tener la cabeza con un valor débil para la cola, y la cola con un punto débil para la cabeza evitará el ciclo.
Una combinación de boost::weak_ptr y boost::shared_ptr ¿quizás? This artículo puede ser de interés.
Vea esta publicación sobre la detección de ciclos en un gráfico.
shared_ptr representa la relación de propiedad . Mientras que weak_ptr representa la conciencia . Tener varios objetos que poseen entre sí significa que tiene problemas con la arquitectura, que se resuelve cambiando uno o más propios ''s en la cuenta de'' s (es decir, weak_ptr ''s).
No entiendo por qué sugerir weak_ptr se considera inútil.