Quais são as mecânicas da otimização de strings curtas em libc ++?

Essa resposta fornece uma boa visão geral de alto nível da otimização de seqüência curta (SSO). No entanto, gostaria de saber com mais detalhes como funciona na prática, especificamente na implementação libc ++:

Eu fiz essa pergunta especificamente para libc ++ porque eu sei que ele usa SSO, isso é mencionado na home page da libc ++ .

Aqui estão algumas observações depois de olhar para a fonte :

O libc ++ pode ser compilado com dois layouts de memory ligeiramente diferentes para a class string, isto é governado pelo sinalizador _LIBCPP_ALTERNATE_STRING_LAYOUT . 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. Vou assumir o layout “normal” e little-endian no que se segue.

Supondo que size_type seja de 4 bytes e que value_type seja 1 byte, é como os primeiros 4 bytes de uma string se pareceriam na memory:

 // 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 deslocada ao acessá-la:

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

Da mesma forma, o getter e setter para a capacidade de uma cadeia longa usa __long_mask para contornar o bit is_long .

Eu ainda estou procurando uma resposta para a minha primeira pergunta, ou seja, qual seria o valor __min_cap , a capacidade de strings curtas, para diferentes arquiteturas?

Outras implementações de biblioteca padrão

Essa resposta fornece uma boa visão geral dos layouts de memory std::string em outras implementações de biblioteca padrão.

A libc ++ basic_string é projetada para ter um sizeof 3 palavras em todas as arquiteturas, onde sizeof(word) == sizeof(void*) . Você dissecou corretamente o sinalizador longo / curto eo campo de tamanho no formato curto.

qual valor __min_cap, a capacidade de strings curtas, leva para arquiteturas diferentes?

Na forma resumida, existem 3 palavras para trabalhar:

  • 1 bit vai para o sinalizador longo / curto.
  • 7 bits vai para o tamanho.
  • Assumindo char , 1 byte vai para o nulo final (libc ++ sempre armazenará um nulo final atrás dos dados).

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

Em uma máquina de 32 bits, 10 caracteres se encheckboxm na seqüência curta. sizeof (string) é 12.

Em uma máquina de 64 bits, 22 caracteres se encheckboxm na seqüência curta. sizeof (string) é 24.

Um dos principais objectives do projeto era minimizar o sizeof(string) , enquanto tornava o buffer interno o maior possível. O raciocínio é acelerar a construção do movimento e mover a atribuição. Quanto maior o tamanho, mais palavras você terá para mover durante uma construção de movimento ou uma atribuição de movimento.

A forma longa precisa de um mínimo de 3 palavras para armazenar o ponteiro de dados, tamanho e capacidade. Por isso, restringi a forma curta às mesmas 3 palavras. Tem sido sugerido que um tamanho de 4 palavras pode ter um 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_LAYOUT que reorganiza os membros de dados de forma que o “layout longo” seja alterado 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 terá algumas vantagens de desempenho devido ao melhor alinhamento. Foi feita uma tentativa de medir as vantagens de desempenho e era difícil de 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 misturada acidentalmente com um libc ++ std::string compilado com uma configuração diferente de _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT , criará erros de tempo de execução.

Eu recomendo que este sinalizador só seja alterado 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 o Empty Base Optimization , também conhecido como template struct __compressed_pair: T1, T2 {}; ; para todos os efeitos, você pode considerá-lo um par regular. Sua importância só aparece porque o std::allocator é sem estado e, portanto, vazio.

Ok, isso é bastante cru, então vamos verificar a mecânica! Internamente, muitas funções chamarão __get_pointer() que por sua vez chama __is_long para determinar se a string está usando a representação __short ou __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 estou muito certo de que este seja o C ++ Padrão (conheço a disposição de subsequência inicial no union mas não sei como ele combina com um sindicato anônimo e um aliasing juntos), mas uma Biblioteca Padrão pode tirar proveito da implementação comportamento definido de qualquer maneira.