Jaka jest mechanika optymalizacji krótkich ciągów znaków w libc ++?

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 <= 16flaga, która jest częścią innej zmiennej składowej? (Wyobrażam sobie, że m_sizelub 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_LAYOUTflaga. 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_typesą to 4 bajty, value_typeczyli 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_maskdo obejścia tego is_longbitu.

Wciąż szukam odpowiedzi na swoje pierwsze pytanie, tj. Jaką wartość miałaby __min_cappojemność krótkich ciągów dla różnych architektur?

Inne implementacje bibliotek standardowych

Ta odpowiedź daje ładny przegląd std::stringukładów pamięci w innych implementacjach bibliotek standardowych.

Biblioteka libc ++ basic_stringzostała zaprojektowana tak, aby zawierała sizeof3 słowa na wszystkich architekturach, gdzie sizeof(word) == sizeof(void*). Prawidłowo rozdzieliłeś długą / krótką flagę i pole rozmiaru w skróconej formie.

jaką wartość miałoby __min_cap, pojemność krótkich ciągów, dla różnych architektur?

W krótkiej formie są 3 słowa do pracy:

• 1 bit trafia do flagi długiej / krótkiej.
• 7 bitów odpowiada rozmiarowi.
• Zakładając 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ększy sizeof, 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_LAYOUTktóra zmienia układ elementów danych w taki sposób, że „długi układ” zmienia się z:

struct __long
{
    size_type __cap_;
    size_type __size_;
    pointer   __data_;
};

do:

struct __long
{
    pointer   __data_;
    size_type __size_;
    size_type __cap_;
};

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::stringskompilowaną z innym ustawieniem, _LIBCPP_ABI_ALTERNATE_STRING_LAYOUTspowoduje powstanie błędów w czasie wykonywania.

Zalecam zmianę tej flagi tylko przez dostawcę libc ++.

Libc ++ realizacja jest nieco skomplikowane, będę ignorować jego alternatywną konstrukcję i załóżmy mały endian komputera:

template <...>
class basic_string {
/* many many things */

    struct __long
    {
        size_type __cap_;
        size_type __size_;
        pointer   __data_;
    };

    enum {__short_mask = 0x01};
    enum {__long_mask  = 0x1ul};

    enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
                      (sizeof(__long) - 1)/sizeof(value_type) : 2};

    struct __short
    {
        union
        {
            unsigned char __size_;
            value_type __lx;
        };
        value_type __data_[__min_cap];
    };

    union __ulx{__long __lx; __short __lxx;};

    enum {__n_words = sizeof(__ulx) / sizeof(size_type)};

    struct __raw
    {
        size_type __words[__n_words];
    };

    struct __rep
    {
        union
        {
            __long  __l;
            __short __s;
            __raw   __r;
        };
    };

    __compressed_pair<__rep, allocator_type> __r_;
}; // basic_string

Uwaga: __compressed_pairto w zasadzie para zoptymalizowana pod kątem optymalizacji pustej bazy , czyli template <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, że std::allocatorjest 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_longaby określić, czy ciąg używa reprezentacji __longlub __short:

bool __is_long() const _NOEXCEPT
    { return bool(__r_.first().__s.__size_ & __short_mask); }

// __r_.first() -> __rep const&
//     .__s     -> __short const&
//     .__size_ -> unsigned char

Szczerze mówiąc, nie jestem zbyt pewien, czy jest to Standard C ++ (znam początkowy podciąg, unionale 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.