Significado da sigla SSO no contexto de std :: string

155

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

Claramente, não "logon único". "Otimização de string compartilhada", talvez?

Raedwald
fonte
57
Isso é apenas uma duplicata da mesma maneira que "o que é 2 + 2" é uma duplicata do "qual é o resultado de 200/50". A resposta é a mesma. A questão é completamente diferente. "Fechar como duplicado" deve ser usado quando várias pessoas fazem a mesma pergunta *. Quando uma pessoa pede "como é std::stringimplementada", e uma outra pergunta: "o que faz SSO média", você tem que ser absolutamente insano considerar que eles sejam a mesma pergunta
jalf
1
@ jalf: Se houver um Q + A existente que abranja exatamente o escopo desta pergunta, eu a consideraria uma duplicata (não estou dizendo que o OP deveria ter procurado por ele mesmo, apenas que qualquer resposta aqui irá cobrir já foi coberto.)
Oliver Charlesworth
47
Você está efetivamente dizendo ao OP que "sua pergunta está errada. Mas você precisava saber a resposta para saber o que deveria ter perguntado". Ótima maneira de desligar as pessoas. Também torna desnecessariamente difícil encontrar as informações necessárias. Se as pessoas não fizerem perguntas (e o fechamento estiver efetivamente dizendo "essa pergunta não deveria ter sido feita"), não haveria maneira possível para as pessoas que ainda não sabem a resposta, obter a resposta para essa pergunta
jalf
7
@ jalf: Nem um pouco. OMI, "votar para fechar" não implica "má pergunta". Eu uso votos negativos para isso. Considero uma duplicata no sentido de que todas as inúmeras perguntas (i = i ++ etc.) cuja resposta é "comportamento indefinido" são duplicadas uma da outra. Em uma nota diferente, por que ninguém respondeu à pergunta se não é uma duplicata?
26712 Oliver Oliverworth
5
@ jalf: Eu concordo com Oli, a pergunta não é uma duplicata, mas a resposta seria, portanto, redirecionando para outra pergunta em que as respostas já estão parecem adequadas. As perguntas fechadas como duplicatas não desaparecem; elas agem como ponteiros para outra pergunta em que a resposta está. A próxima pessoa que estiver procurando por SSO terminará aqui, seguirá o redirecionamento e encontrará sua resposta.
Matthieu M.

Respostas:

213

Histórico / Visão Geral

Operações em variáveis ​​automáticas ("da pilha", que são criadas sem chamar malloc/ new) geralmente são muito mais rápidas do que aquelas que envolvem o armazenamento gratuito ("a pilha", que são criadas usando new). No entanto, o tamanho das matrizes automáticas é fixo no momento da compilação, mas o tamanho das matrizes do armazenamento gratuito não é. Além disso, o tamanho da pilha é limitado (normalmente alguns MiB), enquanto o armazenamento gratuito é limitado apenas pela memória do seu sistema.

SSO é a otimização de cadeia curta / pequena. A std::stringnormalmente armazena a string como um ponteiro para a loja gratuita ("a pilha"), o que fornece características de desempenho semelhantes às de uma chamada 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 otimização, muitas implementações std::stringcriam uma pequena matriz automática, algo assim char [20]. Se você tiver uma string com 20 caracteres ou menos (dado este exemplo, o tamanho real varia), ela será armazenada diretamente nessa matriz. Isso evita a necessidade de ligar new, o que acelera um pouco as coisas.

EDITAR:

Eu não esperava que essa resposta fosse tão popular, mas, como é, permita-me dar uma implementação mais realista, com a ressalva de que nunca realmente li nenhuma implementação do SSO "in the wild".

Detalhes da implementação

No mínimo, é std::stringnecessário armazenar as seguintes informações:

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

O tamanho pode ser armazenado como um std::string::size_typeou como um ponteiro para o final. A única diferença é se você deseja subtrair dois ponteiros quando o usuário chama sizeou adicionar um size_typea 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<char[]> m_data;
    size_type m_size;
    size_type m_capacity;
    std::array<char, 16> m_sso;
};

Para um sistema de 64 bits, isso geralmente significa que std::stringpossui 24 bytes de 'sobrecarga' por sequência, além de outros 16 para o buffer SSO (16 escolhidos aqui em vez de 20 devido a requisitos de preenchimento). Realmente 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, colocarei todos os dados m_sso, para que eu já conheça a capacidade e não precise do ponteiro para os dados. Se m_size > 16, então eu não preciso 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 mais ou menos assim (apenas para fins de exemplo não testados):

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<char[]> m_data;
            size_type m_capacity;
        } m_large;
        std::array<char, sizeof(m_large)> m_small;
    };
};

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

David Stone
fonte
7
Aqui está uma boa explicação de algumas implementações reais: stackoverflow.com/a/28003328/203044
BillT
O SSO é realmente prático quando a maioria dos desenvolvedores passa std :: string usando referências const?
Gupta
1
O SSO tem dois benefícios além de tornar a cópia mais barata. A primeira é que, se o tamanho da cadeia de caracteres se ajustar ao tamanho pequeno do buffer, você não precisará alocar na construção inicial. A segunda é que, quando uma função aceita a std::string const &, chegar aos dados é um único indireção de memória, porque os dados são armazenados no local da referência. Se não houvesse otimização de sequência pequena, o acesso aos dados exigiria duas indiretas de memória (primeiro para carregar a referência à sequência e ler seu conteúdo, depois a segunda para ler o conteúdo do ponteiro de dados na sequência).
David Stone
34

SSO é a abreviação de "Small String Optimization", uma técnica em que pequenas strings são incorporadas no corpo da classe string em vez de usar um buffer alocado separadamente.

Mark Ransom
fonte
15

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

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

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

Benchmarks

Aqui está um pequeno programa que avalia a operação de cópia de várias seqüências de caracteres com o mesmo comprimento. Começa a imprimir o tempo para copiar 10 milhões de strings com comprimento = 1. Em seguida, repete-se com strings de comprimento = 2. Continua até o comprimento ser 50.

#include <string>
#include <iostream>
#include <vector>
#include <chrono>

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<std::string>& 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<std::chrono::milliseconds>(t2 - t1).count();
    std::cerr << list[0].length() << ',' << duration << '\n';
}

void addRandomString(std::vector<std::string>& 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<std::string> list;
        for (int i = 0; i < BENCHMARK_SIZE; i++) {
            addRandomString(list, length);
        }
        benchmark(list);
    }

    return 0;
}

Se você deseja executar este programa, deve fazê-lo da ./a.out > /dev/nullmaneira que o tempo para imprimir as seqüências não seja contado. Os números importantes são impressos para stderrque eles apareçam no console.

Criei gráficos com a saída dos meus computadores MacBook e Ubuntu. Observe que há um grande salto no tempo para copiar as strings quando o comprimento atinge um determinado ponto. Esse é o momento em que as strings não cabem mais no buffer interno e a alocação de memória deve ser usada.

Observe também que na máquina linux, o salto ocorre quando o comprimento da cadeia atinge 16. No macbook, o salto ocorre 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

HugoTeixeira
fonte