Come implementare Copy-on-Write?

Question

Voglio implementare una copia su scrittura sulla mia classe di stringhe C++ personalizzata e mi chiedo come ...

Ho cercato di implementare alcune opzioni, ma sono risultate tutte molto inefficienti.

Grazie ragazzi :-)

Answer 1

In un environemnt multi-threaded (che è la maggior parte di loro al giorno d'oggi) mucca è spesso una performance enorme successo piuttosto che un guadagno. E con un uso attento dei riferimenti const, non è un vantaggio in termini di prestazioni anche in un singolo ambiente con thread.

Questo vecchio articolo del DDJ spiega just how bad CoW can be in a multithreaded environment, even if there's only one thread.

Inoltre, come altre persone hanno sottolineato, le stringhe di CoW sono davvero difficili da implementare ed è facile commettere errori. Ciò, unito alle loro scarse prestazioni nelle situazioni di threading, mi fa davvero dubitare della loro utilità in generale. Ciò diventa ancora più vero una volta che inizi a utilizzare C++ 11 per spostare la costruzione e spostare l'assegnazione.

Ma, per rispondere alla tua domanda ....

Qui ci sono un paio di tecniche di attuazione che possono aiutare con le prestazioni.

Innanzitutto, memorizzare la lunghezza nella stringa stessa. La lunghezza è abbastanza frequente e l'eliminazione del puntatore della dereferenziazione potrebbe essere di aiuto. Vorrei, solo per coerenza, mettere anche la lunghezza assegnata. Questo ti costerà in termini di oggetti di stringa un po 'più grandi, ma il sovraccarico nello spazio e il tempo di copiatura è molto piccolo, soprattutto perché questi valori diventeranno più facili con il compilatore per giocare interessanti trucchi di ottimizzazione.

Questo ti lascia con una classe stringa che assomiglia a questo:

class MyString { 
    ... 
private: 
    class Buf { 
     ... 
    private: 
     ::std::size_t refct_; 
     char *data_; 
    }; 

    ::std::size_t len_; 
    ::std::size_t alloclen_; 
    Buf *data_; 
}; 

Ora, ci sono ulteriori ottimizzazioni che è possibile eseguire. La classe Buf sembra che non contenga o faccia molto, e questo è vero. Inoltre, richiede l'allocazione di un'istanza di Buf e di un buffer per contenere i caratteri. Questo sembra piuttosto dispendioso. Quindi, si passerà a una tecnica comune C implementazione, tamponi elastici:

class MyString { 
    ... 
private: 
    struct Buf { 
     ::std::size_t refct_; 
     char data_[1]; 
    }; 

    void resizeBufTo(::std::size_t newsize); 
    void dereferenceBuf(); 

    ::std::size_t len_; 
    ::std::size_t alloclen_; 
    Buf *data_; 
}; 

void MyString::resizeBufTo(::std::size_t newsize) 
{ 
    assert((data_ == 0) || (data_->refct_ == 1)); 
    if (newsize != 0) { 
     // Yes, I'm using C's allocation functions on purpose. 
     // C++'s new is a poor match for stretchy buffers. 
     Buf *newbuf = ::std::realloc(data_, sizeof(*newbuf) + (newsize - 1)); 
     if (newbuf == 0) { 
     throw ::std::bad_alloc(); 
     } else { 
     data_ = newbuf_; 
     } 
    } else { // newsize is 0 
     if (data_ != 0) { 
     ::std::free(data_); 
     data_ = 0; 
     } 
    } 
    alloclen_ = newsize; 
} 

Quando si fanno le cose in questo modo, si può quindi trattare data_->data_ come se contenesse alloclen_ byte invece di appena 1.

Tieni presente che in tutti questi casi dovrai assicurarti di non utilizzarlo mai in un ambiente multi-thread o di assicurarti che lo refct_ sia un tipo con un incremento sia atomico sia un atomico decremento e test di istruzioni per.

Esiste una tecnica di ottimizzazione ancora più avanzata che prevede l'utilizzo di un'unione per archiviare brevi stringhe all'interno dei bit di dati che si utilizzerebbero per descrivere una stringa più lunga. Ma questo è ancora più complesso, e non penso che mi sentirò propenso a modificare questo per mettere un esempio semplificato qui più tardi, ma non si può mai dire.

Answer 2

Non c'è molto da fare a CoW. Fondamentalmente, copi quando vuoi cambiarlo e lascia che chiunque non voglia cambiarlo mantenga il riferimento alla vecchia istanza. Avrai bisogno del conteggio dei riferimenti per tenere traccia di chi fa ancora riferimento all'oggetto e, dal momento che stai creando una nuova copia, devi ridurre il conteggio sull'istanza "vecchia".Una scorciatoia sarebbe quella di non fare una copia quando quel conteggio è uno (sei l'unico riferimento).

Oltre a ciò, non c'è molto che si può dire, a meno che non ci sia un problema specifico che stai affrontando.

Answer 3

C'è una serie di articoli su questo esattamente sul libro More Exceptional C++ di Herb Sutter. Se non hai accesso ad esso, puoi provare a seguire gli articoli su Internet: part 1, part 2 e part 3.

Answer 4

Si potrebbe voler emulare la stringa "immutable" che hanno altri linguaggi (Python, C# per quanto ne so).

L'idea è che ogni stringa è immutabile, quindi qualsiasi lavoro su una stringa crea una nuova immutabile ... o questa è l'idea di base, per evitare l'esplosione, non avresti bisogno di crearne un'altra se ce n'è una simile .

Answer 5

template <class T> struct cow { 
    typedef boost::shared_ptr<T> ptr_t; 
    ptr_t _data; 

    ptr_t get() 
    { 
    return boost::atomic_load(&_data); 
    } 

    void set(ptr_t const& data) 
    { 
    boost::atomic_store(&_data, data); 
    } 
} 

Answer 6

Vorrei suggerire che se si vuole implementare copy-on-write in modo efficiente (per le stringhe o qualsiasi altra cosa), si dovrebbe definire un tipo di involucro, che si comporterà come una stringa mutabile, e che si terrà sia annullabile riferimento a una stringa mutabile (nessun altro riferimento a quell'elemento sarà mai esistito) e un riferimento nullable a una stringa "immutabile" (riferimenti a cui non esisterà mai al di fuori di cose che non cercheranno di mutarlo). I wrapper verranno sempre creati con almeno uno di questi riferimenti non null; una volta che il riferimento di oggetto mutabile è mai stato impostato su un valore non nullo (durante o dopo la costruzione) si riferirà per sempre allo stesso obiettivo. Ogni volta che entrambi i riferimenti sono non nulli, il riferimento all'elemento immutabile indicherà una copia dell'articolo che è stata fatta qualche tempo dopo la mutazione completata più recente (durante una mutazione, il riferimento all'elemento immutabile può o non può contenere un riferimento a un valore di pre-mutazione).

Per leggere un oggetto, verificare se il riferimento "oggetto mutabile" non è nullo. Se è così, usalo. Altrimenti, controlla se il riferimento "oggetto immutabile" non è nullo. Se è così, usalo. Altrimenti, usa il riferimento "oggetto mutabile" (che ora sarà non nullo).

Per mutare un oggetto, verificare se il riferimento "oggetto mutabile" non è nullo. In caso contrario, copia il target del riferimento "oggetto immutabile" e confrontaExchange un riferimento al nuovo oggetto nel riferimento "oggetto mutabile". Quindi modifica la destinazione del riferimento "oggetto mutabile" e invalida il riferimento "oggetto immutabile".

Per clonare un oggetto, se si prevede che il clone verrà clonato nuovamente prima che venga mutato, recuperare il valore del riferimento "oggetto immutabile". Se è nullo, crea una copia del target "oggetto mutabile" e confrontaExchange un riferimento a quel nuovo oggetto nel riferimento all'elemento immutabile. Quindi crea un nuovo wrapper il cui riferimento "oggetto mutabile" è nullo e il cui riferimento "oggetto immutabile" è il valore recuperato (se non era nullo) o il nuovo elemento (se lo era).

Per clonare un oggetto, se si prevede che il clone venga mutato prima di essere clonato, recuperare il valore del riferimento "oggetto immutabile". Se null, recupera il riferimento "oggetto mutabile". Copia l'obiettivo di qualunque riferimento è stato recuperato e crea un nuovo wrapper il cui riferimento "oggetto mutabile" punta alla nuova copia e il cui riferimento "oggetto immutabile" è nullo.

I due metodi di clonazione saranno semanticamente identici, ma selezionando quello sbagliato per una determinata situazione si otterrà un'operazione di copia aggiuntiva. Se si sceglie coerentemente l'operazione di copia corretta, si otterrà il massimo vantaggio da un approccio "aggressivo" copy-on-write, ma con un sovraccarico molto meno threading. Ogni oggetto di conservazione dei dati (ad esempio una stringa) può essere non condiviso mutabile o condiviso immutabile e nessun oggetto passerà mai da uno stato all'altro.Di conseguenza, se lo si desidera, è possibile eliminare tutto il "sovraccarico di threading/sincronizzazione" (sostituendo le operazioni di CompareExchange con gli archivi diretti) a condizione che nessun oggetto wrapper sia utilizzato in più thread contemporaneamente. Due oggetti wrapper potrebbero contenere riferimenti allo stesso titolare di dati immutabili, ma potrebbero essere ignari dell'esistenza reciproca.

Si noti che alcune operazioni di copia potrebbero essere necessarie quando si utilizza questo approccio rispetto a quando si utilizza un approccio "aggressivo". Ad esempio, se un nuovo wrapper viene creato con una nuova stringa e tale wrapper viene mutato e copiato sei volte, il wrapper originale manterrà i riferimenti al titolare della stringa originale e uno immutabile contenente una copia dei dati. I sei wrapper copiati avrebbero solo mantenuto un riferimento alla stringa immutabile (due stringhe totali, sebbene se la stringa originale non fosse mai stata modificata dopo la copia, un'implementazione aggressiva potrebbe cavarsela con una). Se il wrapper originale fosse mutato, insieme a cinque delle sei copie, tutti i riferimenti tranne uno alla stringa immutabile sarebbero stati invalidati. A quel punto, se la sesta copia del wrapper venisse mutata, un'implementazione aggressiva di copia su scrittura potrebbe rendersi conto che conteneva l'unico riferimento alla sua stringa, e quindi decidere che una copia non era necessaria. L'implementazione che descrivo, tuttavia, creerebbe una nuova copia mutevole e abbandonerebbe quella immutabile. Nonostante il fatto che ci siano alcune operazioni di copia extra, tuttavia, la riduzione del sovraccarico di threading dovrebbe in molti casi più che compensare il costo. Se la maggior parte delle copie logiche prodotte non vengono mai mutate, questo approccio potrebbe essere più efficiente di fare sempre copie di stringhe.