Bedeutung des Akronyms SSO im Zusammenhang mit std::string

Lesezeit: 8 Minuten

Bedeutung des Akronyms SSO im Zusammenhang mit stdstring
Raedwald

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?

Eindeutig kein “Single-Sign-On”. Vielleicht “Shared-String-Optimierung”?

  • Das ist nur ein Duplikat, genauso wie “was 2+2 ist” ein Duplikat von “was ist das Ergebnis von 200/50”. Die Antwort ist dieselbe. Die Frage ist völlig anders. „Als Duplikat schließen“ soll verwendet werden, wenn mehrere Personen dieselbe* Frage stellen. Wenn eine Person fragt: „Wie ist es? std::string implementiert” und ein anderer fragt “was bedeutet SSO”, muss man absolut verrückt sein, um sie für dieselbe Frage zu halten

    – jalf

    25. April 2012 um 11:59 Uhr


  • @jalf: Wenn es ein vorhandenes Q + A gibt, das genau den Umfang dieser Frage umfasst, würde ich es als Duplikat betrachten (ich sage nicht, dass das OP selbst danach hätte suchen sollen, sondern nur, dass jede Antwort hier den Boden abdeckt, der das ist bereits abgedeckt.)

    – Oliver Charlesworth

    25. April 2012 um 12:01 Uhr


  • Sie sagen dem OP effektiv, dass „Ihre Frage falsch ist. Aber Sie mussten die Antwort wissen, um zu wissen, was Sie tun sollte gefragt haben”. Nette Art, Leute von SO abzuhalten. Es macht es auch unnötig schwer, die benötigten Informationen zu finden. Wenn die Leute keine Fragen stellen (und das Schließen effektiv sagt “diese Frage hätte nicht gestellt werden sollen”), dann Es gäbe keinen möglichen Weg für Menschen, die nicht bereits die Antwort kennen, um die Antwort zu bekommen Das Frage

    – jalf

    25. April 2012 um 12:06 Uhr


  • @jalf: Überhaupt nicht. IMO, “vote to close” impliziert keine “schlechte Frage”. Dafür verwende ich Downvotes. Ich betrachte es als Duplikat in dem Sinne, dass all die unzähligen Fragen (i = i ++ usw.), deren Antwort “undefiniertes Verhalten” ist, Duplikate voneinander sind. Auf einer anderen Anmerkung, warum hat niemand die Frage beantwortet, wenn es kein Duplikat ist?

    – Oliver Charlesworth

    25. April 2012 um 12:44 Uhr


  • @jalf: Ich stimme Oli zu, die Frage ist kein Duplikat, aber die Antwort wäre, daher die Umleitung auf eine andere Frage, wo die Antworten bereits lagen, angemessen erscheinen. Als Duplikate geschlossene Fragen verschwinden nicht, sondern dienen als Hinweis auf eine andere Frage, in der die Antwort liegt. Die nächste Person, die nach SSO sucht, landet hier, folgt der Weiterleitung und findet ihre Antwort.

    – Matthias M.

    25. April 2012 um 12:59 Uhr


Bedeutung des Akronyms SSO im Zusammenhang mit stdstring
David Stein

Hintergrund / Überblick

Operationen mit automatischen Variablen (“vom Stack”), bei denen es sich um Variablen handelt, die Sie erstellen, ohne sie aufzurufen malloc / new) sind im Allgemeinen viel schneller als diejenigen, die den kostenlosen Speicher (“the heap”) beinhalten, bei denen es sich um Variablen handelt, die mit erstellt werden new). Die Größe von automatischen Arrays ist jedoch zur Kompilierzeit festgelegt, die Größe von Arrays aus dem kostenlosen Store 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-Optimierung. EIN std::string speichert die Zeichenfolge normalerweise als Zeiger auf den freien Speicher (“den Heap”), was ähnliche Leistungsmerkmale bietet, als ob Sie anrufen würden new char [size]. Dies verhindert einen Stapelüberlauf bei sehr großen Strings, kann aber insbesondere bei Kopiervorgängen langsamer sein. Als Optimierung wurden viele Implementierungen von std::string Erstellen Sie ein kleines automatisches Array, so etwas wie char [20]. Wenn Sie eine Zeichenfolge haben, die 20 Zeichen oder weniger hat (in diesem Beispiel variiert die tatsächliche Größe), wird sie direkt in diesem Array gespeichert. Das erspart den Anruf new überhaupt, was die Sache 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 der Einschränkung, dass ich noch nie eine Implementierung von SSO “in freier Wildbahn” gelesen habe.

Implementierungsdetails

Mindestens a std::string muss die folgenden Informationen speichern:

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

Die Größe könnte als gespeichert werden std::string::size_type oder als Zeiger auf das Ende. Der einzige Unterschied besteht darin, ob Sie zwei Zeiger subtrahieren müssen, wenn der Benutzer aufruft size oder füge ein hinzu size_type zu einem Zeiger, wenn der Benutzer anruft end. Die Kapazität kann auch in beide Richtungen gespeichert werden.

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

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 das im Allgemeinen das std::string hat 24 Bytes ‘Overhead’ pro String, plus weitere 16 für den SSO-Puffer (hier 16 statt 20 aufgrund von Padding-Anforderungen gewählt). Es wäre nicht wirklich sinnvoll, diese drei Datenelemente plus ein lokales Array von Zeichen zu speichern, wie in meinem vereinfachten Beispiel. Wenn m_size <= 16dann gebe ich alle Daten ein m_sso, also kenne ich die Kapazität bereits und brauche den Zeiger auf die Daten nicht. Wenn m_size > 16dann 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 in etwa so aussehen (ungetestet, nur für Beispielzwecke):

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 davon ausgehen, dass die meisten Implementierungen eher so aussehen.

  • Hier ist eine gute Erklärung einiger tatsächlicher Implementierungen: stackoverflow.com/a/28003328/203044

    – BillT

    12. September 2015 um 14:15 Uhr

  • Ist SSO wirklich praktisch, wenn die meisten Entwickler std::string mit konstanten Referenzen übergeben?

    – Gupta

    24. Mai 2019 um 8:13 Uhr

  • SSO hat zwei Vorteile, abgesehen davon, dass das Kopieren billiger wird. Das erste ist, dass Sie, wenn Ihre Zeichenfolgengröße in die kleine Puffergröße passt, bei der anfänglichen Konstruktion keine Zuweisung vornehmen müssen. Die zweite ist, dass wenn eine Funktion a akzeptiert std::string const &, ist das Abrufen der Daten eine einzelne Speicherindirektion, da die Daten am Speicherort der Referenz gespeichert sind. Wenn es keine kleine String-Optimierung gäbe, würde der Zugriff auf die Daten zwei Speicherindirektionen erfordern (erstens, um die Referenz auf den String zu laden und seinen Inhalt zu lesen, dann den zweiten, um den Inhalt des Datenzeigers in dem String zu lesen).

    – David Stein

    2. Juni 2019 um 17:31 Uhr

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 Optimierung kleiner / kurzer Zeichenfolgen. Die Motivation hinter dieser Optimierung ist der unbestreitbare Beweis, dass Anwendungen im Allgemeinen viel mehr kürzere Zeichenfolgen als längere Zeichenfolgen verarbeiten.

Wie von David Stone in seiner obigen Antwort erklärt, die std::string -Klasse verwendet einen internen Puffer, um Inhalte bis zu einer bestimmten Länge zu speichern, und 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 abhängt std::string Implementierung, die von Plattform zu Plattform unterschiedlich ist (siehe Benchmark-Ergebnisse unten).

Benchmarks

Hier ist ein kleines Programm, das den Kopiervorgang vieler gleich langer Strings testet. Es beginnt mit dem Drucken der Zeit zum Kopieren von 10 Millionen Zeichenfolgen mit Länge = 1. Dann wiederholt es sich mit Zeichenfolgen der Länge = 2. 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 es tun ./a.out > /dev/null damit die Zeit zum Drucken der Zeichenfolgen nicht gezählt wird. Die Zahlen, auf die es ankommt, werden gedruckt stderrsodass sie in der Konsole angezeigt werden.

Ich habe Diagramme mit der Ausgabe meiner MacBook- und Ubuntu-Maschinen erstellt. Beachten Sie, dass es einen großen Sprung in der Zeit zum Kopieren der Zeichenfolgen gibt, wenn die Länge einen bestimmten Punkt erreicht. Das ist der Moment, in dem Strings nicht mehr in den internen Puffer passen und Speicherallokation 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
SSO-Benchmark auf Ubuntu

Macbook Pro
SSO-Benchmark auf dem Macbook Pro

  • Ich habe die Zeit von fast 4 Minuten auf fast 1 Minute verkürzt, indem ich weniger als notwendige Designoptionen entfernt habe. ideone.com/KJCh2H

    Benutzer10063119

    17. August 2020 um 16:23 Uhr


998570cookie-checkBedeutung des Akronyms SSO im Zusammenhang mit std::string

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy