Signification de l'acronyme SSO dans le contexte de std :: string

Dans une question C ++ sur l'optimisation et le style de code , plusieurs réponses faisaient référence à "SSO" dans le contexte de l'optimisation des copies de std::string. Que signifie SSO dans ce contexte?

Clairement pas "single sign on". "Optimisation des chaînes partagées", peut-être?

Contexte / Aperçu

Les opérations sur les variables automatiques ("à partir de la pile", qui sont des variables que vous créez sans appeler malloc/ new) sont généralement beaucoup plus rapides que celles impliquant le magasin libre ("le tas", qui sont des variables créées à l'aide de new). Cependant, la taille des tableaux automatiques est fixée au moment de la compilation, mais la taille des tableaux du magasin gratuit ne l'est pas. De plus, la taille de la pile est limitée (généralement quelques Mio), alors que le stockage gratuit n'est limité que par la mémoire de votre système.

SSO est l'optimisation des chaînes courtes / petites. A std::stringstocke généralement la chaîne en tant que pointeur vers le magasin gratuit ("le tas"), qui donne des caractéristiques de performances similaires à celles que vous appeliez new char [size]. Cela évite un débordement de pile pour les très grandes chaînes, mais cela peut être plus lent, en particulier avec les opérations de copie. En tant qu'optimisation, de nombreuses implémentations std::stringcréent un petit tableau automatique, quelque chose comme char [20]. Si vous avez une chaîne de 20 caractères ou moins (dans cet exemple, la taille réelle varie), elle la stocke directement dans ce tableau. Cela évite du tout le besoin d'appeler new, ce qui accélère un peu les choses.

ÉDITER:

Je ne m'attendais pas à ce que cette réponse soit aussi populaire, mais puisque c'est le cas, permettez-moi de donner une implémentation plus réaliste, avec la mise en garde que je n'ai jamais lu une implémentation de SSO "dans la nature".

Détails d'implémentation

Au minimum, a std::stringdoit stocker les informations suivantes:

• La taille
• La capacité
• L'emplacement des données

La taille peut être stockée comme un std::string::size_typeou comme un pointeur vers la fin. La seule différence est de savoir si vous souhaitez avoir à soustraire deux pointeurs lorsque l'utilisateur appelle sizeou ajouter un size_typeà un pointeur lorsque l'utilisateur appelle end. La capacité peut également être stockée dans les deux sens.

Vous ne payez pas ce que vous n'utilisez pas.

Tout d'abord, considérez l'implémentation naïve basée sur ce que j'ai décrit ci-dessus:

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;
};

Pour un système 64 bits, cela signifie généralement qu'il std::stringa 24 octets de «surcharge» par chaîne, plus 16 autres pour le tampon SSO (16 choisis ici au lieu de 20 en raison des exigences de remplissage). Cela n'aurait pas vraiment de sens de stocker ces trois membres de données plus un tableau local de caractères, comme dans mon exemple simplifié. Si m_size <= 16, alors je vais mettre toutes les données m_sso, donc je connais déjà la capacité et je n'ai pas besoin du pointeur vers les données. Si m_size > 16, alors je n'ai pas besoin m_sso. Il n'y a absolument aucun chevauchement là où j'ai besoin de tous. Une solution plus intelligente qui ne gaspille aucun espace ressemblerait un peu plus à ceci (non testé, à titre d'exemple uniquement):

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;
    };
};

Je suppose que la plupart des implémentations ressemblent davantage à ceci.

SSO est l'abréviation de «Small String Optimization», une technique où de petites chaînes sont incorporées dans le corps de la classe de chaînes plutôt que d'utiliser un tampon alloué séparément.

Comme déjà expliqué par les autres réponses, SSO signifie Optimisation des petites / courtes chaînes . La motivation derrière cette optimisation est la preuve indéniable que les applications en général traitent des chaînes beaucoup plus courtes que des chaînes plus longues.

Comme expliqué par David Stone dans sa réponse ci - dessus , la std::stringclasse utilise un tampon interne pour stocker le contenu jusqu'à une longueur donnée, ce qui élimine le besoin d'allouer dynamiquement de la mémoire. Cela rend le code plus efficace et plus rapide .

Cette autre réponse connexe montre clairement que la taille du tampon interne dépend de l' std::stringimplémentation, qui varie d'une plateforme à l'autre (voir les résultats de référence ci-dessous).

Benchmarks

Voici un petit programme qui compare l'opération de copie de beaucoup de chaînes de même longueur. Il commence à imprimer le temps de copie de 10 millions de chaînes avec une longueur = 1. Puis il se répète avec des chaînes de longueur = 2. Il continue jusqu'à ce que la longueur soit de 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;
}

Si vous voulez exécuter ce programme, vous devez le faire comme ./a.out > /dev/nullpour que le temps d'impression des chaînes ne soit pas compté. Les nombres importants sont imprimés stderr, ils apparaîtront donc dans la console.

J'ai créé des graphiques avec la sortie de mes machines MacBook et Ubuntu. Notez qu'il y a un énorme saut dans le temps pour copier les chaînes lorsque la longueur atteint un point donné. C'est le moment où les chaînes ne rentrent plus dans le tampon interne et l'allocation de mémoire doit être utilisée.

Notez également que sur la machine Linux, le saut se produit lorsque la longueur de la chaîne atteint 16. Sur le macbook, le saut se produit lorsque la longueur atteint 23. Cela confirme que SSO dépend de l'implémentation de la plateforme.

Ubuntu

Macbook Pro