Zrozumiałem, że kopiowanie przy zapisie nie jest realnym sposobem implementacji zgodności std::string
w 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::string
któ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::string
implementacji opartych na COW ”.
Odpowiedzi:
Nie jest to dozwolone, ponieważ zgodnie ze standardem 21.4.1 p6 unieważnienie iteratorów / referencji jest dozwolone tylko dla
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.źródło
std::string a("something"); char& c1 = a[0]; std::string b(a); char& c2 = a[1];
c1 jest odniesieniem do a. Następnie „skopiuj” a. Następnie, gdy spróbujesz wziąć referencję po raz drugi, musi wykonać kopię, aby uzyskać referencję inną niż stała, ponieważ istnieją dwa ciągi wskazujące na ten sam bufor. To musiałoby unieważnić pierwsze wzięte odniesienie i jest sprzeczne z cytowaną powyżej sekcją.operator[]
(1) musi wykonać kopię i (2) jest to nielegalne. Z którym z tych dwóch punktów się nie zgadzasz? Patrząc na twój pierwszy komentarz, wydaje się, że implementacja mogłaby udostępniać ciąg, przynajmniej zgodnie z tym wymaganiem, aż do momentu uzyskania do niego dostępu, ale zarówno dostęp do odczytu, jak i do zapisu musiałby cofnąć udostępnianie. Czy to twoje rozumowanie?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:
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
p
unieważnienie w C ++ 11.Używając starej
std::string
implementacji 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 gdys2
jest skonstruowany, udostępnia danes
, ale uzyskanie odniesienia innego niż const za pośrednictwems[0]
wymaga, aby dane nie były udostępniane, więcs
„kopia podczas zapisu”, ponieważ referencjas[0]
może potencjalnie zostać użyta do zapisus
, a następnies2
przechodzi poza zakresem, niszcząc tablicę wskazywaną przezp
).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łaniaoperator[]()
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łaniudata()
.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.
źródło
.data()
(i przy każdym zwróceniu wskaźnika, odwołania lub iteratora) nie cierpi z powodu tego problemu. To znaczy (niezmienny) bufor jest w dowolnym momencie niewspółdzielony lub współdzielony bez zewnętrznych referencji. Myślałem, że zamierzyłeś komentarz na temat tego przykładu jako nieformalne zgłoszenie błędu jako komentarz, bardzo przepraszam za nieporozumienie! Ale jak widać, rozważając taką implementację, jak tutaj opisuję, która działa dobrze w C ++ 11, gdynoexcept
wymagania są ignorowane, przykład nie mówi nic o formalności. Mogę podać kod, jeśli chcesz.std::string
, i szczerze wątpię, czy możesz zademonstrować przydatny, wydajny ciąg COW, który spełnia wymagania dotyczące unieważniania C ++ 11. Dlatego uważam, żenoexcept
specyfikacje dodane w ostatniej chwili są konsekwencją zakazu ciągów COW, a nie przyczyną. N2668 wydaje się zupełnie jasne, dlaczego nadal zaprzeczasz wyraźnym dowodom intencji komitetu, które zostały tam przedstawione?data()
jest to stała funkcja składowa, więc musi być bezpieczna, aby wywołać ją jednocześnie z innymi stałymi składowymi i na przykład wywołaćdata()
współbieżnie z innym wątkiem wykonującym kopię ciągu. Będziesz więc potrzebował całego narzutu muteksu dla każdej operacji na łańcuchach, nawet tych stałych, lub złożoności niezabezpieczonej, zmiennej struktury liczonej jako referencje, a po tym wszystkim, udostępniasz tylko wtedy, gdy nigdy nie zmodyfikujesz ani nie uzyskasz dostępu twoje łańcuchy, tak wiele, wiele łańcuchów będzie miało liczbę odwołań równą jeden. Proszę podać kod, nie krępuj się zignorowaćnoexcept
gwarancji.basic_string
funkcji składowych plus funkcje bezpłatne. Koszt abstrakcji: ten niezoptymalizowany, niezoptymalizowany, świeży kod wersji zerowej jest od 50 do 100% wolniejszy zarówno w przypadku g ++, jak i MSVC. Nie zapewnia bezpieczeństwa wątków (shared_ptr
wydaje mi się, że jest to łatwe do wykorzystania ) i wystarczy, aby obsługiwać sortowanie słownika na potrzeby synchronizacji, ale błędy modulo dowodzą, że zliczane odwołaniabasic_string
są dozwolone, z wyjątkiemnoexcept
wymagań C ++ . github.com/alfps/In-principle-demo-of-ref-counted-basic_stringTo 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 dotyczyc_str()
idata()
.Szybki Google mówi, że wielowątkowość jest w zasadzie powodem, dla którego została skutecznie zabroniona (nie jawnie).
Propozycja mówi:
śledzony przez
Liny są częścią STLPort i SGIs STL.
źródło
Od 21.4.2 konstruktory basic_string i operatory przypisania [string.cons]
Tabela 64 w pomocny sposób dokumentuje, że po skonstruowaniu obiektu za pomocą tego (kopiującego) konstruktora
this->data()
ma wartość:Podobne wymagania są stawiane innym podobnym konstruktorom.
źródło
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[]
lubbegin()
na łańcuchu innym niż const wymagałoby kopii.źródło
c_str()
) musi mieć wartość O (1) i nie może rzucać i nie może wprowadzać wyścigów danych, więc bardzo trudno jest spełnić te wymagania, jeśli leniwie łączysz się. W praktyce jedyną rozsądną opcją jest przechowywanie ciągłych danych.Czy COW jest
basic_string
zabronione w C ++ 11 i nowszych?Jeżeli chodzi o
Tak.
Jeżeli chodzi o
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
… 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
C ++ 11 §21.4.5 / 4 :… 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()
, lubrend()
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
To stwierdzenie jest błędne i mylące z dwóch głównych powodów:
const
pozycjami muszą wyzwalać kopiowanie danych COW.Ale także
const
akcesory 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.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_string
dział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:
C ++ 11 §C.2.11 [diff.cpp03.strings], o §21.3: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
C ++ 03 §21.3 / 5, który obejmuje obsługę COW „pierwszego połączenia”: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życiuconst
akcesorów do elementów, kosztem subtelnych, złożonych reguł unieważniania: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 dlabasic_string
moż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ą:
+
.<<
.basic_string
jako 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_string
dostę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
const
pozycji 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. Przezconst
akcesor niebędący elementem.źródło
std::string
, pomijając wymagania O (1), byłaby nieefektywna, jest Twoją opinią. Nie wiem, jaki mógłby być występ, ale myślę, że to stwierdzenie jest wysuwane bardziej ze względu na jego odczucie, ze względu na wibracje, które przekazuje, niż ze względu na jakiekolwiek znaczenie dla tej odpowiedzi.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.
źródło