Bedeutung des Akronyms SSO im Kontext von std :: string

In einer C ++ - Frage zu Optimierung und Codestil bezogen sich mehrere Antworten auf "SSO" im Zusammenhang mit der Optimierung von Kopien von std::string. Was bedeutet SSO in diesem Zusammenhang?

Ganz klar nicht "Single Sign On". "Shared String Optimization" vielleicht?

Hintergrund / Übersicht

Operationen mit automatischen Variablen ("vom Stapel", bei denen es sich um Variablen handelt, die Sie ohne Aufruf von malloc/ erstellen new) sind im Allgemeinen viel schneller als Operationen mit dem freien Speicher ("der Heap", bei dem es sich um Variablen handelt, die mit erstellt werden new). Die Größe der automatischen Arrays ist jedoch zur Kompilierungszeit festgelegt, die Größe der Arrays aus dem freien Speicher jedoch nicht. Darüber hinaus ist die Stapelgröße begrenzt (normalerweise einige MiB), während der freie Speicher nur durch den Arbeitsspeicher Ihres Systems begrenzt ist.

SSO ist die Short / Small String Optimization. A std::stringspeichert die Zeichenfolge normalerweise als Zeiger auf den freien Speicher ("den Heap"), der ähnliche Leistungsmerkmale bietet, als ob Sie aufrufen würden new char [size]. Dies verhindert einen Stapelüberlauf für sehr große Zeichenfolgen, kann jedoch langsamer sein, insbesondere bei Kopiervorgängen. Als Optimierung std::stringerstellen viele Implementierungen ein kleines automatisches Array, so etwas wie char [20]. Wenn Sie eine Zeichenfolge mit 20 Zeichen oder weniger haben (in diesem Beispiel variiert die tatsächliche Größe), wird sie direkt in diesem Array gespeichert. Dies vermeidet die Notwendigkeit, überhaupt anzurufen new, was die Dinge etwas beschleunigt.

BEARBEITEN:

Ich hatte nicht erwartet, dass diese Antwort so beliebt sein würde, aber da dies der Fall ist, möchte ich eine realistischere Implementierung geben, mit dem Vorbehalt, dass ich noch nie eine Implementierung von SSO "in the wild" gelesen habe.

Implementierungsdetails

A muss mindestens std::stringdie folgenden Informationen speichern:

• Die Größe
• Die Kapazität
• Der Speicherort der Daten

Die Größe kann als std::string::size_typeoder als Zeiger auf das Ende gespeichert werden . Der einzige Unterschied besteht darin, ob Sie zwei Zeiger subtrahieren müssen, wenn der Benutzer aufruft, sizeoder size_typeeinem Zeiger einen hinzufügen möchten, wenn der Benutzer aufruft end. Die Kapazität kann auch so oder so gespeichert werden.

Sie zahlen nicht für das, was Sie nicht verwenden.

Betrachten Sie zunächst die naive Implementierung basierend auf dem, was ich oben skizziert habe:

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

Für ein 64-Bit-System bedeutet dies im Allgemeinen, dass std::string24 Bytes 'Overhead' pro Zeichenfolge plus weitere 16 für den SSO-Puffer vorhanden sind (16 werden hier aufgrund von Auffüllanforderungen anstelle von 20 ausgewählt). Es wäre nicht wirklich sinnvoll, diese drei Datenelemente plus eine lokale Zeichenfolge zu speichern, wie in meinem vereinfachten Beispiel. Wenn m_size <= 16, dann werde ich alle Daten eingeben m_sso, damit ich die Kapazität bereits kenne und den Zeiger auf die Daten nicht benötige. Wenn m_size > 16ja, dann brauche ich nicht m_sso. Es gibt absolut keine Überlappung, wo ich sie alle brauche. Eine intelligentere Lösung, die keinen Platz verschwendet, würde etwas ähnlicher aussehen (ungetestet, nur zu Beispielzwecken):

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

Ich würde annehmen, dass die meisten Implementierungen eher so aussehen.

SSO ist die Abkürzung für "Small String Optimization", eine Technik, bei der kleine Zeichenfolgen in den Hauptteil der Zeichenfolgenklasse eingebettet werden, anstatt einen separat zugewiesenen Puffer zu verwenden.

Wie bereits in den anderen Antworten erläutert, bedeutet SSO Small / Short String Optimization . Die Motivation für diese Optimierung ist der unbestreitbare Beweis, dass Anwendungen im Allgemeinen viel kürzere Zeichenfolgen als längere Zeichenfolgen verarbeiten.

Wie von David Stone in seiner obigen Antwort erläutert , verwendet die std::stringKlasse einen internen Puffer, um Inhalte bis zu einer bestimmten Länge zu speichern. Dadurch entfällt die Notwendigkeit, Speicher dynamisch zuzuweisen. Dies macht den Code effizienter und schneller .

Diese andere verwandte Antwort zeigt deutlich, dass die Größe des internen Puffers von der std::stringImplementierung abhängt , die von Plattform zu Plattform variiert (siehe Benchmark-Ergebnisse unten).

Benchmarks

Hier ist ein kleines Programm, das den Kopiervorgang vieler Zeichenfolgen mit derselben Länge bewertet. Es beginnt mit dem Drucken der Zeit zum Kopieren von 10 Millionen Zeichenfolgen mit der Länge = 1. Dann wird es mit Zeichenfolgen mit der Länge = 2 wiederholt. Es wird fortgesetzt, bis die Länge 50 beträgt.

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

Wenn Sie dieses Programm ausführen möchten, sollten Sie dies ./a.out > /dev/nullso tun , dass die Zeit zum Drucken der Zeichenfolgen nicht gezählt wird. Die wichtigen Zahlen werden gedruckt stderr, sodass sie in der Konsole angezeigt werden.

Ich habe Diagramme mit der Ausgabe meiner MacBook- und Ubuntu-Computer erstellt. Beachten Sie, dass die Zeit zum Kopieren der Zeichenfolgen sehr groß ist, wenn die Länge einen bestimmten Punkt erreicht. Dies ist der Moment, in dem Zeichenfolgen nicht mehr in den internen Puffer passen und die Speicherzuordnung verwendet werden muss.

Beachten Sie auch, dass auf dem Linux-Computer der Sprung erfolgt, wenn die Länge der Zeichenfolge 16 erreicht. Auf dem MacBook erfolgt der Sprung, wenn die Länge 23 erreicht. Dies bestätigt, dass SSO von der Plattformimplementierung abhängt.

Ubuntu

Macbook Pro