Come rilevare cicli quando si utilizza shared_ptr

StackOverflow https://stackoverflow.com/questions/776042

Domanda

shared_ptr è un riferimento conteggio puntatore intelligente nella libreria Boost.

Il problema con il conteggio di riferimento è che esso non può disporre di cicli. Mi chiedo come si potrebbe fare per risolvere questo in C ++.

Si prega di non suggerimenti come: "non fare cicli", o "utilizzare un weak_ptr"

Modifica

Non mi piace suggerimenti che dicono di utilizzare solo un weak_ptr perché ovviamente se sapete si creerà un ciclo, allora si dovrebbe non avere un problema. Non è inoltre possibile sapere si avrà un ciclo in fase di compilazione se generate shared_ptrs durante il runtime.

Quindi, per favore, di sé eliminare le risposte che utilizzano weak_ptr in loro, perché ho chiesto espressamente di non avere quel tipo di risposte ...

È stato utile?

Soluzione

Non ho trovato un metodo molto migliore di disegno grandi grafici UML e guardare fuori per i cicli.

Per eseguire il debug, io uso un contatore esempio andare al Registro di sistema, in questo modo: 

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
};

Ho appena ned aggiungere che alle classi in questione, e hanno uno sguardo al Registro di sistema.

(L'ID, se dato come per esempio 'XYZ!' Sarà convertito in una stringa. Purtroppo, non è possibile specificare una stringa costante come parametro di template)

Altri suggerimenti

shared_ptr rappresenta proprietà relazione. Mentre weak_ptr rappresenta consapevolezza . Avere diversi oggetti che possiedono ogni altro mezzo di problemi con l'architettura, che viene risolto modificando uno o più proprio 's in consapevoli di ' s (cioè, weak_ptr di).

Non capisco il motivo per cui suggerendo weak_ptr è considerato inutile.

Capisco la sua irritazione per essere disinvoltura ha detto di usare weak_ptr per rompere i riferimenti ciclici e mi sono quasi sentire rabbia quando mi è stato detto che i riferimenti ciclici sono un cattivo stile di programmazione.

Il tuo chiedere specificamente come si fa a individuare i riferimenti ciclici. La verità è che in un progetto complesso alcuni cicli di riferimento sono indiretti e difficili da individuare.

La risposta è che non si deve fare false dichiarazioni che lasciano vulnerabili ai riferimenti ciclici. Io sono serio e io sto criticando una pratica molto popolare -. Ciecamente utilizzando shared_ptr per tutto

Si dovrebbe essere chiaro nel vostro disegno che i puntatori sono proprietari e quali sono gli osservatori.

Per i proprietari usano shared_ptr

Per gli osservatori usano weak_ptr - tutti, non solo quelli che si ritiene possa essere parte di un ciclo

.

Se si segue questa pratica quindi i riferimenti ciclici non causerà alcun problema e non c'è bisogno di preoccuparsi di loro. Naturalmente si avrà un sacco di codice da scrivere per convertire tutti questi weak_ptrs a shared_ptrs quando si desidera utilizzarli -. Boost non è davvero all'altezza del compito

E 'abbastanza facile da rilevare cicli:

  • impostato un conteggio di un numero abbastanza grande, diciamo 1000 (dimensione esatta dipende dalla vostra applicazione)
  • iniziare con la pionter che ti interessa e seguire indicazioni da esso
  • per ogni puntatore si segue, diminuire il conteggio
  • se il numero scende a zero prima di raggiungere la fine della catena puntatore, si dispone di un ciclo

Non è, tuttavia, molto utile. E non è generalmente possibile per risolvere il problema cycvle per i puntatori Ref-contato -. È per questo che i regimi di immondizia colection alternative come scavenging generazione sono stati inventati

Una combinazione di boost::weak_ptr e boost::shared_ptr forse? Questo articolo può essere di interesse.

Si veda questo post su rilevazione cicli in un grafico.

La soluzione generica di trovare un ciclo può essere trovato qui:

miglior algoritmo per verificare se un collegato lista ha un ciclo di

Questo presuppone che si conosce la struttura degli oggetti nella lista, e seguire tutte le indicazioni contenute in ogni oggetto.

Si sono probabilmente bisogno di una tecnica di Garbage Collector, come Marco e Sweep . L'idea di questo algoritmo è:

  1. Tenere un elenco con i riferimenti a tutti i blocchi di memoria allocata.
  2. A un certo punto si avvia il garbage collector:
    1. primi segni di tutti i blocchi che possono comunque accedere senza utilizzare l'elenco di riferimento.
    2. Si passa attraverso la lista cancellando ogni elemento che non è stato possibile applicare, lasciando intendere che non è più raggiungibile, quindi non è utile.

Dal momento che si sta utilizzando shared_ptr tutti i puntatori ancora esistenti non si riesce a raggiungere devono essere considerati come membri di un ciclo.

Attuazione

Sotto descrivo un esempio molto naif di come implementare la parte sweep() dell'algoritmo, ma sarà reset() tutti i puntatori rimanenti sul collettore.

Questo codice negozi shared_ptr<Cycle_t> puntatori. Il Collector classe è responsabile di tenere traccia di tutti i puntatori e l'eliminazione di loro quando viene eseguito 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.
    }
  }
};

È quindi possibile utilizzare in questo modo: 

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();
  }
}

L'ho provato con Valgrind e senza perdite di memoria o "ancora raggiungibile" sono stati elencati i blocchi, quindi è probabilmente funziona come previsto.

Alcune note su questa implementazione:

  1. Il vettore di memoria crescerà senza fine, si consiglia di utilizzare qualche tecnica di allocazione della memoria per assicurarsi che non occupa tutta la memoria di lavoro.
  2. Si può sostenere che non v'è alcuna necessità di utilizzare shared_ptr (che funziona come un GC Riferimento conteggio) per attuare tale Garbage Collector in quanto il marchio e sweep algoritmo sarebbe già prendersi cura del lavoro.
  3. Non ho implementare la funzione contrassegno () perché sarebbe complicare l'esempio, ma è possibile e vi spiegherò qui sotto.

Infine, se siete interessati con (2), questo tipo di implementazione non è inaudito. CPython (la principale implementazione di Python) fa uso di una miscela di conteggio dei riferimenti e Mark e Sweep, ma soprattutto per ragioni storiche .

L'implementazione della funzione mark():

Per implementare la funzione mark() è necessario apportare alcune modifiche:

Si sarebbe necessario aggiungere un attributo bool marked; a Cycle_t, e utilizzarlo per verificare se il puntatore è segnata o meno.

Sarà necessario scrivere la funzione Collector::mark() che sarebbe simile a questa: 

void mark(Ref_t root) {
  root->marked = true;

  // For each other Ref_t stored on root:
  for (Ref_t& item : root) {
    mark(item);
  }
}

E allora si dovrebbe modificare la funzione sweep() per rimuovere il segno se il puntatore è contrassegnato oppure reset() il puntatore: 

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();
      }
    }
  }
}

E 'stata una lunga spiegazione, ma spero che aiuta qualcuno.

Risposta per la vecchia questione, si può provare il puntatore invadente che può dare una mano per contare quante volte la risorsa cui si fa riferimento. 

#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;
}

Ecco il risultato restituito. 

Resource created 
Resource referenced: 1 
Resource referenced: 2 
Program exiting 
Resource unreferenced: 1
Resource unreferenced: 0 
Resource destroyed
*** Program Exit ***

So che hai detto "no weak_ptr" ma perché no? Avere la testa con un weak_ptr alla coda, e la coda con un weak_ptr a capo impedirà il ciclo.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top