Significado do acrônimo SSO no contexto de std :: string

Em uma questão de C ++ sobre otimização e estilo de código , várias respostas se referiam a “SSO” no contexto de otimização de cópias de std::string . O que significa SSO nesse contexto?

Claramente não “single sign on”. “Otimização de string compartilhada”, talvez?

Antecedentes / Visão Geral

Operações em variables ​​automáticas (“da pilha”, que são variables ​​que você cria sem chamar malloc / new ) são geralmente muito mais rápidas do que aquelas que envolvem o free store (“o heap”, que são variables ​​criadas usando new ). No entanto, o tamanho dos arrays automáticos é fixado em tempo de compilation, mas o tamanho dos arrays do armazenamento gratuito não é. Além disso, o tamanho da pilha é limitado (tipicamente alguns MiB), enquanto o armazenamento gratuito é limitado apenas pela memory do seu sistema.

O SSO é a Otimização de Cadeia Curta / Pequena. Um std::string normalmente armazena a string como um apontador para o free store (“o heap”), que fornece características de desempenho similares como se você fosse chamar new char [size] . Isso evita um estouro de pilha para cadeias muito grandes, mas pode ser mais lento, especialmente com operações de cópia. Como uma otimização, muitas implementações de std::string criam um pequeno array automático, algo como char [20] . Se você tiver uma cadeia de 20 caracteres ou menor (dado este exemplo, o tamanho real varia), ela é armazenada diretamente nessa matriz. Isso evita a necessidade de chamar de new , o que acelera um pouco as coisas.

EDITAR:

Eu não estava esperando que essa resposta fosse tão popular, mas desde que é, deixe-me dar uma implementação mais realista, com a ressalva de que eu nunca li nenhuma implementação de SSO “em estado selvagem”.

Detalhes de implementação

No mínimo, um std::string precisa armazenar as seguintes informações:

  • O tamanho
  • A capacidade
  • A localização dos dados

O tamanho pode ser armazenado como um std::string::size_type ou como um ponteiro para o final. A única diferença é se você deseja subtrair dois pointers quando o usuário chama size ou adiciona um size_type a um ponteiro quando o usuário chama end . A capacidade também pode ser armazenada de qualquer maneira.

Você não paga pelo que não usa.

Primeiro, considere a implementação ingênua com base no que descrevi acima:

 class string { public: // all 83 member functions private: std::unique_ptr m_data; size_type m_size; size_type m_capacity; std::array m_sso; }; 

Para um sistema de 64 bits, isso geralmente significa que std::string tem 24 bytes de ‘sobrecarga’ por string, além de outros 16 para o buffer de SSO (16 escolhidos aqui em vez de 20 devido a requisitos de preenchimento). Não faria sentido armazenar esses três membros de dados mais uma matriz local de caracteres, como no meu exemplo simplificado. Se m_size < = 16 , então eu colocarei todos os dados em m_sso , então eu já conheço a capacidade e não preciso do ponteiro para os dados. Se m_size > 16 , então eu não preciso de m_sso . Não há absolutamente nenhuma sobreposição onde eu preciso de todos eles. Uma solução mais inteligente que não desperdice espaço seria algo um pouco mais parecido com isso (não testado, apenas para fins de exemplo):

 class string { public: // all 83 member functions private: size_type m_size; union { class { // This is probably better designed as an array-like class std::unique_ptr m_data; size_type m_capacity; } m_large; std::array m_small; }; }; 

Eu diria que a maioria das implementações se parece mais com isso.

SSO é a abreviatura de “Small String Optimization”, uma técnica em que strings pequenas são incorporadas no corpo da class de strings em vez de usar um buffer alocado separadamente.

Como já explicado pelas outras respostas, o SSO significa otimização de seqüência pequena / curta . A motivação por trás dessa otimização é a evidência inegável de que os aplicativos em geral manipulam seqüências de caracteres muito mais curtas do que cadeias mais longas.

Como explicado por David Stone em sua resposta acima , a class std::string usa um buffer interno para armazenar o conteúdo até um determinado comprimento, e isso elimina a necessidade de alocar memory dinamicamente. Isso torna o código mais eficiente e mais rápido .

Essa outra resposta relacionada mostra claramente que o tamanho do buffer interno depende da implementação std::string , que varia de plataforma para plataforma (consulte os resultados do benchmark abaixo).

Referências

Aqui está um pequeno programa que faz o benchmark da operação de cópia de muitas strings com o mesmo tamanho. Ele começa a imprimir o tempo para copiar 10 milhões de strings com comprimento = 1. Então ele repete com strings de comprimento = 2. Ele continua indo até o comprimento de 50.

 #include  #include  #include  #include  static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; static const int ARRAY_SIZE = sizeof(CHARS) - 1; static const int BENCHMARK_SIZE = 10000000; static const int MAX_STRING_LENGTH = 50; using time_point = std::chrono::high_resolution_clock::time_point; void benchmark(std::vector& list) { std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now(); // force a copy of each string in the loop iteration for (const auto s : list) { std::cout < < s; } std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now(); const auto duration = std::chrono::duration_cast(t2 - t1).count(); std::cerr < < list[0].length() << ',' << duration << '\n'; } void addRandomString(std::vector& list, const int length) { std::string s(length, 0); for (int i = 0; i < length; ++i) { s[i] = CHARS[rand() % ARRAY_SIZE]; } list.push_back(s); } int main() { std::cerr << "length,time\n"; for (int length = 1; length <= MAX_STRING_LENGTH; length++) { std::vector list; for (int i = 0; i < BENCHMARK_SIZE; i++) { addRandomString(list, length); } benchmark(list); } return 0; } 

Se você deseja executar este programa, você deve fazê-lo como ./a.out > /dev/null para que o tempo para imprimir as strings não seja contado. Os números que importam são impressos no stderr , então eles aparecerão no console.

Eu criei charts com a saída das minhas máquinas MacBook e Ubuntu. Observe que há um salto enorme no tempo para copiar as strings quando o comprimento atinge um determinado ponto. Esse é o momento em que as seqüências de caracteres não se encheckboxm mais no buffer interno e a alocação de memory tem que ser usada.

Note também que na máquina linux, o salto acontece quando o comprimento da corda atinge 16. No macbook, o salto acontece quando o comprimento atinge 23. Isso confirma que o SSO depende da implementação da plataforma.

Ubuntu Referência de SSO no Ubuntu

MacBook Pro Referência de SSO no Macbook Pro