Was sind die Mechanismen der Short-String-Optimierung in libc++?

Diese Antwort gibt einen schönen allgemeinen Überblick über die Short-String-Optimierung (SSO). Ich würde jedoch gerne genauer wissen, wie es in der Praxis funktioniert, insbesondere in der libc++-Implementierung:

• Wie kurz muss die Zeichenfolge sein, um sich für SSO zu qualifizieren? Hängt dies von der Zielarchitektur ab?

• Wie unterscheidet die Implementierung beim Zugriff auf die String-Daten zwischen kurzen und langen Strings? Ist es so einfach wie m_size <= 16 oder ist es ein Flag, das Teil einer anderen Member-Variablen ist? (Ich kann es mir vorstellen m_size oder ein Teil davon könnte auch zum Speichern von Zeichenkettendaten verwendet werden).

Ich habe diese Frage speziell für libc++ gestellt, weil ich weiß, dass es SSO verwendet, dies wird sogar auf der erwähnt libc++-Homepage.

Hier sind einige Beobachtungen nach dem Betrachten die Quelle:

libc++ kann mit zwei leicht unterschiedlichen Speicherlayouts für die String-Klasse kompiliert werden, dies wird durch die geregelt _LIBCPP_ALTERNATE_STRING_LAYOUT Flagge. Beide Layouts unterscheiden auch zwischen Little-Endian- und Big-Endian-Maschinen, sodass wir insgesamt 4 verschiedene Varianten haben. Ich gehe im Folgenden vom “normalen” Layout und Little-Endian aus.

Weiter davon ausgegangen size_type ist 4 Bytes und das value_type 1 Byte ist, würden die ersten 4 Bytes einer Zeichenfolge im Speicher so aussehen:

// short string: (s)ize and 3 bytes of char (d)ata
sssssss0;dddddddd;dddddddd;dddddddd
       ^- is_long = 0

// long string: (c)apacity
ccccccc1;cccccccc;cccccccc;cccccccc
       ^- is_long = 1

Da die Größe des kurzen Strings in den oberen 7 Bit liegt, muss er beim Zugriff verschoben werden:

size_type __get_short_size() const {
    return __r_.first().__s.__size_ >> 1;
}

Ebenso werden Getter und Setter für die Kapazität eines langen Strings genutzt __long_mask um die zu arbeiten is_long bisschen.

Ich suche noch eine Antwort auf meine erste Frage, also welchen Wert würde das haben __min_capdie Kapazität von kurzen Strings, für unterschiedliche Architekturen?

Andere Implementierungen von Standardbibliotheken

Diese Antwort gibt einen schönen Überblick über std::string Speicherlayouts in anderen Implementierungen von Standardbibliotheken.

Die libc++ basic_string ist so konzipiert, dass ein sizeof 3 Wörter zu allen Architekturen, wo sizeof(word) == sizeof(void*). Sie haben das Lang/Kurz-Flag und das Größenfeld in der Kurzform korrekt seziert.

Welchen Wert würde __min_cap, die Kapazität kurzer Strings, für verschiedene Architekturen annehmen?

In der Kurzform gibt es 3 Wörter, mit denen man arbeiten kann:

• 1 Bit geht an das Lang/Kurz-Flag.
• 7 Bit gehen an die Größe.
• Vorausgesetzt char1 Byte geht an die abschließende Null (libc++ speichert immer eine abschließende Null hinter den Daten).

Dies lässt 3 Wörter minus 2 Bytes übrig, um eine kurze Zeichenfolge (d. h. die größte capacity() ohne Zuordnung).

Auf einem 32-Bit-Computer passen 10 Zeichen in die kurze Zeichenfolge. sizeof(string) ist 12.

Auf einem 64-Bit-Computer passen 22 Zeichen in die kurze Zeichenfolge. sizeof(string) ist 24.

Ein Hauptdesignziel war die Minimierung sizeof(string), während der interne Puffer so groß wie möglich gemacht wird. Das Grundprinzip besteht darin, die Zugkonstruktion und Zugzuweisung zu beschleunigen. Je größer die sizeofdesto mehr Wörter müssen Sie während einer Zugkonstruktion oder Zugaufgabe bewegen.

Die Langform benötigt mindestens 3 Wörter, um den Datenzeiger, die Größe und die Kapazität zu speichern. Daher habe ich die Kurzform auf dieselben 3 Wörter beschränkt. Es wurde angedeutet, dass eine Größe von 4 Wörtern eine bessere Leistung haben könnte. Ich habe diese Designwahl nicht getestet.

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

Es gibt ein Konfigurationsflag namens _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT wodurch die Datenelemente so neu angeordnet werden, dass sich das “lange Layout” ändert von:

struct __long
{
    size_type __cap_;
    size_type __size_;
    pointer   __data_;
};

zu:

struct __long
{
    pointer   __data_;
    size_type __size_;
    size_type __cap_;
};

Die Motivation für diese Änderung ist der Glaube, dass das Putten __data_ first wird aufgrund der besseren Ausrichtung einige Leistungsvorteile haben. Es wurde versucht, die Leistungsvorteile zu messen, und es war schwierig, sie zu messen. Die Leistung wird dadurch nicht schlechter, aber möglicherweise etwas besser.

Die Flagge sollte mit Vorsicht verwendet werden. Es ist eine andere ABI und wird versehentlich mit einer libc++ gemischt std::string kompiliert mit einer anderen Einstellung von _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT erzeugt Laufzeitfehler.

Ich empfehle, dieses Flag nur von einem Anbieter von libc++ zu ändern.

Die libc++-Implementierung ist ein bisschen kompliziert, ich ignoriere sein alternatives Design und nehme einen kleinen Endian-Computer an:

template <...>
class basic_string {
/* many many things */

    struct __long
    {
        size_type __cap_;
        size_type __size_;
        pointer   __data_;
    };

    enum {__short_mask = 0x01};
    enum {__long_mask  = 0x1ul};

    enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
                      (sizeof(__long) - 1)/sizeof(value_type) : 2};

    struct __short
    {
        union
        {
            unsigned char __size_;
            value_type __lx;
        };
        value_type __data_[__min_cap];
    };

    union __ulx{__long __lx; __short __lxx;};

    enum {__n_words = sizeof(__ulx) / sizeof(size_type)};

    struct __raw
    {
        size_type __words[__n_words];
    };

    struct __rep
    {
        union
        {
            __long  __l;
            __short __s;
            __raw   __r;
        };
    };

    __compressed_pair<__rep, allocator_type> __r_;
}; // basic_string

Notiz: __compressed_pair ist im Wesentlichen ein Paar, das für die optimiert ist Optimierung der leeren Basisauch bekannt template <T1, T2> struct __compressed_pair: T1, T2 {};; Sie können es in jeder Hinsicht als normales Paar betrachten. Seine Bedeutung ergibt sich nur, weil std::allocator ist zustandslos und somit leer.

Okay, das ist ziemlich roh, also lasst uns die Mechanik überprüfen! Intern werden viele Funktionen aufgerufen __get_pointer() der selbst ruft __is_long um festzustellen, ob die Zeichenfolge die verwendet __long oder __short Darstellung:

bool __is_long() const _NOEXCEPT
    { return bool(__r_.first().__s.__size_ & __short_mask); }

// __r_.first() -> __rep const&
//     .__s     -> __short const&
//     .__size_ -> unsigned char

Um ehrlich zu sein, bin ich mir nicht sicher, ob dies Standard-C++ ist (ich kenne die anfängliche Subsequence-Bestimmung in union aber ich weiß nicht, wie es mit einer anonymen Vereinigung und einem Alias ​​zusammenpasst), aber eine Standardbibliothek darf trotzdem das durch die Implementierung definierte Verhalten nutzen.