Qual é a mecânica de otimização de string curta em libc ++?

Esta resposta oferece uma boa visão geral de alto nível da otimização de string curta (SSO). Porém, gostaria de saber mais detalhadamente como funciona na prática, especificamente na implementação libc ++:

• Quão curta a string deve ser para se qualificar para o SSO? Isso depende da arquitetura de destino?

• Como a implementação distingue entre strings curtas e longas ao acessar os dados da string? É tão simples quanto m_size <= 16ou é um sinalizador que faz parte de alguma outra variável de membro? (Eu imagino que m_sizeou parte dele também possa ser usado para armazenar dados de string).

Eu fiz essa pergunta especificamente para libc ++ porque eu sei que ela usa SSO, isso é até mencionado na página inicial da libc ++ .

Aqui estão algumas observações após olhar para a fonte :

libc ++ pode ser compilado com dois layouts de memória ligeiramente diferentes para a classe string, isso é governado pelo _LIBCPP_ALTERNATE_STRING_LAYOUTsinalizador. Ambos os layouts também distinguem entre máquinas little-endian e big-endian, o que nos deixa com um total de 4 variantes diferentes. Assumirei o layout "normal" e o little-endian no que segue.

Supondo ainda que size_typesejam 4 bytes e value_type1 byte, é assim que os primeiros 4 bytes de uma string seriam na memória:

// 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

Como o tamanho da string curta está nos 7 bits superiores, ela precisa ser alterada ao acessá-la:

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

Da mesma forma, o getter e o setter para a capacidade de uma longa string usam __long_maskpara contornar o is_longbit.

Ainda estou procurando uma resposta para minha primeira pergunta, ou seja, qual valor __min_cap, a capacidade de strings curtas, teria para diferentes arquiteturas?

Outras implementações de biblioteca padrão

Esta resposta fornece uma boa visão geral dos std::stringlayouts de memória em outras implementações de biblioteca padrão.

O libc ++ basic_stringé projetado para ter sizeof3 palavras em todas as arquiteturas, onde sizeof(word) == sizeof(void*). Você dissecou corretamente a bandeira longa / curta e o campo de tamanho na forma curta.

que valor __min_cap, a capacidade de strings curtas, teria para diferentes arquiteturas?

Na forma curta, existem 3 palavras para trabalhar:

• 1 bit vai para a bandeira longa / curta.
• 7 bits vão para o tamanho.
• Supondo que char1 byte vai para o nulo final (a libc ++ sempre armazenará um nulo final atrás dos dados).

Isso deixa 3 palavras menos 2 bytes para armazenar uma string curta (ou seja, a maior capacity()sem uma alocação).

Em uma máquina de 32 bits, 10 caracteres caberão na string curta. sizeof (string) é 12.

Em uma máquina de 64 bits, 22 caracteres caberão na string curta. sizeof (string) é 24.

Um dos principais objetivos do projeto era minimizar sizeof(string), ao mesmo tempo que tornava o buffer interno o maior possível. A lógica é acelerar a construção e a atribuição de movimentos. Quanto maior osizeof , mais palavras você terá que mover durante uma construção de movimento ou atribuição de movimento.

O formato longo precisa de no mínimo 3 palavras para armazenar o indicador de dados, tamanho e capacidade. Portanto, restringi a forma abreviada às mesmas 3 palavras. Foi sugerido que um tamanho de 4 palavras pode ter melhor desempenho. Eu não testei essa escolha de design.

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

Há um sinalizador de configuração chamado _LIBCPP_ABI_ALTERNATE_STRING_LAYOUTque reorganiza os membros de dados de forma que o "layout longo" mude de:

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

para:

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

A motivação para essa mudança é a crença de que colocar __data_ primeiro lugar terá algumas vantagens de desempenho devido ao melhor alinhamento. Foi feita uma tentativa de medir as vantagens de desempenho e era difícil medir. Não vai piorar o desempenho e pode torná-lo um pouco melhor.

A bandeira deve ser usada com cuidado. É uma ABI diferente e, se acidentalmente misturada com uma libc ++ std::stringcompilada com uma configuração diferente de _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT, criará erros de tempo de execução.

Eu recomendo que este sinalizador seja alterado apenas por um fornecedor de libc ++.

A implementação da libc ++ é um pouco complicada, vou ignorar seu design alternativo e supor um pequeno computador 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

Nota: __compressed_pairé essencialmente um par otimizado para a Otimização de Base Vazia , também conhecida como template <T1, T2> struct __compressed_pair: T1, T2 {};; para todos os efeitos, você pode considerá-lo um par normal. Sua importância só surge porque não std::allocatortem estado e, portanto, está vazio.

Ok, isso é bastante cru, então vamos verificar a mecânica! Internamente, muitas funções chamarão as __get_pointer()próprias chamadas __is_longpara determinar se a string está usando a representação __longou __short:

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

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

Para ser honesto, não tenho certeza se isso é C ++ padrão (eu conheço a provisão de subsequência inicial, unionmas não sei como ela se mescla com uma união anônima e aliasing lançados juntos), mas uma biblioteca padrão pode tirar vantagem da implementação definida comportamento de qualquer maneira.