Jaka jest mechanika optymalizacji krótkich łańcuchów w libc++?

Ta odpowiedź daje ładny przegląd wysokiego poziomu krótki ciąg optymalizacji (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, aby zakwalifikować się do SSO? Czy to zależy od docelowej architektury?

  • W Jaki Sposób wdrożenie rozróżnia krótkie i długie ciągi znaków podczas uzyskiwania dostępu do danych ciągów znaków? Czy to takie proste jako m_size <= 16 czy jest to flaga, która jest częścią innej zmiennej członkowskiej? (I wyobraź sobie, że m_size lub jej część może być również użyta do przechowywania string data).

Zadałem to pytanie specjalnie dla libc++ , ponieważ Wiem, że używa SSO, jest to nawet wspomniane na stronie głównej libc++ .

Oto kilka uwag po przyjrzeniu się źródłu :

Libc++ można skompilować z dwoma nieco różnymi układami pamięci dla klasy string, to jest zarządzana przez flagę _LIBCPP_ALTERNATE_STRING_LAYOUT. Oba układy rozróżniają również maszyny little-endian i big-endian, co daje nam w sumie 4 różne warianty. Zakładam "normalny" układ i little-endian w tym, co następuje.

Zakładając dalej, że size_type jest 4 bajtami, a {[6] } jest 1 bajtem, tak wyglądałyby pierwsze 4 bajty ciągu znaków 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 jest w górnych 7 bitach, musi być przesunięty, gdy dostęp do niego: 

size_type __get_short_size() const {
    return __r_.first().__s.__size_ >> 1;
}

Podobnie, getter i setter dla pojemności długiego ciągu używa __long_mask do pracy wokół bitu is_long.

Wciąż szukam odpowiedzi na moje pierwsze pytanie, tzn. jaką wartość __min_cap, pojemność krótkich łańcuchów, miałaby dla różnych architektur?

Inne implementacje bibliotek standardowych

Ta odpowiedź daje ładny przegląd std::string układów pamięci w innych standardowych bibliotekach wdrożenia.

Author: Community, 2014-02-11
Source

2 answers

Libc++ basic_string jest zaprojektowany tak, aby mieć sizeof 3 słowa na wszystkich architekturach, gdzie sizeof(word) == sizeof(void*). Poprawnie rozciąłeś flagę długą / krótką i pole rozmiaru w krótkim formularzu.

Jaką wartość_ _ min _ cap, pojemność krótkich łańcuchów, przyjmie dla różnych architektur?

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

  • 1 bit idzie do flagi long / short.
  • 7 bitów idzie do rozmiaru.
  • zakładając char, 1 bajt przechodzi do końcowego null (libc++ zawsze będzie przechowywać końcowe null za danymi).

To pozostawia 3 słowa minus 2 bajty do przechowywania krótkiego ciągu (tj. największy capacity() bez przydziału).

Na maszynie 32-bitowej 10 znaków zmieści się w krótkim łańcuchu. sizeof (string) wynosi 12.

Na maszynie 64-bitowej 22 znaki będą pasowały do krótkiego ciągu. sizeof (string) wynosi 24.

Głównym celem projektu było zminimalizowanie sizeof(string), jednocześnie czyniąc wewnętrzny bufor tak dużym jak to możliwe. Uzasadnieniem jest przyspieszenie budowy i przenoszenie zadań. Im większy sizeof, tym więcej słów musisz przenieść podczas budowy ruchu lub przypisania ruchu.

Długi formularz wymaga minimum 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 wyrazów może mieć lepszą wydajność. Nie testowałem tego projektu wybór.

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

Istnieje flaga konfiguracji o nazwie _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT, która przestawia elementy danych tak, ż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 umieszczenie __data_ na pierwszym miejscu będzie miało pewne zalety wydajności dzięki lepszemu dopasowaniu. Podjęto próbę zmierzenia zalet wydajności i było to trudne do zmierzenia. To nie sprawi, że wydajność gorsza, a to może sprawić, że będzie nieco lepiej.

Flaga powinna być używana ostrożnie. Jest to inny ABI, a jeśli przypadkowo zmieszany z libc++ std::string skompilowanym z innym ustawieniem _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT spowoduje błędy w czasie wykonywania.

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

 96
Author: Howard Hinnant,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-11-15 17:24:39

Implementacja libc++ jest nieco skomplikowana, zignoruję jej alternatywny projekt i załóżmy, że mały komputer endian: 

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_pair jest zasadniczo parą zoptymalizowaną dla optymalizacji pustej bazy , aka template <T1, T2> struct __compressed_pair: T1, T2 {};; dla wszystkich zamiarów i celów można uznać ją za zwykłą parę. Jej znaczenie pojawia się tylko dlatego, że std::allocator jest bezpaństwowa, a więc pusta.

OK, to jest raczej surowe, więc sprawdźmy mechanikę! Wewnętrznie, wiele funkcji będzie wywołanie __get_pointer(), które samo wywołuje __is_long, aby określić, czy łańcuch używa reprezentacji __long lub __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 zapis w union, Ale Nie wiem, jak łączy się z anonimowym związkiem i aliasingiem), ale Biblioteka standardowa i tak może korzystać z implementacji zdefiniowanego zachowania.

 17
Author: Matthieu M.,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-02-11 08:30:58