Implementazione di copy-on-write

2

Ho una classe piuttosto grande che contiene un numero di variabili membro associate. Queste variabili membro possono essere raggruppate in sezioni correlate. Abbiamo notato che il modello di utilizzo della classe è di creare una copia di un'istanza esistente, modificare solo alcune delle variabili membro e quindi lavorare con l'istanza risultante. Ci sono 2 problemi che abbiamo colpito.

  1. Le istanze della classe sono grandi e spesso in pila, quindi sarebbe bello ridurne le dimensioni
  2. La copia di tutte le variabili membro è un po 'lenta.

Quindi abbiamo avuto l'idea di raggruppare le variabili membro associate nei propri oggetti. Questa è solo una buona idea per rendere il codice più facile da capire. Ma se lo facessimo e avessimo ognuno di questi oggetti solo un puntatore condiviso a un'istanza esistente, ridurrebbe la dimensione della classe principale in quanto diverse variabili membro sarebbero state sostituite con un singolo puntatore condiviso. Inoltre accelererebbe la copia, poiché la copia creerebbe semplicemente un nuovo puntatore condiviso che punta all'istanza esistente.

Il problema è che ora ogni volta che dobbiamo scrivere qualcosa in uno di questi oggetti condivisi, dobbiamo fare una copia di esso al momento della prima scrittura. (E dobbiamo controllare su ogni scrittura se è necessario copiarlo o no.) Non scriviamo molto spesso, quindi non penso che sarà un successo in termini di prestazioni. Ma l'implementazione di questo sembra problematico.

C'è un modo per fare in modo che una classe sia copy-on-write quando è necessario modificare una delle sue variabili membro? La classe stessa è scritta in C ++, anche se potrei usare anche C o Objective-C per implementarlo. Ad esempio, non voglio dover scrivere manualmente il controllo del conteggio dei riferimenti del puntatore condiviso in ogni setter. C'è un modo per evitarlo?

    
posta user1118321 02.11.2017 - 07:12
fonte

3 risposte

5

C ++ non ha una copia integrata sulla semantica di scrittura. È possibile implementare tale semantica con una classe di puntatore intelligente o scegliere un approccio a livello di progettazione che rende inutili le copie, ad es. utilizzando il pattern di decorazione . Tuttavia, potresti scoprire che queste ottimizzazioni non valgono il loro sforzo.

Copia su Scrivi puntatore intelligente

L'idea è che i tuoi membri siano memorizzati in un puntatore intelligente che ne gestisce la proprietà. Quando il puntatore intelligente viene copiato, non copierà l'oggetto gestito. Tuttavia, una volta richiesto l'accesso in scrittura, viene eseguita una copia.

Questo non è del tutto banale da correggere, specialmente se ci possono essere altri indicatori nell'oggetto gestito. Alcune implementazioni di CoW si attivano solo quando una copia desidera scrivere sull'oggetto, altre implementazioni eseguono anche una copia quando il proprietario originale scrive sull'oggetto (condiviso).

Dovrai quindi scrivere il tuo puntatore intelligente che implementa la semantica desiderata. Probabilmente, questo può essere implementato con uno sforzo moderato in cima a std::shared_ptr .

Uno svantaggio significativo di CoW è che queste copie pigre possono rendere il tuo codice molto più difficile da eseguire il debug. Copiare un oggetto C ++ può avere effetti collaterali osservabili, ma ora può accadere in momenti imprevisti. Inoltre, ogni accesso in scrittura deve prima controllare lo stato del puntatore intelligente e deve eventualmente dereferenziare più puntatori.

Motivo decoratore

Il motivo decoratore può essere utilizzato per sovrapporre parti di un oggetto con un'implementazione diversa. Ad esempio, potresti voler sovrapporre parti di struct { A a; B b; C c; } . Innanzitutto, dobbiamo definire un'interfaccia in modo da poter combinare i nostri Decoratori:

class Data {
public:
  virtual A& get_a() = 0;
  virtual B& get_b() = 0;
  virtual C& get_c() = 0;
};

Ora possiamo implementare questa interfaccia con una classe di archiviazione di base:

class BaseStorage : public Data {
  A a; B b; C c;
public:
  BaseStorage(A const& a, B const& b, C const& c) : a(a), b(b), c(c) {}
  A& get_a() override { return a; }
  B& get_b() override { return b; }
  C& get_c() override { return c; }
};

Se vogliamo sovrapporre il valore di A , possiamo definire una classe che delega tutte le chiamate a un oggetto base, eccetto per le richieste dei dati A :

class OverlayA : public Data {
  Data& base;
  A a;
public:
  OverlayA(Data& base, A&& a) : base(base), a(std::move(a)) {}
  A& get_a() override { return a; }
  B& get_b() override { return base.get_b(); }
  C& get_c() override { return base.get_c(); }
};

Invece di eseguire una copia di alcuni Data , possiamo ora sovrapporre la parte di essa che stiamo per cambiare:

Data& orig = ...;
// call a function with a copied A
will_change_a(OverlayA(orig, A(orig.get_a())));

Sfortunatamente, questi decoratori rendono davvero difficile scrivere codice const-correct - potresti voler che Data& base sia un riferimento const per evitare scritture nello storage di base, ma l'interfaccia può anche descrivere dati sovrapposti dove le scritture sono necessarie Questo potrebbe essere espresso attraverso i modelli.

Se il comportamento di qualsiasi implementazione dell'interfaccia Data modifica direttamente i campi privati piuttosto che passare attraverso i metodi virtuali, ciò potrebbe non scrivere nei dati sovrapposti. Pertanto, l'interfaccia Data non dovrebbe contenere comportamenti aggiuntivi. È possibile implementare tale comportamento in una classe separata che include un Data& .

Questa tecnica richiede di sapere in anticipo quali parti dell'oggetto devono essere sovrapposte ai dati copiati. In quanto tale, è potenzialmente soggetto a errori.

Lo schema decoratore crea un elenco collegato di sovrapposizioni. Se l'elenco aumenta di molti livelli in profondità, l'inseguimento del puntatore potrebbe danneggiare le prestazioni.

Le copie sono buone

In molti casi, la creazione di una copia è preferibile all'intelligenza come CoW. In particolare, se gli oggetti in questione non sono molto grandi e sono banalmente copiabili, fare una copia ogni volta potrebbe rivelarsi più economico rispetto alle alternative. A causa della memorizzazione nella cache, i puntatori di ricerca tendono ad essere costosi rispetto alle operazioni su oggetti contigui. Sia CoW che Decoratori hanno un overhead continuo per lettura, mentre le copie hanno solo un overhead prevedibile per copia.

Se il tuo profilo determina che le copie sono un problema di prestazioni, allora potrebbe essere sensato provare uno di questi approcci o una combinazione di essi (ad esempio, eseguire una copia ma usare CoW per i membri costosi da copiare come i vettori potrebbe essere ragionevole ). Ove possibile, evita la proprietà di costosi per copiare i dati nel tuo oggetto.

    
risposta data 02.11.2017 - 10:19
fonte
3

Puoi controllare come è fatto in Qt QSharedDataPointer .

L'idea è di avere un puntatore intelligente che implementa operator->() e operator->() const . Il primo eseguirà una copia prima di restituire i dati, mentre il secondo non lo farà.

    
risposta data 02.11.2017 - 10:54
fonte
1

Ho costruito un framework intorno all'immutabilità attraverso qualcosa come COW parziale che mi piace molto (trovato che ha davvero eliminato molte fonti di errori precedenti di gestione dello stato che ho fatto, specialmente con thread multipli che vogliono toccare gli stessi dati), ma la risposta di base alla tua domanda è "no", il C ++ non fornisce le funzionalità linguistiche necessarie per automatizzare e semplificare il processo di creazione di un tipo immutabile in cui alcuni dei suoi campi possono essere modificati senza eseguire una copia profonda dell'intero tipo. Devi rimboccarti le maniche e ideare la tua soluzione.

Per essere in grado di fornire un tipo efficiente immutabile con solo parti di esso copiate in profondità sulla scrittura e con la sicurezza del thread, non è più possibile utilizzarlo con una semplice logica scalare. Prendiamo un array come un semplice esempio:

Immaginiamochel'arrayrealesiamoltopiùgrande(soloperevitaredifareundiagrammaenorme)ocheognisingoloelementonell'arraysiaenormeecostosodacopiare.Intalcaso,dobbiamodividerel'arrayinblocchicontiguipiùpiccoliperpotertrasformareparzialmentel'arrayecopiarloparzialmentesenzacopiaretutto:

Orapossiamomodificaresologlielementinell'intervallo[0,4),inquestomodo:

Tuttavia, cosa significa questo per il codice cliente? Generalmente significa che non possiamo più manipolare la matrice con una semplice logica scalare, altrimenti ci sarebbe un blocco di thread e una copia profonda di elementi da 0 a 3 per ogni singola singola manipolazione di un singolo elemento di matrice nell'intervallo, [0, 4 ). Di conseguenza, dobbiamo progettare un'interfaccia in cui i clienti iniziano a richiedere modifiche a transazioni ingombranti, come un esempio troppo semplicistico:

immutable_array<int> transform(immutable_array<int> data)
{
    // @return A new array with elements in the range
    // [0, 4) replaced with new values.
    const int new_values[] = {666, 666, 666, 69};
    return data.modified(0, 4, new_values);
}

Quindi diventa un po 'ingombrante lavorare con tipi così immutabili, almeno in C ++, anche se un valido compromesso se i benefici sono abbastanza buoni per quanto riguarda la sicurezza (trovo soprattutto immutabilità di questo tipo con parziale COW utile per il multithreading ottenere un codice parallelo che sia ragionevolmente efficiente con garanzie e ragionamenti facili sulla sicurezza che non riesco a ottenere con tipi mutabili che vogliono essere toccati da più thread contemporaneamente).

Tipo di oggetto simile con questo esempio:

class Cyborg
{
public:
   ...
private:
   shared_ptr<Head> head;
   shared_ptr<Arms> torso;
   shared_ptr<Arms> arms;
   shared_ptr<Arms> legs;
};

In questo caso non possiamo fornire in modo efficiente funzioni, almeno in C ++, per modificare solo una parte del tronco del cyborg. Dobbiamo creare un nuovo torso, manipolarlo e commettere una sostituzione del busto del cyborg come una singola transazione. Ancora una volta dobbiamo trasformare le cose in un modo più massiccio e ingombrante.

Detto questo, se l'immutabilità di questo tipo è abbastanza vantaggiosa per te (ho trovato sicuramente il caso per le strutture complesse usate nel contesto multithreaded e per i sistemi di annullamento), allora il gomito necessario per fare questo sia in termini di l'implementazione e il codice client per utilizzare l'interfaccia possono davvero essere utili.

I don't want to have to manually write the check of the shared pointer's reference count in every setter, for example. Is there any way to avoid that?

Se applichi le cose come ho fatto sopra, allora ogni singola funzione che trasforma il tuo tipo immutabile e restituisce una nuova copia parziale non avrà bisogno di eseguire questo controllo. Invece è fatto così per l'esempio cyborg sopra:

void Cyborg::replace_arm(const Arm& new_arm)
{
    // Perform thread lock as needed.
    arm = make_shared(new_arm);
}

Se vuoi garantire che i cyborg siano immutabili, allora lo fai e tutte le funzioni dei membri saranno di sola lettura:

Cyborg Cyborg::replace_arm(const Arm& new_arm) const
{
    // Perform thread lock as needed.
    Cyborg new_cyborg = *this;
    new_cyborg.arm = make_shared(new_arm);
    return new_cyborg;
}

È un diverso tipo di approccio COW dalle vecchie versioni di std::string che devono essere contrassegnate quando viene copiata la stringa nel suo complesso, ma richiede un'interfaccia che modifichi blocchi di dati ragionevolmente grandi in massa come una transazione atomica per la sicurezza dei thread ed efficienza. La tua interfaccia non può consistere in semplici setter per modificare piccoli pezzi di dati come un piccolo elemento scalare (es: un singolo carattere di una stringa o un singolo dado e un fulmine sul braccio di un cyborg). Se stai per impostare / sostituire qualcosa, dovrebbe essere qualcosa di grande perché ogni singola funzione membro che modifica lo stato, se ne hai, creerà una nuova copia modificata di qualcosa di grande come una transazione ingombrante.

Non sono sicuro che valga la pena chiamare più copy-on-write tanto quanto implementazioni di tipi immutabili, ma è una soluzione al tuo problema di dover copiare ripetutamente ogni pezzo di dati di un oggetto enorme quando solo alcune parti devono essere rese uniche. Naturalmente puoi progettare classi intermedie, come Arm , che ti permettono di modificare piccole parti di esso prima di commettere una sostituzione di braccio come una transazione atomica a un cyborg o di crearne una nuova versione immutabile con un braccio diverso. / p>     

risposta data 29.11.2017 - 11:24
fonte

Leggi altre domande sui tag