Jak zaimplementować Copy-on-Write?

Question

Chcę zaimplementować kopiowanie przy zapisie na mojej niestandardowej klasy C++ String, i zastanawiam się, jak ...

starałem się wdrożyć kilka opcji, ale wszystkie okazały się bardzo nieefektywne.

Dziękuję chłopaki :-)

Answer 1

W wielowątkowych environemnt (co jest w dzisiejszych czasach większość z nich) Krowa jest często ogromna wydajność hit zamiast zysku. I przy ostrożnym użyciu odniesień do stałych, nie ma dużego wzrostu wydajności nawet w środowisku z pojedynczym gwintem.

Ten stary artykuł DDJ wyjaśnia just how bad CoW can be in a multithreaded environment, even if there's only one thread.

Dodatkowo, jak zauważyli inni, ciągi CoW są naprawdę trudne do wdrożenia i łatwo popełniają błędy. To w połączeniu z ich słabymi wynikami w sytuacjach związanych z gwintowaniem sprawia, że ​​naprawdę kwestionuję ich użyteczność w ogóle. Staje się to jeszcze bardziej prawdziwe, gdy zaczniesz używać konstrukcji C++ 11 i przenosisz zadanie.

Jednak, aby odpowiedzieć na to pytanie ....

Oto kilka technik wykonawczych, które mogą pomóc w wydajności.

Najpierw przechowuj długość w ciągu znaków. Dostęp do tej długości jest dość częsty i prawdopodobnie pomogłoby wyeliminowanie dereferencji wskaźnika. Ja bym, po prostu dla spójności, umieścił tam przydzieloną długość. To będzie kosztować cię pod względem swoich obiektów smyczkowych jest trochę większy, ale napowietrznej tam w czasie i przestrzeni kopiowania jest bardzo mały, zwłaszcza, że ​​wartości te będą następnie stają się łatwiejsze do kompilatora do gry ciekawe sztuczki z optymalizacji.

To pozostawia cię z klasy string, który wygląda tak:

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

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

Teraz istnieją dalsze optymalizacje, które można wykonać. Wygląda na to, że klasa Buf tak naprawdę nie zawiera ani nie robi wiele, i to prawda. Dodatkowo wymaga przydziału zarówno instancji Buf, jak i bufora do przechowywania znaków. Wydaje się to raczej marnotrawstwem. Tak, to zwracamy się do wspólnego techniką realizacji C, rozciągliwe bufory:

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

Podczas robienia rzeczy w ten sposób, można następnie potraktować data_->data_ jakby zawierał alloclen_ bajty zamiast tylko 1.

Należy mieć na uwadze, że we wszystkich tych przypadkach trzeba będzie upewnić się, że albo nigdy nie używać to w środowisku wielowątkowym, lub, aby upewnić się, że refct_ to typ, który masz zarówno przyrost atomową, i atomowa dekrementacja i instrukcja testowa dla.

Jest jeszcze bardziej zaawansowane techniki optymalizacji, która polega na wykorzystaniu unii przechowywanie krótkie ciągi prawo wewnątrz bitów danych, które można użyć do opisania dłuższy łańcuch. Ale to jeszcze bardziej skomplikowane i nie sądzę, bym był skłonny do edycji tego, aby umieścić uproszczony przykład tutaj później, ale nigdy nie można powiedzieć.

Answer 2

Nic nie kosztuje CoW. Zasadniczo kopiujesz, gdy chcesz go zmienić, i pozwalasz każdemu, kto nie chce go zmienić, zachować odniesienie do starej instancji. Musisz licznik odniesień do śledzenia kto nadal odwołuje się do obiektu, a ponieważ podczas tworzenia nowej kopii, trzeba zmniejszyć liczbę na „starych” instancji.Skrót polegałby na tym, aby nie zrobić kopii, gdy ta liczba to jedna (jesteś jedyną referencją).

Poza tym niewiele można powiedzieć, chyba że wystąpi specyficzny problem.

Answer 3

Istnieje seria artykułów o tym właśnie w książce Herba Suttera More Exceptional C++. Jeśli nie masz do niego dostępu, możesz wypróbować następujące artykuły internetowe: part 1, part 2 i part 3.

Answer 4

Możesz chcieć emulować ciąg "niezmienny", jaki mają inne języki (Python, C#, o ile wiem).

Chodzi o to, że każdy ciąg jest niezmienny, dlatego każda praca na sznurku tworzy nową niezmienną ... lub to jest podstawowa idea, aby uniknąć eksplozji, nie musiałbyś tworzyć kolejnego, jeśli jest podobny .

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

Sugerowałbym, że jeśli chce się wdrożyć kopiowanie przy zapisie skutecznie (na smyczki lub cokolwiek), należy zdefiniować typ wrapper który będzie zachowywał się jak zmienny łańcucha, i która będzie posiadać zarówno pustych odwołanie do zmiennego łańcucha (żadne inne odniesienie do tego elementu nigdy nie będzie istnieć) i zerowalne odniesienie do "niezmiennych" ciągów (odniesienia do których nigdy nie będzie istnieć poza rzeczami, które nie będą próbowały go zmutować). Opakowania będą zawsze tworzone z co najmniej jednym z tych odniesień, które nie są zerowe; gdy odniesienie do pozycji zmiennoprzecinkowej jest kiedykolwiek ustawione na wartość inną niż null (podczas lub po zakończeniu budowy), zawsze będzie odnosić się do tego samego celu. Za każdym razem, gdy oba odniesienia mają wartość inną niż null, odwołanie do niezmiennego elementu wskaże kopię elementu, który został wykonany jakiś czas po ostatniej zakończonej mutacji (podczas mutacji odwołanie do niezmiennego elementu może lub nie może zawierać odniesienia do wartości przed mutacją).

Aby odczytać obiekt, należy sprawdzić, czy odwołanie do "zmiennego elementu" ma wartość inną niż null. Jeśli tak, użyj go. W przeciwnym razie sprawdź, czy odwołanie do "niezmiennego elementu" ma wartość inną niż null. Jeśli tak, użyj go. W przeciwnym razie użyj odwołania "item zmienny" (które już nie będzie miało wartości NULL).

Aby zmutować obiekt, sprawdź, czy odniesienie do "pozycji zmiennej" ma wartość inną niż null. Jeśli nie, skopiuj cel odniesienia "niezmienny element" i porównajZmień odniesienie do nowego obiektu do pozycji odniesienia "pozycja zmienna". Następnie zmodyfikuj cel odniesienia odniesienia "zmienny przedmiot" i unieważnij odniesienie do "niezmiennych elementów".

Aby sklonować obiekt, jeśli klon ma zostać ponownie sklonowany przed zmutowaniem, należy pobrać wartość odwołania "niezmienny element". Jeśli ma wartość NULL, wykonaj kopię elementu docelowego "zmienny element" i porównaj wartość odniesienia do tego nowego obiektu w odwołanie do niezmiennego elementu. Następnie utwórz nowe opakowanie, którego odwołanie do "pozycji zmiennoprzecinkowych" jest puste i którego odwołanie do "niezmiennego elementu" jest wartością pobraną (jeśli nie była zerowa) lub nową pozycją (jeśli takowa była).

Aby sklonować obiekt, jeśli klon ma zostać zmutowany przed sklonowaniem, należy pobrać wartość odniesienia "niezmienny element". Jeśli null, pobierz odwołanie do "pozycji zmiennej". Skopiuj cel dowolnego odwołania, a następnie utwórz nowe opakowanie, którego odniesienie do "pozycji zmiennoprzecinkowych" wskazuje na nową kopię i którego odwołanie do "niezmiennego elementu" jest puste.

Obie metody klonowania będą semantycznie identyczne, ale wybór niewłaściwej dla danej sytuacji spowoduje dodatkową operację kopiowania. Jeśli konsekwentnie wybierzesz poprawną operację kopiowania, uzyskasz największą korzyść z "agresywnego" kopiowania przy zapisie, ale z dużo mniejszym obciążeniem. Każdy obiekt przechowujący dane (na przykład łańcuch) będzie albo nieudostępniony, albo zmienny, niezmienny i żaden obiekt nigdy nie będzie przełączał się między tymi stanami.W związku z tym można w razie potrzeby wyeliminować wszystkie "narzuty do gwintowania/synchronizacji" (zastępując operacje CompareExchange prostymi magazynami), pod warunkiem, że żaden obiekt opakowania nie jest używany w więcej niż jednym wątku jednocześnie. Dwa obiekty opakowania mogą zawierać odniesienia do tego samego niezmiennego właściciela danych, ale mogą być nieświadome istnienia innych.

Należy pamiętać, że podczas korzystania z tego podejścia może być wymagane kilka dodatkowych operacji kopiowania niż w przypadku stosowania metody "agresywnej". Na przykład, jeśli nowa etykieta zostanie utworzona z nowym ciągiem, a opakowanie zostanie zmutowane i skopiowane sześć razy, oryginalne opakowanie będzie zawierać odniesienia do oryginalnego posiadacza ciągów znaków i niezmiennego pliku przechowującego kopię danych. Sześć skopiowanych owijaczy wystarczyłoby odwołać się do niezmiennego ciągu (dwa ciągi łącznie, chociaż jeśli pierwotny ciąg nigdy nie został zmutowany po wykonaniu kopii, agresywna implementacja mogłaby zająć jeden). Jeśli oryginalne opakowanie zostało zmutowane, wraz z pięcioma z sześciu kopii, wszystkie z wyjątkiem jednego z odwołań do niezmiennego łańcucha zostałyby unieważnione. W tym momencie, jeśli szósta kopia opakowania została zmutowana, agresywna implementacja kopiowania przy zapisie może uświadomić sobie, że zawiera ona jedyne odniesienie do jej ciągu, a tym samym zdecydować, że kopia nie była potrzebna. Wdrożona przeze mnie implementacja utworzyłaby nową zmienną kopię i porzuciłaby niezmienny. Pomimo faktu, że istnieje kilka dodatkowych operacji kopiowania, jednak zmniejszenie narzutu na gwint powinno w większości przypadków zrekompensować koszty. Jeśli większość tworzonych kopii logicznych nigdy nie zostanie zmutowana, takie podejście może być skuteczniejsze niż wykonywanie kopii ciągów.