Legalność implementacji COW std :: string w C ++ 11

Zrozumiałem, że kopiowanie przy zapisie nie jest realnym sposobem implementacji zgodności std::stringw C ++ 11, ale kiedy pojawiło się to niedawno w dyskusji, nie mogłem bezpośrednio poprzeć tego stwierdzenia.

Czy mam rację, że C ++ 11 nie dopuszcza implementacji opartych na COW std::string?

Jeśli tak, czy to ograniczenie zostało wyraźnie określone gdzieś w nowym standardzie (gdzie)?

Czy też to ograniczenie jest implikowane w tym sensie, że jest to połączony efekt nowych wymagań, std::stringktóry wyklucza implementację opartą na COW std::string. W tym przypadku byłbym zainteresowany wyprowadzeniem stylu rozdziałów i wersetów „C ++ 11 skutecznie zabrania std::stringimplementacji opartych na COW ”.

Nie jest to dozwolone, ponieważ zgodnie ze standardem 21.4.1 p6 unieważnienie iteratorów / referencji jest dozwolone tylko dla

- jako argument dla dowolnej standardowej funkcji bibliotecznej, przyjmującej jako argument odwołanie do non-const basic_string.

- Wywoływanie funkcji składowych innych niż const, z wyjątkiem operatora [], at, front, back, begin, rbegin, end i rend.

W przypadku łańcucha COW wywołanie wartości innej niż const operator[]wymagałoby wykonania kopii (i unieważnienia odniesień), co jest zabronione w powyższym akapicie. Dlatego nie jest już legalne posiadanie ciągu COW w C ++ 11.

Odpowiedzi udzielone przez Dave S i gbjbaanb są prawidłowe . (I Luc Danton też ma rację, chociaż jest to raczej efekt uboczny zakazu ciągów COW niż oryginalna zasada, która zabrania tego).

Ale żeby wyjaśnić pewne nieporozumienia, dodam trochę dalszych wyjaśnień. Różne komentarze odsyłają do mojego komentarza na bugzilli GCC, który podaje następujący przykład:

std::string s("str");
const char* p = s.data();
{
    std::string s2(s);
    (void) s[0];
}
std::cout << *p << '\n';  // p is dangling

Celem tego przykładu jest wykazanie, dlaczego ciąg zliczanych referencji (COW) GCC nie jest prawidłowy w C ++ 11. Standard C ++ 11 wymaga, aby ten kod działał poprawnie. Nic w kodzie nie pozwala na punieważnienie w C ++ 11.

Używając starej std::stringimplementacji zliczanej odwołań GCC , ten kod ma niezdefiniowane zachowanie, ponieważ p jest unieważniony, stając się wiszącym wskaźnikiem. (Dzieje się tak, że gdy s2jest skonstruowany, udostępnia dane s, ale uzyskanie odniesienia innego niż const za pośrednictwem s[0]wymaga, aby dane nie były udostępniane, więc s„kopia podczas zapisu”, ponieważ referencja s[0]może potencjalnie zostać użyta do zapisu s, a następnie s2przechodzi poza zakresem, niszcząc tablicę wskazywaną przez p).

Standard C ++ 03 wyraźnie zezwala na takie zachowanie w 21.3 [lib.basic.string] p5, gdzie mówi, że po wywołaniu data()pierwszego wywołania operator[]()może unieważnić wskaźniki, referencje i iteratory. Zatem łańcuch COW GCC był poprawną implementacją C ++ 03.

Standard C ++ 11 nie zezwala już na takie zachowanie, ponieważ żadne wywołanie nie operator[]()może unieważnić wskaźników, odwołań lub iteratorów, niezależnie od tego, czy następują po wywołaniu data().

Zatem powyższy przykład musi działać w C ++ 11, ale nie działa z łańcuchem typu COW typu libstdc ++, dlatego ten rodzaj łańcucha COW nie jest dozwolony w C ++ 11.

To znaczy, CoW jest akceptowalnym mechanizmem tworzenia szybszych ciągów ... ale ...

spowalnia wielowątkowość kodu (całe to blokowanie, aby sprawdzić, czy jesteś jedyną osobą piszącą, zabija wydajność, gdy używasz wielu ciągów). To był główny powód, dla którego CoW został zabity lata temu.

Innym powodem jest to, że []operator zwróci ci dane ciągu, bez żadnej ochrony, abyś mógł nadpisać ciąg, którego ktoś inny oczekuje, że będzie niezmienny. To samo dotyczy c_str()i data().

Szybki Google mówi, że wielowątkowość jest w zasadzie powodem, dla którego została skutecznie zabroniona (nie jawnie).

Propozycja mówi:

Wniosek

Proponujemy, aby wszystkie operacje iteratora i dostępu do elementów były bezpiecznie wykonywane jednocześnie.

Zwiększamy stabilność operacji nawet w kodzie sekwencyjnym.

Ta zmiana skutecznie uniemożliwia implementacje kopiowania przy zapisie.

śledzony przez

Największa potencjalna utrata wydajności spowodowana odejściem od implementacji kopiowania przy zapisie to zwiększone zużycie pamięci przez aplikacje z bardzo dużymi ciągami znaków do odczytu. Uważamy jednak, że dla tych zastosowań liny są lepszym rozwiązaniem technicznym i zalecamy rozważenie propozycji lin do włączenia do Biblioteki TR2.

Liny są częścią STLPort i SGIs STL.

Od 21.4.2 konstruktory basic_string i operatory przypisania [string.cons]

basic_string(const basic_string<charT,traits,Allocator>& str);

[…]

2 Efekty : Konstruuje obiekt klasy basic_stringzgodnie z tabelą 64. [...]

Tabela 64 w pomocny sposób dokumentuje, że po skonstruowaniu obiektu za pomocą tego (kopiującego) konstruktora this->data()ma wartość:

wskazuje na pierwszy element przydzielonej kopii tablicy, na której pierwszy element jest wskazywany przez str.data ()

Podobne wymagania są stawiane innym podobnym konstruktorom.

Ponieważ jest teraz gwarantowane, że ciągi są przechowywane w sposób ciągły i możesz teraz wziąć wskaźnik do wewnętrznej pamięci ciągu (tj. & Str [0] działa tak jak dla tablicy), nie jest możliwe utworzenie użytecznego COW realizacja. Musiałbyś zrobić kopię dla zbyt wielu rzeczy. Nawet samo użycie operator[]lub begin()na łańcuchu innym niż const wymagałoby kopii.

Czy COW jest basic_stringzabronione w C ++ 11 i nowszych?

Jeżeli chodzi o

„ Czy mam rację, że C ++ 11 nie dopuszcza implementacji opartych na COW std::string?

Tak.

Jeżeli chodzi o

„ Jeśli tak, to czy to ograniczenie zostało wyraźnie określone gdzieś w nowym standardzie (gdzie)?

Niemal bezpośrednio, przez wymagania stałej złożoności dla wielu operacji, które wymagałyby O ( n ) fizycznego kopiowania danych łańcuchowych w implementacji COW.

Na przykład dla funkcji składowych

auto operator[](size_type pos) const -> const_reference;
auto operator[](size_type pos) -> reference;

… Co w implementacji COW ¹ spowodowałoby kopiowanie danych ciągów w celu cofnięcia udostępniania wartości ciągu, standard C ++ 11 wymaga

„ Złożoność: stały czas.

… Co wyklucza takie kopiowanie danych, a tym samym COW.

C ++ 03 obsługiwane przez implementacje krowa nie posiadające tych wymagań stałą złożoność, oraz, pod pewnymi warunkami ograniczającymi, pozwalając połączeń do operator[](), at(), begin(), rbegin(), end(), lub rend()do unieważnienia piśmiennictwem, wskaźników i iteratory nawiązujących do elementów łańcuchowych, czyli ewentualnie ponieść Kopiowanie danych COW. Ta obsługa została usunięta w C ++ 11.

Czy COW jest również zabronione przez reguły unieważniania C ++ 11?

W innej odpowiedzi, która w chwili pisania tego tekstu została wybrana jako rozwiązanie i która jest silnie przegłosowana i dlatego najwyraźniej wierzy, że

„ W przypadku łańcucha COW wywołanie non- const operator[]wymagałoby wykonania kopii (i unieważnienia odniesień), co jest zabronione przez [cytowany] akapit powyżej [C ++ 11 §21.4.1 / 6]. Dlatego nie jest już legalne posiadanie ciągu COW w C ++ 11.

To stwierdzenie jest błędne i mylące z dwóch głównych powodów:

• Wskazuje niepoprawnie, że tylko metody dostępu niebędące constpozycjami muszą wyzwalać kopiowanie danych COW.
  Ale także constakcesory elementów muszą wyzwalać kopiowanie danych, ponieważ pozwalają one kodowi klienta na tworzenie referencji lub wskaźników, których (w C ++ 11) nie można później unieważnić poprzez operacje, które mogą wywołać kopiowanie danych COW.
• Niepoprawnie zakłada, że ​​kopiowanie danych COW może spowodować unieważnienie odniesienia.
  Ale w poprawnej implementacji kopiowanie danych COW, cofanie udostępniania wartości ciągu, jest wykonywane w momencie, gdy istnieją jakiekolwiek odwołania, które można unieważnić.

Aby zobaczyć, jak poprawna implementacja COW w C ++ 11 basic_stringdziałałaby, gdy wymagania O (1), które powodują, że jest to nieprawidłowe, są ignorowane, pomyśl o implementacji, w której łańcuch może przełączać się między zasadami własności. Instancja typu string zaczyna się od zasady Sharable. Gdy ta polityka jest aktywna, nie może być żadnych odwołań do elementów zewnętrznych. Instancja może przejść do strategii Unique i musi to zrobić, gdy potencjalnie zostanie utworzone odwołanie do elementu, na przykład z wywołaniem .c_str()(przynajmniej jeśli spowoduje to wyświetlenie wskaźnika do bufora wewnętrznego). W ogólnym przypadku wielu wystąpień współdzielących własność wartości pociąga za sobą kopiowanie danych ciągu. Po przejściu do unikalnej zasady instancja może przejść z powrotem do Sharable tylko przez operację, która unieważnia wszystkie odwołania, takie jak przypisanie.

Tak więc, chociaż wniosek tej odpowiedzi, że łańcuchy COW są wykluczone, jest poprawny, przedstawione rozumowanie jest nieprawidłowe i mocno mylące.

Podejrzewam, że przyczyną tego nieporozumienia jest nienormatywna uwaga w załączniku C C ++ 11:

Zmiana : basic_stringwymagania nie zezwalają już na ciągi zliczane jako odwołania
Uzasadnienie: Unieważnienie jest nieco inne niż w przypadku ciągów zliczanych jako odwołania. Ta zmiana reguluje zachowanie (sic) dla niniejszej Normy Międzynarodowej.
Wpływ na oryginalną funkcję: Prawidłowy kod C ++ 2003 może działać inaczej w ramach niniejszej Normy Międzynarodowej

Tutaj uzasadnienie wyjaśnia główne, dlaczego zdecydowano się usunąć specjalną obsługę COW C ++ 03. To uzasadnienie, dlaczego , nie jest tym, jak norma skutecznie zabrania implementacji COW. Norma zabrania COW poprzez wymagania O (1).

Krótko mówiąc, reguły unieważnienia C ++ 11 nie wykluczają implementacji COW std::basic_string. Ale wykluczają w miarę wydajną, nieograniczoną implementację COW w stylu C ++ 03, taką jak ta w przynajmniej jednej z implementacji bibliotek standardowych g ++. Specjalna obsługa C ++ 03 COW zapewniła praktyczną wydajność, w szczególności przy użyciu constakcesorów do elementów, kosztem subtelnych, złożonych reguł unieważniania:

” Referencje, wskazówki i iteratory odnoszące się do elementów basic_stringsekwencji może być unieważnione w następujących zastosowaniach tego basic_stringobiektu
- jako argument funkcji trzecimi swap()(21.3.7.8), operator>>()(21.3.7.9) i getline()(21.3. 7.9).
- Jako argument do basic_string::swap().
- Funkcje wywoławcze data()i c_str()członkowskie.
- Wywołanie innych niż constfunkcje składowe, z wyjątkiem operator[](), at(), begin(), rbegin(), end(), i rend().
- Po dowolnego z powyższych zastosowań, z wyjątkiem form insert()i erase()które zwracają iteratorami, pierwsze połączenie na bez constfunkcji składowych operator[](), at(), begin(), rbegin(),end()lub rend().

Zasady te są tak złożone i subtelne, że wątpię, aby wielu programistów, jeśli w ogóle w ogóle, potrafiło podać dokładne podsumowanie. Nie mógłbym.

Co się stanie, jeśli zignoruje się wymagania O (1)?

Jeśli np. Wymagania dotyczące stałego czasu C ++ 11 operator[]zostaną zignorowane, wówczas COW dla basic_stringmoże być technicznie wykonalne, ale trudne do wdrożenia.

Operacje, które mogłyby uzyskać dostęp do zawartości łańcucha bez powodowania kopiowania danych COW obejmują:

• Łączenie za pośrednictwem +.
• Wyjście przez <<.
• Używanie basic_stringjako argumentu do standardowych funkcji bibliotecznych.

To drugie, ponieważ biblioteka standardowa może polegać na specyficznej dla implementacji wiedzy i konstrukcjach.

Dodatkowo implementacja może oferować różne niestandardowe funkcje dostępu do zawartości łańcucha bez wyzwalania kopiowania danych COW.

Głównym czynnikiem komplikującym jest to, że w C ++ 11 basic_stringdostęp do pozycji musi wyzwalać kopiowanie danych (cofanie udostępniania danych ciągu), ale nie jest wymagany, aby go nie rzucać , np. C ++ 11 §21.4.5 / 3 „ Zgłasza: Nic.”. Dlatego nie może używać zwykłej alokacji dynamicznej do tworzenia nowego bufora do kopiowania danych COW. Jednym ze sposobów obejścia tego jest użycie specjalnej sterty, w której można zarezerwować pamięć bez faktycznej alokacji, a następnie zarezerwowanie wymaganej ilości dla każdego logicznego odwołania do wartości ciągu. Rezerwowanie i anulowanie rezerwacji w takiej stercie może być stałe w czasie, O (1), a alokowanie kwoty, którą już zarezerwowano, może byćnoexcept. Aby spełnić wymagania normy, przy takim podejściu wydaje się, że potrzebna byłaby jedna taka specjalna sterta oparta na rezerwacji dla każdego rozdzielacza.

^{Uwagi:
¹ Akcesor constpozycji wyzwala kopiowanie danych COW, ponieważ umożliwia kodowi klienta uzyskanie odniesienia lub wskaźnika do danych, których nie można unieważnić przez późniejsze kopiowanie danych wyzwalane np. Przez constakcesor niebędący elementem.}

Zawsze zastanawiałem się nad niezmiennymi krowami: kiedy krowa zostanie stworzona, mogłem się zmienić tylko poprzez przypisanie z innej krowy, dzięki czemu będzie to zgodne ze standardem.

Miałem dziś czas, aby wypróbować to w celu przeprowadzenia prostego testu porównawczego: mapa o rozmiarze N z kluczem ciąg / krowa, z każdym węzłem zawierającym zestaw wszystkich ciągów na mapie (mamy liczbę obiektów NxN).

Przy łańcuchach o rozmiarze ~ 300 bajtów i N = 2000 krowy są nieco szybsze i używają prawie o rząd wielkości mniej pamięci. Zobacz poniżej, rozmiary podano w kilogramach, wybieg b dotyczy krów.

~/icow$ ./tst 2000
preparation a
run
done a: time-delta=6 mem-delta=1563276
preparation b
run
done a: time-delta=3 mem-delta=186384