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

102

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.

ValarDohaeris
źródło
libc ++ jest open-source, możesz znaleźć jego stringnagłówek tutaj , sprawdzam to w tej chwili :)
Matthieu M.
@Matthieu M .: Widziałem to już wcześniej, niestety to bardzo duży plik, dzięki za pomoc przy sprawdzaniu.
ValarDohaeris,
@Ali: Natknąłem się o to w Google. Jednak ten post na blogu wyraźnie mówi, że jest to tylko ilustracja logowania jednokrotnego, a nie wysoce zoptymalizowany wariant, który byłby używany w praktyce.
ValarDohaeris,

Odpowiedzi:

120

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 ++.

Howard Hinnant
źródło
17
Nie jestem pewien, czy istnieje zgodność licencji między libc ++ i Facebook Folly, ale FBstring udaje się przechowywać dodatkowy znak (tj. 23), zmieniając rozmiar na pozostałą pojemność , dzięki czemu może wykonywać podwójną funkcję jako terminator zerowy dla krótkiego ciągu 23 znaków .
TemplateRex,
20
@TemplateRex: To sprytne. Jednak jeśli libc ++ przyjmie, będzie wymagało, aby libc ++ zrezygnowało z jednej innej cechy, którą lubię w swoim std :: string: Domyślnie skonstruowana stringjest 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żesz calloczapamiętać i po prostu zadeklarować, że jest pełna domyślnych skonstruowanych łańcuchów.
Howard Hinnant,
6
Ach, 0-init jest naprawdę fajne! BTW, FBstring ma 2 bity flagi, wskazujące na krótkie, pośrednie i duże łańcuchy. Używa SSO dla łańcuchów do 23 znaków, a następnie używa malloc-ed obszaru pamięci dla łańcuchów do 254 znaków, a poza tym robią COW (już nie legalne w C ++ 11, wiem).
TemplateRex,
Dlaczego nie można przechowywać rozmiaru i pojemności w ints, aby klasa mogła być pakowana tylko do 16 bajtów na architekturach 64-bitowych?
phuclv
@ LưuVĩnhPhúc: Chciałem zezwolić na ciągi większe niż 2 Gb na 64-bitowej. Koszt jest co prawda większy sizeof. Ale jednocześnie wewnętrzny bufor dla charwynosi od 14 do 22, co jest całkiem niezłą korzyścią.
Howard Hinnant
21

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.

Matthieu M.
źródło
Dziękuję za szczegółową odpowiedź! Brakuje mi tylko tego __min_cap, co oceniłbym dla różnych architektur, nie jestem pewien, co sizeof()powróci i jaki ma na to wpływ aliasing.
ValarDohaeris,
1
@ValarDohaeris to zdefiniowana implementacja. zazwyczaj można by się spodziewać 3 * the size of one pointerw tym przypadku 12 oktetów na łuku 32-bitowym i 24 na łuku 64-bitowym.
justin,