Ta odpowiedź daje ładny, ogólny przegląd optymalizacji krótkich ciągów (SSO). Chciałbym jednak dowiedzieć się bardziej szczegółowo, jak to działa w praktyce, szczególnie w implementacji libc ++:
Jak krótki musi być ciąg znaków, aby kwalifikować się do logowania jednokrotnego? Czy to zależy od docelowej architektury?
W jaki sposób implementacja rozróżnia krótkie i długie ciągi podczas uzyskiwania dostępu do danych ciągu? Czy jest to tak proste, jak
m_size <= 16
flaga, która jest częścią innej zmiennej składowej? (Wyobrażam sobie, żem_size
lub jego część może być również używana do przechowywania danych ciągów).
Zadałem to pytanie specjalnie dla libc ++, ponieważ wiem, że korzysta z SSO, jest to nawet wspomniane na stronie domowej libc ++ .
Oto kilka obserwacji po spojrzeniu na źródło :
libc ++ można skompilować z dwoma nieco różnymi układami pamięci dla klasy string, zarządza to _LIBCPP_ALTERNATE_STRING_LAYOUT
flaga. Oba układy rozróżniają również maszyny little-endian i big-endian, co daje nam w sumie 4 różne warianty. Przyjmę "normalny" układ i little-endian w dalszej części.
Zakładając dalej, że size_type
są to 4 bajty, value_type
czyli 1 bajt, tak wyglądałyby pierwsze 4 bajty ciągu w pamięci:
// short string: (s)ize and 3 bytes of char (d)ata
sssssss0;dddddddd;dddddddd;dddddddd
^- is_long = 0
// long string: (c)apacity
ccccccc1;cccccccc;cccccccc;cccccccc
^- is_long = 1
Ponieważ rozmiar krótkiego ciągu znajduje się w górnych 7 bitach, należy go przesunąć podczas uzyskiwania do niego dostępu:
size_type __get_short_size() const {
return __r_.first().__s.__size_ >> 1;
}
Podobnie metoda pobierająca i ustawiająca dla pojemności długiego łańcucha używa __long_mask
do obejścia tego is_long
bitu.
Wciąż szukam odpowiedzi na swoje pierwsze pytanie, tj. Jaką wartość miałaby __min_cap
pojemność krótkich ciągów dla różnych architektur?
Inne implementacje bibliotek standardowych
Ta odpowiedź daje ładny przegląd std::string
układów pamięci w innych implementacjach bibliotek standardowych.
źródło
string
nagłówek tutaj , sprawdzam to w tej chwili :)Odpowiedzi:
Biblioteka libc ++
basic_string
została zaprojektowana tak, aby zawierałasizeof
3 słowa na wszystkich architekturach, gdziesizeof(word) == sizeof(void*)
. Prawidłowo rozdzieliłeś długą / krótką flagę i pole rozmiaru w skróconej formie.W krótkiej formie są 3 słowa do pracy:
char
, że 1 bajt trafia do końcowego null (libc ++ zawsze będzie przechowywać końcowe null za danymi).Pozostawia to 3 słowa minus 2 bajty na przechowywanie krótkiego łańcucha (tj. Największego
capacity()
bez alokacji).Na komputerze 32-bitowym w krótkim ciągu zmieści się 10 znaków. sizeof (string) to 12.
Na komputerze 64-bitowym w krótkim łańcuchu zmieszczą się 22 znaki. sizeof (string) to 24.
Głównym celem projektowym było zminimalizowanie
sizeof(string)
przy jednoczesnym maksymalnym zwiększeniu bufora wewnętrznego. Uzasadnieniem jest przyspieszenie konstrukcji i przypisanie ruchu. Im większysizeof
, tym więcej słów musisz przenieść podczas konstrukcji ruchu lub zadania przeniesienia.Długi formularz wymaga co najmniej 3 słów, aby zapisać wskaźnik danych, rozmiar i pojemność. Dlatego ograniczyłem krótką formę do tych samych 3 słów. Sugerowano, że rozmiar 4 słów może mieć lepszą wydajność. Nie testowałem tego wyboru projektu.
_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
Istnieje flaga konfiguracji o nazwie,
_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
która zmienia układ elementów danych w taki sposób, że „długi układ” zmienia się z:do:
Motywacją do tej zmiany jest przekonanie, że stawianie na
__data_
pierwszym miejscu przyniesie pewne korzyści w zakresie wydajności dzięki lepszemu wyrównaniu. Podjęto próbę zmierzenia zalet wydajności i było to trudne do zmierzenia. Nie pogorszy to wydajności, ale może ją nieco poprawić.Flagi należy używać ostrożnie. Jest to inny ABI i jeśli przypadkowo zostanie zmieszany z biblioteką libc ++
std::string
skompilowaną z innym ustawieniem,_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
spowoduje powstanie błędów w czasie wykonywania.Zalecam zmianę tej flagi tylko przez dostawcę libc ++.
źródło
string
jest cała 0 bitów. To sprawia, że domyślna konstrukcja jest super wydajna. A jeśli chcesz naginać zasady, czasem nawet za darmo. Np. Możeszcalloc
zapamiętać i po prostu zadeklarować, że jest pełna domyślnych skonstruowanych łańcuchów.int
s, aby klasa mogła być pakowana tylko do 16 bajtów na architekturach 64-bitowych?sizeof
. Ale jednocześnie wewnętrzny bufor dlachar
wynosi od 14 do 22, co jest całkiem niezłą korzyścią.Libc ++ realizacja jest nieco skomplikowane, będę ignorować jego alternatywną konstrukcję i załóżmy mały endian komputera:
Uwaga:
__compressed_pair
to w zasadzie para zoptymalizowana pod kątem optymalizacji pustej bazy , czylitemplate <T1, T2> struct __compressed_pair: T1, T2 {};
; pod każdym względem można uznać to za zwykłą parę. Jego znaczenie pojawia się właśnie dlatego, żestd::allocator
jest bezpaństwowcem, a zatem jest puste.Okay, to jest raczej surowe, więc sprawdźmy mechanikę! Wewnętrznie wiele funkcji wywoła,
__get_pointer()
które same wywołują,__is_long
aby określić, czy ciąg używa reprezentacji__long
lub__short
:Szczerze mówiąc, nie jestem zbyt pewien, czy jest to Standard C ++ (znam początkowy podciąg,
union
ale nie wiem, w jaki sposób łączy się z anonimową unią i aliasami złożonymi razem), ale biblioteka standardowa może korzystać z implementacji zdefiniowanej zachowanie w każdym razie.źródło
__min_cap
, co oceniłbym dla różnych architektur, nie jestem pewien, cosizeof()
powróci i jaki ma na to wpływ aliasing.3 * the size of one pointer
w tym przypadku 12 oktetów na łuku 32-bitowym i 24 na łuku 64-bitowym.