Was ist die Mechanik der Kurzstringoptimierung in libc ++?

102

Diese Antwort gibt einen schönen Überblick über die Short String Optimization (SSO). Ich möchte jedoch 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 Zeichenfolgendaten zwischen kurzen und langen Zeichenfolgen? Ist es so einfach wie m_size <= 16oder ist es ein Flag, das Teil einer anderen Mitgliedsvariablen ist? (Ich stelle mir vor, dass m_sizeoder ein Teil davon auch zum Speichern von Zeichenfolgendaten verwendet werden könnte).

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

Hier sind einige Beobachtungen nach dem Betrachten der Quelle :

libc ++ kann mit zwei leicht unterschiedlichen Speicherlayouts für die Zeichenfolgenklasse kompiliert werden. Dies wird durch das _LIBCPP_ALTERNATE_STRING_LAYOUTFlag gesteuert . Beide Layouts unterscheiden auch zwischen Little-Endian- und Big-Endian-Maschinen, sodass wir insgesamt 4 verschiedene Varianten haben. Ich werde im Folgenden das "normale" Layout und Little-Endian annehmen.

Unter der Annahme, dass dies size_type4 Bytes und value_type1 Byte sind, würden die ersten 4 Bytes eines Strings im Speicher folgendermaßen 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 der kurzen Zeichenfolge in den oberen 7 Bits liegt, muss sie beim Zugriff verschoben werden:

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

In ähnlicher Weise verwendet der Getter und Setter für die Kapazität eines langen Strings __long_mask, um das zu umgehenis_long Bit zu umgehen.

Ich suche immer noch nach einer Antwort auf meine erste Frage, dh welchen Wert würde __min_capdie Kapazität von kurzen Strings für verschiedene Architekturen haben?

Andere Standardbibliotheksimplementierungen

Diese Antwort gibt einen schönen Überblick über std::stringSpeicherlayouts in anderen Standardbibliotheksimplementierungen.

ValarDohaeris
quelle
libc ++ ist Open-Source, Sie können seinen stringHeader hier finden , ich überprüfe es im Moment :)
Matthieu M.
@Matthieu M.: Ich hatte das schon einmal gesehen, leider ist es eine sehr große Datei, danke für die Hilfe beim Auschecken.
ValarDohaeris
@Ali: Ich bin beim Googeln darüber gestolpert. In diesem Blogbeitrag heißt es jedoch ausdrücklich, dass es sich nur um eine Illustration von SSO handelt und nicht um eine hochoptimierte Variante, die in der Praxis verwendet werden würde.
ValarDohaeris

Antworten:

120

Die libc ++ basic_stringist so konzipiert, dass sie sizeofauf allen Architekturen 3 Wörter enthält sizeof(word) == sizeof(void*). Sie haben das Long / Short-Flag und das Größenfeld in der Kurzform korrekt zerlegt.

Welchen Wert würde __min_cap, die Kapazität von kurzen Zeichenfolgen, für verschiedene Architekturen annehmen?

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

  • 1 Bit geht an das Long / Short-Flag.
  • 7 Bits gehen auf die Größe.
  • Angenommen char, 1 Byte geht an die nachfolgende Null (libc ++ speichert immer eine nachfolgende Null hinter den Daten).

Dies lässt 3 Wörter minus 2 Bytes übrig, um eine kurze Zeichenfolge zu speichern (dh 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 wichtiges Entwurfsziel war die Minimierung sizeof(string), während der interne Puffer so groß wie möglich gemacht wurde. Das Grundprinzip besteht darin, die Bewegungskonstruktion und die Bewegungszuweisung zu beschleunigen. Je größer diesizeof , desto mehr Wörter müssen Sie während einer Zugkonstruktion oder einer Zugzuweisung bewegen.

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

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

Es gibt ein Konfigurationsflag namens, _LIBCPP_ABI_ALTERNATE_STRING_LAYOUTdas die Datenelemente so neu anordnet, 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 Veränderung ist der Glaube, dass Putten __data_ erste Mal aufgrund einer besseren Ausrichtung einige Leistungsvorteile hat. Es wurde versucht, die Leistungsvorteile zu messen, und es war schwierig zu messen. Dies wird die Leistung nicht verschlechtern und möglicherweise etwas verbessern.

Die Flagge sollte mit Vorsicht verwendet werden. Es ist ein anderes ABI, und wenn es versehentlich mit einem libc ++ gemischt wird, std::stringdas mit einer anderen Einstellung von kompiliert wurde _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT, entstehen Laufzeitfehler.

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

Howard Hinnant
quelle
17
Ich bin nicht sicher, ob zwischen libc ++ und Facebook Folly eine Lizenzkompatibilität besteht, aber der FBstring kann ein zusätzliches Zeichen (dh 23) speichern, indem er die Größe auf die verbleibende Kapazität ändert , sodass er für eine kurze Zeichenfolge von 23 Zeichen die doppelte Aufgabe als Nullterminator ausführen kann .
TemplateRex
20
@ TemplateRex: Das ist klug. Wenn libc ++ jedoch übernommen wird, muss libc ++ ein anderes Merkmal aufgeben, das mir an seinem std :: string gefällt: Ein konstruierter Standardwert stringsind alle 0 Bits. Das macht die Standardkonstruktion sehr effizient. Und wenn Sie bereit sind, die Regeln zu biegen, manchmal sogar frei. Sie könnten beispielsweise callocspeichern und es einfach als voll von standardmäßig erstellten Zeichenfolgen deklarieren.
Howard Hinnant
6
Ah, 0-init ist in der Tat nett! Übrigens hat FBstring 2 Flag-Bits, die kurze, mittlere und große Strings anzeigen. Es verwendet das SSO für Zeichenfolgen mit bis zu 23 Zeichen und verwendet dann einen Speicherbereich für Zeichenfolgen mit bis zu 254 Zeichen und darüber hinaus COW (ich weiß, in C ++ 11 nicht mehr legal).
TemplateRex
Warum können Größe und Kapazität nicht in ints gespeichert werden, sodass die Klasse auf 64-Bit-Architekturen auf nur 16 Byte gepackt werden kann?
Phuclv
@ LưuVĩnhPhúc: Ich wollte Zeichenfolgen mit mehr als 2 GB auf 64-Bit zulassen. Die Kosten sind zugegebenermaßen höher sizeof. Gleichzeitig chargeht der interne Puffer für von 14 auf 22, was ein ziemlich guter Vorteil ist.
Howard Hinnant
21

Die libc ++ - Implementierung ist etwas kompliziert. Ich werde das alternative Design ignorieren und einen kleinen Endian-Computer annehmen:

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

Hinweis: __compressed_pairist im Wesentlichen ein Paar, das für die Optimierung der leeren Basis optimiert wurde , auch bekannt als template <T1, T2> struct __compressed_pair: T1, T2 {};; In jeder Hinsicht können Sie es als reguläres Paar betrachten. Ihre Bedeutung kommt nur zum Ausdruck, weil sie std::allocatorstaatenlos und damit leer ist.

Okay, das ist ziemlich roh, also lasst uns die Mechanik überprüfen! Intern rufen viele Funktionen auf, __get_pointer()die selbst aufrufen , __is_longum festzustellen, ob die Zeichenfolge die Darstellung __longoder verwendet __short:

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 Subsequenz-Bereitstellung in union, weiß aber nicht, wie sie mit einer anonymen Vereinigung und einem zusammengewürfelten Aliasing zusammenwirkt), aber eine Standardbibliothek darf die definierte Implementierung nutzen Verhalten sowieso.

Matthieu M.
quelle
Vielen Dank für diese ausführliche Antwort! Das einzige Stück, das mir fehlt, ist, was __min_capfür verschiedene Architekturen bewertet werden würde. Ich bin nicht sicher, was sizeof()zurückkehren wird und wie es durch Aliasing beeinflusst wird.
ValarDohaeris
1
@ValarDohaerist die Implementierung definiert. In der Regel erwarten Sie 3 * the size of one pointerin diesem Fall 12 Oktette auf einem 32-Bit-Bogen und 24 auf einem 64-Bit-Bogen.
Justin