Kapitel 4. Die Verwendung von Zeichenfolgen optimieren: Eine Fallstudie

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: translation-feedback@oreilly.com

Nur wenige können die magische Schnur berühren,
und lauter Ruhm ist stolz, sie zu gewinnen:
Wehe denen, die nie singen,
sondern mit all ihrer Musik in ihnen sterben!"

Oliver Wendell Holmes, "The Voiceless" (1858)

Die C++ std::string Klassenvorlagen gehören zu den meistgenutzten Funktionen der C++ Standardbibliothek. In einem Artikel im Google Chromium-Entwicklerforum heißt es beispielsweise, dass std::string die Hälfte aller Aufrufe des Speichermanagers in Chromium ausmacht. Jeder häufig ausgeführte Code, der Zeichenketten manipuliert, ist ein fruchtbarer Boden für die Optimierung. In diesem Kapitel wird die Optimierung des Umgangs mit Zeichenketten diskutiert, um wiederkehrende Themen der Optimierung zu veranschaulichen.

Warum Strings ein Problem sind

Das Konzept von Strings ist einfach, aber es ist ziemlich schwierig, sie effizient zu implementieren. Die besondere Kombination von Funktionen in std::string interagiert auf eine Weise, die eine effiziente Implementierung fast unmöglich macht. Als dieses Buch geschrieben wurde, boten mehrere beliebte Compiler std::string Implementierungen an, die in verschiedener Hinsicht nicht konform waren.

Außerdem wurde das Verhalten von std::string im Laufe der Jahre geändert, um mit den Änderungen im C++ Standard Schritt zu halten. Das bedeutet, dass sich eine konforme std::string -Implementierung aus einem C++98-Compiler möglicherweise nicht genauso verhält wie eine std::string -Implementierung nach C++11.

Strings haben einige Eigenschaften, die ihre Verwendung teuer machen, unabhängig von ihrer Implementierung. Sie werden dynamisch zugewiesen, sie verhalten sich wie Werte in Ausdrücken und ihre Implementierung erfordert eine Menge Kopiervorgänge.

Strings werden dynamisch zugewiesen

Strings sind praktisch, weil sie automatisch mitwachsen, wenn sie ihren Inhalt aufnehmen müssen. Im Gegensatz dazu arbeiten die Funktionen der C-Bibliotheken (strcat(), strcpy(), etc.) mit Zeichenarrays fester Größe. Um diese Flexibilität zu erreichen, werden Strings dynamisch zugewiesen. Die dynamische Zuweisung ist im Vergleich zu den meisten anderen C++-Funktionen teuer, so dass Strings auf jeden Fall zu den Optimierungsschwerpunkten gehören. Die dynamisch zugewiesene Speicherung wird automatisch freigegeben, wenn eine String-Variable den Gültigkeitsbereich verlässt oder der Variablen ein neuer Wert zugewiesen wird. Das ist bequemer, als die Speicherung manuell freizugeben, wie es bei einem dynamisch zugewiesenen Zeichenarray im C-Stil der Fall wäre, wie im folgenden Code:

char* p = (char*) malloc(7);
strcpy(p, "string");
   ...
free(p);

Der interne Zeichenpuffer der Zeichenkette hat jedoch immer noch eine feste Größe. Jede Operation, die die Zeichenkette verlängert, wie das Anhängen eines Zeichens oder einer Zeichenkette, kann dazu führen, dass die Zeichenkette die Größe ihres internen Puffers überschreitet. Wenn das passiert, holt sich die Operation einen neuen Puffer vom Speichermanager und kopiert die Zeichenfolge in den neuen Puffer.

std::string Implementierungen wenden einen Trick an, um die Kosten für die Neuzuweisung von Speicherplatz für den Zeichenpuffer zu amortisieren, wenn die Zeichenfolge wächst. Anstatt die genaue Anzahl der benötigten Zeichen beim Speichermanager anzufordern, rundet die String-Implementierung die Anforderung auf eine größere Anzahl von Zeichen auf. Einige Implementierungen runden die Anfrage beispielsweise auf die nächste Potenz von 2 auf. Die Zeichenkette kann dann auf das Doppelte ihrer aktuellen Größe anwachsen, bevor sie erneut den Speichermanager ansprechen muss. Wenn das nächste Mal eine Operation die Länge der Zeichenkette erweitern muss, ist im vorhandenen Puffer Platz und es muss kein neuer Puffer zugewiesen werden. Der Vorteil dieses Tricks ist, dass sich die Kosten für das Anhängen von Zeichen an eine Zeichenkette asymptotisch einer Konstante nähern, wenn die Zeichenkette länger wird. Der Preis für diesen Trick ist, dass Strings etwas ungenutzten Speicherplatz mit sich herumtragen. Wenn die Zeichenkette Anfragen auf eine Potenz von 2 aufrundet, kann bis zur Hälfte der Speicherung in einer Zeichenkette ungenutzt sein.

Zeichenketten sind Werte

Strings verhalten sich in Zuweisungen und Ausdrücken wie Werte (siehe "Wertobjekte und Entity-Objekte"). Numerische Konstanten wie 2 und 3,14159 sind Werte. Du kannst einer Variablen einen neuen Wert zuweisen, aber wenn du die Variable änderst, ändert sich der Wert nicht. Ein Beispiel:

int i,j;
i = 3; // i has the value 3
j = i; // j also has the value 3
i = 5; // i now has the value 5, j still has the value 3

Das Zuweisen einer Zeichenkette an eine andere funktioniert auf die gleiche Weise, als ob jede String-Variable eine private Kopie ihres Inhalts hätte:

std::string s1, s2;
s1 = “hot”;  // s1 is "hot"
s2 = s1;     // s2 is "hot"
s1[0] = 'n'; // s2 is still "hot", s1 is "not"

Da Strings Werte sind, sind auch die Ergebnisse von String-Ausdrücken Werte. Wenn du Strings verkettest, wie in der Anweisung s1 = s2 + s3 + s4;, ist das Ergebnis von s2 + s3 ein neu zugewiesener temporärer String-Wert. Das Ergebnis der Verkettung von s4 mit dieser temporären Zeichenfolge ist ein weiterer temporärer Zeichenfolgenwert. Dieser Wert ersetzt den vorherigen Wert von s1. Dann werden die dynamisch zugewiesene Speicherung für die erste temporäre Zeichenfolge und der vorherige Wert von s1 freigegeben. Dies führt zu einer Menge von Aufrufen des Speichermanagers.

Strings machen eine Menge Kopien

Da sich Strings wie Werte verhalten, darf die Änderung eines Strings keine anderen Strings verändern. Aber Strings haben auch mutierende Operationen, die den Inhalt eines Strings verändern. Wegen dieser Veränderungen muss sich jede String-Variable so verhalten, als ob sie eine private Kopie des Strings hätte. Die einfachste Möglichkeit, dieses Verhalten zu implementieren, besteht darin, die Zeichenkette zu kopieren, wenn sie konstruiert, zugewiesen oder als Argument an eine Funktion übergeben wird. Wenn Strings auf diese Weise implementiert werden, sind Zuweisung und Argumentübergabe teuer, aber mutierende Funktionen und nichtconst Referenzen sind billig.

Es gibt ein bekanntes Programmieridiom für Dinge, die sich wie Werte verhalten, aber teuer zu kopieren sind. Sie wird "copy on write" genannt und in der C++-Literatur oft mit COW abgekürzt (siehe "Implementiere das Idiom "Copy on Write""). In einem COW-String kann die dynamisch zugewiesene Speicherung zwischen Strings geteilt werden. Ein Referenzzähler zeigt jedem String an, ob er die gemeinsame Speicherung nutzt. Wenn ein String einem anderen zugewiesen wird, wird nur ein Zeiger kopiert und der Referenzzähler wird erhöht. Jede Operation, die den Wert einer Zeichenkette ändert, prüft zunächst, ob es nur einen Zeiger auf diese Speicherung gibt. Wenn mehrere Zeichenketten auf die Speicherung zeigen, wird bei jeder Änderung (die den Inhalt der Zeichenkette verändern kann) neuer Speicher zugewiesen und eine Kopie der Zeichenkette erstellt, bevor die Änderung vorgenommen wird:

COWstring s1, s2;
s1 = "hot";  // s1 is "hot"
s2 = s1;     // s2 is "hot" (s1 and s2 point to the same storage)
s1[0] = 'n'; // s1 makes a new copy of its storage before 
             // changing anything
             // s2 is still "hot", s1 is "not"

Copy-on-Write ist ein so bekanntes Idiom, dass Entwickler leicht davon ausgehen können, dass std::string auf diese Weise implementiert ist. Aber Copy-on-Write ist nicht einmal für C++11-konforme Implementierungen erlaubt und ist in jedem Fall problematisch.

Wenn Strings mit Copy-on-Write implementiert werden, sind Zuweisung und Argumentübergabe billig, aber nichtconst Referenzen und jeder Aufruf einer mutierenden Funktion erfordert eine teure Allocate-and-Copy-Operation, wenn der String gemeinsam genutzt wird. COW-Strings sind auch in konkurrierendem Code teuer. Jede mutierende Funktion und jede nicht-const Referenz greift auf die Referenzanzahl zu. Wenn mehrere Threads auf den Referenzwert zugreifen, muss jeder Thread eine spezielle Anweisung verwenden, um eine Kopie des Referenzwerts aus dem Hauptspeicher zu erhalten, um sicherzustellen, dass kein anderer Thread den Wert geändert hat (siehe "Speicherzäune").

In C++11 und später wird der Kopieraufwand durch das Vorhandensein von rValue-Referenzen und der damit verbundenen Move-Semantik (siehe "Implementieren der Move-Semantik") etwas verringert. Wenn eine Funktion eine rWert-Referenz als Argument annimmt, kann der String eine kostengünstige Zeigerkopie durchführen, wenn das eigentliche Argument ein rWert-Ausdruck ist, wodurch eine Kopie eingespart wird.

Erster Versuch zur Optimierung von Strings

Angenommen, das Profiling eines großen Programms zeigt, dass die in Beispiel 4-1 dargestellte Funktion remove_ctrl() viel Zeit im Programm verbraucht. Diese Funktion entfernt Steuerzeichen aus einer Kette von ASCII-Zeichen. Sie sieht ganz harmlos aus, aber die Leistung der Funktion ist in der geschriebenen Form aus vielen Gründen schrecklich. Tatsächlich ist diese Funktion eine kompakte Demonstration der Gefahr, eine Programmieraufgabe ohne Rücksicht auf die Leistung auszuführen.

Beispiel 4-1. remove_ctrl(): Code bereit zum Optimieren
std::string remove_ctrl(std::string s) {
    std::string result;
    for (int i=0; i<s.length(); ++i) {
        if (s[i] >= 0x20)
            result = result + s[i];
    }
    return result;
}

remove_ctrl() verarbeitet jedes Zeichen im Argument string s in einer Schleife. Der Code in der Schleife ist das, was diese Funktion zu einem Hot Spot macht. Die if-Bedingung holt ein Zeichen aus der Zeichenkette und vergleicht es mit einer Literalkonstante. Das wird wahrscheinlich nicht das Problem sein. Die kontrollierte Anweisung in Zeile 5 ist eine andere Geschichte.

Wie bereits erwähnt, ist der String-Verkettungsoperator teuer. Er ruft den Speichermanager auf, um ein neues temporäres String-Objekt zu erstellen, das den verketteten String enthält. Wenn das Argument für remove_ctrl() typischerweise eine Zeichenkette mit druckbaren Zeichen ist, dann erstellt remove_ctrl() für fast jedes Zeichen in s ein neues temporäres String-Objekt. Bei einer Zeichenkette mit 100 Zeichen sind das 100 Aufrufe an den Speichermanager, um Speicher für die temporäre Zeichenkette zu erstellen, und weitere 100 Aufrufe, um die Speicherung freizugeben.

Zusätzlich zu den temporären Strings, die für das Ergebnis der Verkettung zugewiesen werden, können weitere Strings zugewiesen werden, wenn der String-Ausdruck result zugewiesen wird, je nachdem, wie Strings implementiert sind:

  • Wenn Strings mit dem Copy-on-Write-Idiom implementiert werden, führt der Zuweisungsoperator eine effiziente Zeigerkopie durch und erhöht die Referenzanzahl.

  • Wenn für Strings ein nicht gemeinsamer Puffer implementiert ist, muss der Zuweisungsoperator den Inhalt des temporären Strings kopieren. Wenn die Implementierung naiv ist oder der Puffer von resultnicht über genügend Kapazität verfügt, weist der Zuweisungsoperator auch einen neuen Puffer zu, in den er kopiert. Dies führt zu 100 Kopiervorgängen und bis zu 100 zusätzlichen Zuweisungen.

  • Wenn der Compiler rValue-Referenzen und Move-Semantik im Stil von C++11 implementiert, kann der Compiler aufgrund der Tatsache, dass das Ergebnis des Verkettungsausdrucks ein rValue ist, den Move-Konstruktor von resultanstelle des Copy-Konstruktors aufrufen. Das Ergebnis ist, dass das Programm eine effiziente Zeigerkopie durchführt.

Die Verkettungsoperation kopiert außerdem bei jeder Ausführung alle zuvor verarbeiteten Zeichen in die temporäre Zeichenfolge. Wenn der Argument-String n Zeichen enthält, kopiert remove_ctrl() O(n2) Zeichen. Das Ergebnis all dieser Zuweisungen und Kopien ist eine schlechte Leistung.

Da remove_ctrl() eine kleine, eigenständige Funktion ist, ist es möglich, ein Test-Harness zu erstellen, das die Funktion wiederholt aufruft, um genau zu messen, wie viel Leistung durch Optimierung verbessert werden kann. Die Erstellung von Testprogrammen und die Leistungsmessung werden in Kapitel 3 behandelt. Der Code für das Test-Harness und anderer Code aus dem Buch kann von meiner Website heruntergeladen werden.

Ich habe einen Zeittest geschrieben, bei dem remove_ctrl() wiederholt mit einer 222 Zeichen langen Argumentationskette aufgerufen wurde, die mehrere Steuerzeichen enthielt. Im Durchschnitt dauerte jeder Aufruf 24,8 Mikrosekunden. Diese Zahl ist an sich nicht wichtig, da sie von meinem PC (Intel i7 Tablet), dem Betriebssystem (Windows 8.1) und dem Compiler (Visual Studio 2010, 32-Bit, Release Build) abhängt. Vielmehr bildet sie eine Grundlage für die Messung der Leistungsverbesserung. In den folgenden Abschnitten beschreibe ich eine Reihe von Optimierungsschritten und die daraus resultierende Verbesserung der Leistung der Funktion remove_ctrl().

Mutating-String-Operationen verwenden, um Temporäre zu eliminieren

Ich habe damit begonnen, remove_ctrl() zu optimieren, indem ich Zuweisungs- und Kopieroperationen entfernt habe. Beispiel 4-2 ist eine verbesserte Version von remove_ctrl(), in der der Verkettungsausdruck in Zeile 5, der so viele neue temporäre String-Objekte erzeugte, durch den mutierenden, verkettenden Zuweisungsoperator += ersetzt wurde.

Beispiel 4-2. remove_ctrl_mutating(): String-Operatoren mutieren
std::string remove_ctrl_mutating(std::string s) {
    std::string result;
    for (int i=0; i<s.length(); ++i) {
        if (s[i] >= 0x20)
            result += s[i];
    }
    return result;
}

Diese kleine Änderung hat eine dramatische Auswirkung auf die Leistung. Derselbe Timing-Test ergab jetzt einen Durchschnitt von nur 1,72 Mikrosekunden pro Aufruf, eine 13-fache Verbesserung. Diese Verbesserung ergibt sich aus dem Wegfall aller Aufrufe zur Zuweisung temporärer String-Objekte, um das Ergebnis des Verkettungsausdrucks zu speichern, sowie des damit verbundenen Kopierens und Löschens von temporären Objekten. Je nach String-Implementierung entfallen auch die Zuweisung und das Kopieren bei der Zuweisung.

Reduziere die Neuzuweisung durch Reservierung von Speicherplatz

Die Funktion remove_ctrl_mutating() führt noch eine Operation durch, die result verlängert. Das bedeutet, dass result in regelmäßigen Abständen in einen größeren internen dynamischen Puffer kopiert wird. Wie bereits erwähnt, verdoppelt eine mögliche Implementierung von std::string die Menge der zugewiesenen Speicherung jedes Mal, wenn die Kapazität des Zeichenpuffers der Zeichenkette überschritten wird. Wenn std::string mit dieser Regel implementiert wird, kann die Neuzuweisung bei einer 100-Zeichen-Zeichenfolge bis zu 8 Mal erfolgen.

Wenn wir davon ausgehen, dass Strings in der Regel aus druckbaren Zeichen bestehen und nur gelegentlich Steuerzeichen entfernt werden müssen, dann ist die Länge des String-Arguments s eine hervorragende Schätzung der möglichen Länge des Ergebnisstrings. Beispiel 4-3 verbessert remove_ctrl_mutating(), indem es die Mitgliedsfunktion reserve() von std::stringverwendet, um die geschätzte Menge an Speicherung vorab zuzuweisen. Durch die Verwendung von reserve() wird nicht nur die Neuzuweisung des String-Puffers vermieden, sondern auch die Cache-Lokalität der Daten, auf die die Funktion zugreift, verbessert, sodass wir noch mehr Nutzen aus dieser Änderung ziehen können.

Beispiel 4-3. remove_ctrl_reserve(): Speicherung reservieren
std::string remove_ctrl_reserve(std::string s) {
    std::string result;
    result.reserve(s.length());
    for (int i=0; i<s.length(); ++i) {
        if (s[i] >= 0x20)
            result += s[i];
    }
    return result;
}

Der Wegfall mehrerer Zuweisungen führt zu einer deutlichen Verbesserung der Leistung. Ein Test mit remove_ctrl_reserve() verbraucht 1,47 Mikrosekunden pro Aufruf, eine Verbesserung von 17 % gegenüber remove_ctrl_mutating().

Kopieren von String-Argumenten eliminieren

Bisher habe ich remove_ctrl() erfolgreich optimiert, indem ich die Aufrufe des Speichermanagers entfernt habe. Es ist daher sinnvoll, weiterhin nach Zuweisungen zu suchen, die entfernt werden können.

Wenn ein String-Ausdruck als Wert an eine Funktion übergeben wird, wird das formale Argument (in diesem Fall s) als Kopie konstruiert. Abhängig von der String-Implementierung kann dies zu einer Kopie führen:

  • Wenn Strings mit dem Copy-on-Write-Idiom implementiert werden, erzeugt der Compiler einen Aufruf des Copy-Konstruktors, der eine effiziente Zeigerkopie durchführt und die Referenzanzahl erhöht.

  • Wenn Strings eine nicht freigegebene Pufferimplementierung haben, muss der Kopierkonstruktor einen neuen Puffer zuweisen und den Inhalt des aktuellen Arguments kopieren.

  • Wenn der Compiler rValue-Referenzen und eine Move-Semantik im Stil von C++11 implementiert hat, ist das eigentliche Argument ein Ausdruck und ein rValue, so dass der Compiler den Move-Konstruktor aufruft, was zu einer effizienten Zeigerkopie führt. Wenn das eigentliche Argument eine Variable ist, wird der Kopierkonstruktor des formalen Arguments aufgerufen, was zu einer Zuweisung und Kopie führt. Rvalue-Referenzen und die Move-Semantik werden unter "Implementierung der Move-Semantik" genauer beschrieben .

remove_ctrl_ref_args() in Beispiel 4-4 ist eine verbesserte Funktion, die s beim Aufruf nicht kopiert. Da die Funktion s nicht verändert, gibt es keinen Grund, eine separate Kopie von s zu erstellen. Stattdessen nimmt remove_ctrl_ref_args() einen const Verweis auf s als Argument. Das spart eine weitere Zuweisung. Da die Zuweisung teuer ist, kann es sich lohnen, auch nur eine Zuweisung einzusparen.

Beispiel 4-4. remove_ctrl_ref_args(): Argumentkopie eliminiert
std::string remove_ctrl_ref_args(std::string const& s) {
    std::string result;
    result.reserve(s.length());
    for (int i=0; i<s.length(); ++i) {
        if (s[i] >= 0x20)
            result += s[i];
    }
    return result;
}

Das Ergebnis ist eine Überraschung. Der Timing-Test von remove_ctrl_ref_args() benötigte 1,60 Mikrosekunden pro Aufruf, 8% schlechter als remove_ctrl_reserve().

Was ist hier los? Visual Studio 2010 kopiert String-Werte beim Aufruf, also sollte diese Änderung eine Zuweisung einsparen. Entweder wird diese Einsparung nicht realisiert, oder etwas anderes, das mit der Änderung von s von String zu String-Referenz zusammenhängt, muss diese Einsparung aufbrauchen.

Referenzvariablen sind als Zeiger implementiert. Überall dort, wo s in remove_ctrl_ref_args() auftaucht, dereferenziert das Programm also einen Zeiger, den es in remove_ctrl_reserve() nicht dereferenzieren musste. Ich vermute, dass diese zusätzliche Arbeit ausreicht, um die Leistungseinbußen zu erklären.

Zeiger-Dereferenzierung mit Iteratoren beseitigen

Die Lösung ist die Verwendung von Iteratoren über die Zeichenkette, wie in Beispiel 4-5. String-Iteratoren sind einfache Zeiger auf den Zeichenpuffer. Das spart zwei Dereferenzierungsoperationen gegenüber dem Nicht-Iterator-Code in der Schleife.

Beispiel 4-5. remove_ctrl_ref_args_it(): Iterator-Version von remove_ctrl_ref_args()
std::string remove_ctrl_ref_args_it(std::string const& s) {
    std::string result;
    result.reserve(s.length());
    for (auto it=s.begin(),end=s.end(); it != end; ++it) {
        if (*it >= 0x20)
            result += *it;
    }
    return result;
}

Der Zeittest für remove_ctrl_ref_args_it() ergab ein zufriedenstellendes Ergebnis von 1,04 Mikrosekunden pro Aufruf. Es ist definitiv besser als die Nicht-Iterator-Version. Aber was wäre, wenn s eine String-Referenz wäre? Um herauszufinden, ob diese Optimierung tatsächlich etwas gebracht hat, habe ich eine Iterator-Version von remove_ctrl_reserve() programmiert. Der Timing-Test für remove_ctrl_reserve_it() dauerte 1,26 Mikrosekunden pro Aufruf, statt 1,47 Mikrosekunden. Die Optimierung der String-Referenz-Argumente hat die Leistung definitiv verbessert.

Tatsächlich habe ich Iterator-Versionen aller von remove_ctrl() abgeleiteten Funktionen programmiert. Iteratoren waren in allen Fällen ein klarer Gewinn gegenüber den tiefgestellten Versionen (in "Zweiter Versuch zur Optimierung von Strings" werden wir jedoch sehen, dass dies nicht immer der Fall ist).

remove_ctrl_ref_args_it() enthält eine weitere bemerkenswerte Optimierung. Der Wert s.end(), der zur Steuerung der for Schleife verwendet wird, wird bei der Initialisierung der Schleife zwischengespeichert. Das spart weitere 2n Indirektionen, wobei n die Länge des Argumentstrings ist.

Das Kopieren von zurückgegebenen String-Werten eliminieren

Die ursprüngliche Funktion remove_ctrl() gibt ihr Ergebnis als Wert zurück. C++ kopiert das Ergebnis in den aufrufenden Kontext, obwohl der Compiler die Kopierkonstruktion nach Möglichkeit aussparen (d.h. vereinfachen) kann. Wenn wir sicher sein wollen, dass es keine Kopie gibt, haben wir mehrere Möglichkeiten. Eine Möglichkeit, die für alle Versionen von C++ und alle String-Implementierungen gilt, ist die Rückgabe des Strings als Out-Parameter. Das ist genau das, was der Compiler macht, wenn er eine Kopierkonstruktion ausschließt. Eine verbesserte Version von remove_ctrl_ref_args_it() findest du in Beispiel 4-6.

Beispiel 4-6. remove_ctrl_ref_result_it(): Kopie des Rückgabewerts eliminiert
void remove_ctrl_ref_result_it(
    std::string& result,
    std::string const& s) 
{
    result.clear();
    result.reserve(s.length());
    for (auto it=s.begin(),end=s.end(); it != end; ++it) {
        if (*it >= 0x20)
            result += *it;
    }
}

Wenn ein Programm remove_ctrl_ref_result_it() aufruft, wird eine Referenz auf eine String-Variable in das formale Argument result übergeben. Wenn die String-Variable, auf die result verweist, leer ist, wird durch den Aufruf von reserve() Speicherplatz für genügend Zeichen reserviert. Wenn die String-Variable schon einmal benutzt wurde - wenn das Programm remove_ctrl_ref_result_it() in einer Schleife aufgerufen hat -, kann der Puffer bereits groß genug sein. Wenn die Funktion zurückkehrt, enthält die String-Variable im Aufrufer den Rückgabewert, ohne dass eine Kopie erforderlich ist. Das Schöne an remove_ctrl_ref_result_it() ist, dass es in vielen Fällen jede Zuweisung überflüssig macht.

Die gemessene Leistung von remove_ctrl_ref_result_it() liegt bei 1,02 Mikrosekunden pro Aufruf und ist damit etwa 2 % schneller als die Vorgängerversion.

remove_ctrl_ref_result_it() ist sehr effizient, aber seine Schnittstelle kann auf eine Weise missbraucht werden, wie es bei der ursprünglichen remove_ctrl() nicht der Fall war. Eine Referenz - selbst eine const Referenz - verhält sich nicht genau so wie ein Wert. Der folgende Aufruf führt zu ungewollten Ergebnissen und gibt einen leeren String zurück:

std::string foo("this is a string");
remove_ctrl_ref_result_it(foo, foo);

Zeichenketten anstelle von Strings verwenden

Wenn ein Programm besonders leistungsfähig sein muss, ist es möglich, die C++-Standardbibliothek ganz zu umgehen und die Funktion mit den String-Funktionen im C-Stil zu programmieren, wie in Beispiel 4-7. Die String-Funktionen im C-Stil sind schwieriger zu benutzen als std::string, aber der Leistungsgewinn kann beeindruckend sein. Um die String-Funktionen im C-Stil zu verwenden, muss der Programmierer entweder manuell Zeichenpuffer zuweisen und freigeben oder statische Arrays verwenden, die auf die Größe des schlimmsten Falles ausgelegt sind. Die Deklaration einer Reihe von statischen Arrays ist problematisch, wenn der Speicherplatz begrenzt ist. In der Regel ist es jedoch möglich, große temporäre Puffer in der lokalen Speicherung (d. h. auf dem Funktionsaufrufstapel) zu deklarieren. Diese Puffer werden mit vernachlässigbaren Laufzeitkosten zurückgewonnen, wenn die Funktion beendet wird. Außer in sehr eingeschränkten Embedded-Umgebungen ist es kein Problem, im schlimmsten Fall einen Puffer von 1.000 oder sogar 10.000 Zeichen auf dem Stack zu deklarieren.

Beispiel 4-7. remove_ctrl_cstrings(): Codierung auf dem Bare Metal
void remove_ctrl_cstrings(char* destp, char const* srcp, size_t size) {
    for (size_t i=0; i<size; ++i) {
        if (srcp[i] >= 0x20)
            *destp++ = srcp[i];
    }
    *destp = 0;
}

remove_ctrl_cstrings() brauchte im Timing-Test 0,15 Mikrosekunden pro Aufruf. Das ist 6 Mal schneller als sein Vorgänger und erstaunliche 170 Mal schneller als die ursprüngliche Funktion. Ein Grund für die Verbesserung ist die Eliminierung mehrerer Funktionsaufrufe und die damit verbundene Verbesserung der Cache-Lokalität.

Die ausgezeichnete Cache-Lokalität kann jedoch dazu beitragen, dass eine einfache Leistungsmessung irreführend ist. Im Allgemeinen wird der Cache durch andere Operationen zwischen den Aufrufen von remove_ctrl_cstrings() geleert. Wenn die Funktion jedoch in einer engen Schleife aufgerufen wird, bleiben Anweisungen und Daten im Cache.

Ein weiterer Faktor, der sich auf remove_ctrl_cstrings() auswirkt, ist die Tatsache, dass sie eine deutlich andere Schnittstelle als die ursprüngliche Funktion hat. Wenn sie von vielen Stellen aus aufgerufen wird, ist es ein erheblicher Aufwand, alle Aufrufe zu ändern, und möglicherweise eine Optimierung zu viel. Nichtsdestotrotz ist remove_ctrl_cstrings() ein Beispiel dafür, wie viel Leistung ein Entwickler gewinnen kann, wenn er bereit ist, eine Funktion komplett neu zu programmieren und ihre Schnittstelle zu ändern .

Zusammenfassung des ersten Optimierungsversuchs

Tabelle 4-1 fasst die Ergebnisse der Optimierungsbemühungen für remove_ctrl() zusammen. Diese Ergebnisse wurden erzielt, indem eine einfache Regel befolgt wurde: Speicherzuweisungen und damit verbundene Kopiervorgänge wurden entfernt. Die erste Optimierung brachte den größten Geschwindigkeitszuwachs.

Viele Faktoren beeinflussen die absoluten Timings, darunter der Prozessor, die Grundtaktrate, die Speicherbusfrequenz, der Compiler und der Optimierer. Um dies zu verdeutlichen, habe ich Testergebnisse von Debug- und Release-Builds (optimiert) bereitgestellt. Der Code des Release-Builds ist zwar viel schneller als der Debug-Code, aber die Verbesserung ist sowohl im Debug- als auch im Release-Build sichtbar.

Tabelle 4-1. Leistungsübersicht VS 2010, i7
Funktion Debuggen Δ Freigabe Δ Freigabe vs. Debuggen
remove_ctrl() 967 μs 24,8 μs 3802%
remove_ctrl_mutating() 104 μs 834% 1,72 μs 1,341% 5923%
remove_crtl_reserve() 102 μs 142% 1,47 μs 17% 6853%
remove_ctrl_ref_args_it() 215 μs 9% 1,04 μs 21% 20559%
remove_ctrl_ref_result_it() 215 μs 0% 1,02 μs 2% 21012%
remove_ctrl_cstrings() 1 μs 9,698% 0,15 μs 601% 559%

Die prozentuale Verbesserung scheint in den Release-Builds viel dramatischer zu sein. Das ist wahrscheinlich ein Effekt von Amdahls Gesetz. Im Debug-Build ist das Funktions-Inlining ausgeschaltet, was die Kosten jedes Funktionsaufrufs erhöht und dazu führt, dass der Anteil der Laufzeit, der für die Speicherzuweisung verwendet wird, geringer ist.

Zweiter Versuch zur Optimierung von Strings

Es gibt noch andere Wege, die der Entwickler auf der Suche nach besserer Leistung einschlagen kann; wir werden in diesem Abschnitt ein paar weitere Optionen untersuchen.

Verwende einen besseren Algorithmus

Eine Möglichkeit ist der Versuch, den Algorithmus zu verbessern. Das Original remove_ctrl() verwendet einen einfachen Algorithmus, der ein Zeichen nach dem anderen in die Ergebniszeichenkette kopiert. Diese unglückliche Wahl führt zu dem schlechtestmöglichen Zuweisungsverhalten. Beispiel 4-8 verbessert das ursprüngliche Design, indem es ganze Teilstrings in die Ergebniszeichenkette verschiebt. Diese Änderung hat den Effekt, dass die Anzahl der Zuordnungs- und Kopiervorgänge reduziert wird. Eine weitere Optimierung, die in remove_ctrl_block() eingeführt wurde, ist das Zwischenspeichern der Länge des Argumentstrings, um die Kosten für die Schleifenabbruchklausel der äußeren for Schleife zu reduzieren.

Beispiel 4-8. remove_ctrl_block(): ein schnellerer Algorithmus
std::string remove_ctrl_block(std::string s) {
    std::string result;
    for (size_t b=0, i=b, e=s.length(); b < e; b = i+1) {
        for (i=b; i<e; ++i) {
            if (s[i] < 0x20) 
                break;
        }
        result = result + s.substr(b,i-b);
    }
    return result;
}

remove_ctrl_block() führt den Zeittest in 2,91 Mikrosekunden durch, etwa 7 Mal schneller als das Original remove_ctrl().

Diese Funktion kann wiederum auf die gleiche Weise wie zuvor verbessert werden, indem die Verkettung durch eine mutierende Zuweisung ersetzt wird (remove_ctrl_block_mutate(), 1,27 Mikrosekunden pro Aufruf), aber substr() konstruiert immer noch einen temporären String. Da die Funktion Zeichen an result anhängt, kann der Entwickler eine der Überladungen von std::string's append() Mitgliedsfunktion verwenden, um die Teilzeichenkette zu kopieren, ohne eine temporäre Zeichenkette zu erstellen. Die daraus resultierende Funktion remove_ctrl_block_append() (wie in Beispiel 4-9 gezeigt) führt den Zeittest in 0,65 Mikrosekunden pro Aufruf durch. Dieses Ergebnis schlägt die beste Zeit von 1,02 Mikrosekunden pro Aufruf für remove_ctrl_ref_result_it() deutlich und ist 36 Mal besser als das Original remove_ctrl(). Dies ist eine prägnante Demonstration der Leistungsfähigkeit der Auswahl eines guten Algorithmus.

Beispiel 4-9. remove_ctrl_block_append(): ein schnellerer Algorithmus
std::string remove_ctrl_block_append(std::string s) {
    std::string result;
    result.reserve(s.length());
    for (size_t b=0,i=b; b < s.length(); b = i+1) {
        for (i=b; i<s.length(); ++i) {
            if (s[i] < 0x20) break;
        }
        result.append(s, b, i-b);
    }
    return result;
}

Diese Ergebnisse können wiederum verbessert werden, indem die Speicherung in result reserviert und die Kopie des Arguments eliminiert wird (remove_ctrl_block_args(), 0,55 Mikrosekunden pro Aufruf) und indem die Kopie des zurückgegebenen Wertes entfernt wird (remove_ctrl_block_ret(), 0,51 Mikrosekunden pro Aufruf).

Eine Sache, die die Ergebnisse zumindest anfangs nicht verbessert hat, war die Umcodierung von remove_ctrl_block() mit Iteratoren. Nachdem jedoch sowohl das Argument als auch der Rückgabewert zu Referenzparametern gemacht wurden, war die Iteratorversion plötzlich nicht mehr zehnmal so teuer, sondern nur noch 20 % weniger teuer, wie in Tabelle 4-2 zu sehen ist.

Tabelle 4-2. Leistungsübersicht des zweiten remove_ctrl-Algorithmus
Zeit pro Anruf Δ vs. früher
remove_ctrl() 24,8 μs
remove_ctrl_block() 2,91 μs 751%
remove_ctrl_block_mutate() 1,27 μs 129%
remove_ctrl_block_append() 0,65 μs 95%
remove_ctrl_block_args() 0,55 μs 27%
remove_ctrl_block_ret() 0,51 μs 6%
remove_ctrl_block_ret_it() 0,43 μs 19%

Eine andere Möglichkeit, die Leistung zu verbessern, besteht darin, die Zeichenkette des Arguments zu verändern, indem du die Steuerzeichen aus ihr entfernst. Dazu verwendest du die Mutationsfunktion von std::string erase() . Beispiel 4-10 veranschaulicht diesen Ansatz.

Beispiel 4-10. remove_ctrl_erase(): Mutation des String-Arguments anstelle der Erstellung eines Ergebnisstrings
std::string remove_ctrl_erase(std::string s) {
    for (size_t i = 0; i < s.length(); )
        if (s[i] < 0x20)
            s.erase(i,1);
        else ++i;
    return s;
}

Der Vorteil dieses Algorithmus ist, dass s immer kürzer wird und es nie zu einer Neuzuweisung kommt, außer möglicherweise für den zurückgegebenen Wert. Die Leistung dieser Funktion ist hervorragend: Sie schließt den Test in 0,81 Mikrosekunden pro Aufruf ab, also 30 Mal schneller als die ursprüngliche remove_ctrl(). Ein Entwickler, der dieses hervorragende Ergebnis beim ersten Versuch erreicht, könnte sich als Sieger fühlen und sich ohne weitere Anstrengungen vom Schlachtfeld zurückziehen. Manchmal ist ein anderer Algorithmus einfacher zu optimieren oder von Natur aus effizienter.

Einen besseren Compiler verwenden

Ich habe die gleichen Zeittests mit dem Visual Studio 2013 Compiler durchgeführt. Visual Studio 2013 implementiert eine Move-Semantik, die einige der Funktionen deutlich schneller machen sollte. Die Ergebnisse waren jedoch gemischt. Im Debugger war Visual Studio 2013 5-15 % schneller als Visual Studio 2010. Von der Kommandozeile aus war VS2013 5-20 % langsamer. Ich habe den Visual Studio 2015 Release Candidate ausprobiert, aber er war noch langsamer. Das könnte an den Änderungen in den Containerklassen liegen. Ein neuer Compiler kann die Leistung verbessern, aber das muss der Entwickler testen, anstatt es einfach zu glauben.

Eine bessere String-Bibliothek verwenden

Die Definition von std::string war ursprünglich recht vage, um eine breite Palette von Implementierungen zu ermöglichen. Die Anforderungen an Effizienz und Vorhersagbarkeit führten schließlich zu einer Präzisierung des C++-Standards, die die meisten neuen Implementierungen ausschloss. Das für std::string definierte Verhalten ist also ein Kompromiss, der sich aus konkurrierenden Designüberlegungen über einen langen Zeitraum hinweg entwickelt hat:

  • Wie andere Container der Standardbibliothek bietet std::string Iteratoren für den Zugriff auf die einzelnen Zeichen des Strings.

  • Wie C-Zeichenketten bietet std::string eine Array-ähnliche Indizierungsnotation, die operator[] verwendet, um auf die Elemente zuzugreifen. std::string bietet auch einen Mechanismus, um einen Zeiger auf eine C-ähnliche null-terminierte Version der Zeichenkette zu erhalten.

  • std::string hat einen Verkettungsoperator und wertgebende Funktionen, die ihm eine Wertesemantik verleihen, ähnlich wie bei BASIC-Strings.

  • std::string bietet eine begrenzte Anzahl von Operationen, die manche Nutzer als einschränkend empfinden .

Der Wunsch, std::string so effizient wie char Arrays im C-Stil zu machen, zwingt die Implementierung dazu, die Zeichenkette in einem zusammenhängenden Speicher darzustellen. Der C++-Standard schreibt vor, dass die Iteratoren einen zufälligen Zugriff haben müssen, und verbietet eine Copy-on-Write-Semantik. Das macht es einfacher zu definieren, welche Aktionen Iteratoren in einem std::string ungültig machen, schränkt aber den Spielraum für clevere Implementierungen ein.

Außerdem muss die std::string Implementierung, die mit einem kommerziellen C++ Compiler geliefert wird, so einfach sein, dass sie getestet werden kann, um zu garantieren, dass sie in jeder denkbaren Situation ein standardkonformes Verhalten und eine akzeptable Effizienz erzeugt. Die Kosten für den Compilerhersteller, der einen Fehler macht, sind hoch. Das zwingt die Implementierungen zur Einfachheit.

Das standardmäßig definierte Verhalten von std::string birgt einige Schwachstellen. Das Einfügen eines einzelnen Zeichens in eine Zeichenkette mit Millionen von Zeichen führt dazu, dass das gesamte Suffix der Zeichenkette kopiert und möglicherweise neu zugewiesen werden muss. Ebenso müssen alle Teilstring-Operationen, die einen Wert zurückgeben, ihre Ergebnisse zuweisen und kopieren. Manche Entwickler suchen nach Optimierungsmöglichkeiten, indem sie eine oder mehrere der vorherigen Einschränkungen aufheben (Iteratoren, Indexierung, Zugriff auf C-Zeichenfolgen, Wertesemantik, Einfachheit).

Eine umfangreichere Bibliothek für std::string einführen

Manchmal bedeutet die Verwendung einer besseren Bibliothek nicht mehr als die Bereitstellung zusätzlicher String-Funktionen. Hier sind ein paar der vielen Bibliotheken, die mit std::string arbeiten:

Boost String Bibliothek

Die Boost-String-Bibliothek bietet Funktionen für die Tokenisierung, Formatierung und exotischere Manipulationen von std::string. Sie ist ein Leckerbissen für diejenigen, die den <algorithm> Header der Standardbibliothek sehr lieben.

C++ String Toolkit Bibliothek

Eine weitere Möglichkeit ist die C++ String Toolkit Library (StrTk). StrTk ist besonders gut im Parsen und Tokenisieren von Strings und ist kompatibel mit std::string.

Verwende std::stringstream, um Wertesemantik zu vermeiden

In C++ gibt es bereits mehrere String-Implementierungen: die Templating-Zeichenketten mit variabler Länge, auf die mit Iteratoren zugegriffen werden kann ( std::string), die einfachen, iteratorbasierten Zeichenketten ( std::vector<char>) und die älteren, nullterminierten Zeichenketten in Arrays fester Größe (C).

Obwohl es schwierig ist, Zeichenketten im Stil von C gut zu verwenden, haben wir bereits ein Experiment gesehen, das gezeigt hat, dass das Ersetzen von C++'s std::string durch Zeichenarrays im Stil von C die Leistung unter den richtigen Bedingungen dramatisch verbessert. Keine der beiden Implementierungen ist perfekt für jede Situation.

C++ enthält noch eine weitere Art von String. std::stringstream macht für Strings das, was std::ostream für Ausgabedateien macht. Die Klasse std::stringstream kapselt einen dynamisch größenveränderlichen Puffer (in der Regel std::string) auf eine andere Art und Weise, nämlich als Entität (siehe "Wertobjekte und Entitätsobjekte"), an die Daten angehängt werden können. std::stringstream ist ein Beispiel dafür, wie eine andere API auf eine ähnliche Implementierung aufgesetzt werden kann, um eine effizientere Codierung zu fördern. Beispiel 4-11 veranschaulicht seine Verwendung.

Beispiel 4-11. std::stringstream: wie string, aber ein Objekt
std::stringstream s;
for (int i=0; i<10; ++i) {
    s.clear();
    s << "The square of " << i << " is " << i*i << std::endl;
    log(s.str());
}

Dieses Snippet zeigt mehrere optimale Codierungstechniken. Da s als Entität geändert wird, erzeugt der lange Einfügeausdruck keine temporären Dateien, die zugewiesen und in die kopiert werden müssen. Eine weitere bewusste Praxis ist, dass s außerhalb der Schleife deklariert wird. Auf diese Weise wird der interne Puffer innerhalb von s wiederverwendet. Beim ersten Durchlauf der Schleife muss der Puffer möglicherweise mehrmals neu zugewiesen werden, wenn Zeichen angehängt werden, aber bei den folgenden Iterationen ist es unwahrscheinlich, dass der Puffer neu zugewiesen wird. Wäre s dagegen innerhalb der Schleife deklariert worden, wäre bei jedem Schleifendurchlauf ein leerer Puffer erstellt und möglicherweise neu zugewiesen worden, wenn der Einfügeoperator Zeichen anfügte.

Wenn std::stringstream mit Hilfe von std::string implementiert wird, kann es niemals wirklich besser sein als std::string. Sein Vorteil liegt darin, dass er einige der Programmierpraktiken verhindert, die zu Ineffizienz führen.

Eine neue String-Implementierung einführen

Ein Entwickler kann die gesamte String-Abstraktion unzureichend finden. Eine der wichtigsten Eigenschaften von C++ ist, dass Abstraktionen wie Strings nicht in die Sprache eingebaut sind, sondern als Vorlagen oder Funktionsbibliotheken bereitgestellt werden. Alternative Implementierungen haben Zugang zu denselben Sprachmerkmalen wie std::string, so dass die Leistung durch einen ausreichend cleveren Implementierer verbessert werden kann. Durch die Aufhebung einer oder mehrerer der zu Beginn dieses Abschnitts aufgeführten Einschränkungen (Iteratoren, Indexierung, Zugriff auf C-Strings, Einfachheit) erhält eine benutzerdefinierte String-Klasse Zugang zu Optimierungen, die std::string verwehrt sind.

Im Laufe der Zeit wurden viele clevere Datenstrukturen für Strings vorgeschlagen, die versprechen, die Kosten für die Neuzuweisung von Speicher und das Kopieren von String-Inhalten deutlich zu senken. Das kann aus mehreren Gründen ein Sirenengesang sein:

  • Jeder Anwärter auf den Thron von std::string muss in einer Vielzahl von Situationen sowohl ausdrucksstärker als auch effizienter sein als std::string. Die meisten vorgeschlagenen alternativen Implementierungen bieten keine guten Garantien für eine höhere allgemeine Leistung.

  • Jedes Vorkommen von std::string in einem großen Programm durch eine andere Zeichenkette zu ersetzen, ist ein großes Unterfangen, ohne dass man sicher sein kann, dass es einen Unterschied in der Leistung macht.

  • Es wurden zwar viele alternative String-Konzepte vorgeschlagen und einige auch implementiert, aber es dauert mehr als ein paar Minuten zu googeln, um eine String-Implementierung zu finden, die so vollständig, gut getestet und gut verstanden ist wie std::string.

Das Ersetzen von std::string kann praktischer sein, wenn du ein Design überlegst, als wenn du es optimierst. Für ein großes Team mit Zeit und Ressourcen mag das möglich sein. Aber der Gewinn ist so ungewiss, dass diese Optimierung vielleicht eine Brücke zu weit ist. Für die Mutigen und Verzweifelten gibt es jedoch Code in freier Wildbahn, der helfen könnte:

std::string_view

string_view löst einige der Probleme von std::string. Sie enthält einen Zeiger auf Zeichenkettendaten und eine Länge, so dass sie eine Teilzeichenkette von std::string oder eine literale Zeichenkette darstellt. Operationen wie substring und trim sind effizienter als die entsprechenden wertgebenden Memberfunktionen von std::string. string_view ist auf dem Weg, in C++14 zu erscheinen. Einige Compiler haben es bereits in std::experimental. string_view hat größtenteils die gleiche Schnittstelle wie std::string.

Das Problem mit string_view ist, dass der Zeiger nicht gehört. Der Programmierer muss sicherstellen, dass die Lebensdauer eines string_view nicht länger ist als die Lebensdauer des std::string, auf den er zeigt.

folly::fbstring

Folly ist eine ganze Code-Bibliothek, die von Facebook auf seinen eigenen Servern verwendet wird. Sie enthält einen hochoptimierten direkten Ersatz für std::string, der einen nicht zugewiesenen Puffer zur Optimierung kurzer Strings implementiert. fbstringDie Entwickler von Folly behaupten messbare Leistungsverbesserungen.

Aufgrund seiner Herkunft ist Folly ungewöhnlich robust und vollständig. Folly wird auf Linux unterstützt.

Ein Werkzeugkasten mit String-Klassen

Dieser Artikel und Code aus dem Jahr 2000 beschreibt einen Templating-String-Typ mit der gleichen Schnittstelle wie die SGI-Implementierung von std::string. Er bietet einen String mit fester Maximalgröße und einen String-Typ mit variabler Länge. Es ist eine Meisterleistung der Templating-Metaprogrammierung, die für manche Leute schwer zu verstehen sein mag. Für jemanden, der eine bessere Stringklasse entwerfen will, ist sie ein brauchbarer Kandidat.

"C++03 Ausdrucksvorlagen"

Dies ist ein Beitrag aus dem Jahr 2005, in dem einige Templates vorgestellt werden, die das spezielle Problem der Verkettung lösen. Ausdrucksvorlagen setzen den Operator + außer Kraft, um einen Zwischentyp zu erstellen, der die Verkettung von zwei Strings oder einem String und einem String-Ausdruck symbolisch darstellt. Ausdrucksvorlagen verschieben die Zuweisung und das Kopieren an das Ende des Ausdrucks und führen eine Zuweisung durch, wenn die Ausdrucksvorlage einer Zeichenkette zugewiesen wird. Expression Templates sind mit std::string kompatibel. Der vorhandene Code kann die Leistung erheblich verbessern, wenn ein String-Ausdruck eine lange Liste von verketteten Teilstrings ist. Das gleiche Konzept könnte auf eine ganze String-Bibliothek ausgeweitet werden.

Die bessere String-Bibliothek

Dieses Code-Archiv enthält eine universelle String-Implementierung, die sich von std::string unterscheidet, aber einige leistungsstarke Funktionen enthält. Wenn viele Strings aus Teilen anderer Strings aufgebaut sind, ermöglicht bstring die Bildung eines Strings aus einem Offset und einer Länge innerhalb eines anderen Strings. Ich habe mit einer proprietären Implementierung dieser Idee gearbeitet, die sehr effizient war. Es gibt eine C++-Wrapper-Klasse namens CBString für die Bibliothek bstring.

rope<T,alloc>

Dies ist eine String-Bibliothek, mit der du Einfügungen und Löschungen in sehr langen Strings vornehmen kannst. Sie ist nicht mit std::string kompatibel.

Boost String-Algorithmen

Dies ist eine Bibliothek mit String-Algorithmen, die die std::string Mitgliedsfunktionen ergänzen. Sie basieren auf dem Konzept des Suchens und Ersetzens.

Verwende einen besseren Allokator

In jedem std::string befindet sich ein dynamisch zugewiesenes Array von char. std::string ist eine Spezialisierung einer allgemeineren Vorlage, die wie folgt aussieht:

namespace std {
    template < class charT,
               class traits = char_traits<charT>,
               class Alloc = allocator<charT>
               > class basic_string; 
           
    typedef basic_string<char> string;
    ...
};

Der dritte Template-Parameter, Alloc, definiert einen Allokator, eine spezielle Schnittstelle zum C++ Speichermanager. Alloc ist standardmäßig auf std::allocator eingestellt und ruft ::operator new() und ::operator delete() auf, die globalen C++ Speicherallokatorfunktionen.

Das Verhalten von ::operator new() und ::operator delete() sowie von Zuweisungsobjekten wird in Kapitel 13 ausführlicher behandelt. Für den Moment möchte ich nur sagen, dass ::operator new() und ::operator delete() eine sehr komplexe und schwierige Aufgabe haben: die Zuweisung von Speicherplatz für all die vielen Arten von dynamischen Variablen. Sie müssen für große und kleine Objekte und für Single- und Multithreading-Programme funktionieren. Ihr Design ist ein Kompromiss, um diese Allgemeinheit zu erreichen. Manchmal kann ein speziellerer Allokator eine bessere Arbeit leisten. Daher kann Alloc als etwas anderes als der Standardwert angegeben werden, um einen spezialisierten Allokator für std::string bereitzustellen.

Ich habe einen extrem einfachen Allokator programmiert, um zu zeigen, welche Art von Leistungsverbesserung möglich sein könnte. Dieser Allokator verwaltet ein paar Blöcke mit fester Größe des Speichers. Ich habe eine neue typedef für eine Art von String erstellt, die diesen Allocator verwendet. Dann habe ich die ursprüngliche, sehr ineffiziente Version von remove_ctrl() geändert, um die speziellen Strings zu verwenden, wie in Beispiel 4-12 gezeigt.

Beispiel 4-12. Originalversion von remove_ctrl() mit einfachem festen Block-Allokator
typedef std::basic_string<
    char,
    std::char_traits<char>,
    block_allocator<char, 10>> fixed_block_string;

fixed_block_string remove_ctrl_fixed_block(std::string s) {
    fixed_block_string result;
    for (size_t i=0; i<s.length(); ++i) {
        if (s[i] >= 0x20)
            result = result + s[i];
    }
    return result;
}

Das Ergebnis war dramatisch. remove_ctrl_fixed_block() führte denselben Test in 13.636 Millisekunden durch, etwa 7,7 Mal schneller als das Original.

Das Ändern von Zuweisern ist nichts für schwache Nerven. Du kannst Zeichenketten, die auf unterschiedlichen Zuweisern basieren, nicht einander zuweisen. Das hier gezeigte, geänderte Beispiel funktioniert nur, weil s[i] ein char ist und nicht ein einstelliges std::string. Du kannst den Inhalt einer Zeichenkette in eine andere kopieren, indem du sie in eine C-Zeichenkette umwandelst, zum Beispiel mit result = s.c_str();.

Wenn du alle Vorkommen von std::string in fixed_block_string änderst, hat das massive Auswirkungen auf die Codebasis. Aus diesem Grund ist es eine gute Idee, frühzeitig eine projektweite typedef zu erstellen, wenn ein Team denkt, dass es an seinen Strings herumfummeln könnte:

typedef std::string MyProjString;

Dann können Experimente, die eine globale Änderung beinhalten, an einer Stelle durchgeführt werden. Das funktioniert allerdings nur, wenn der neue String dieselben Mitgliedsfunktionen hat wie der, den er ersetzt. Unterschiedlich zugeordnete std::basic_strings haben diese Eigenschaft.

Eliminiere die String-Konvertierung

Zu den komplexen Gegebenheiten der modernen Welt gehört, dass es mehr als eine Art von Zeichenkette gibt. In der Regel erlauben String-Funktionen nur den Vergleich, die Zuweisung oder die Verwendung gleicher Arten von Strings als Operanden oder Argumente, so dass der Programmierer von einer Art String in eine andere konvertieren muss. Jedes Mal, wenn die Konvertierung das Kopieren von Zeichen oder die Zuweisung von dynamischem Speicher erfordert, bietet sich eine Gelegenheit, die Leistung zu verbessern.

Die Bibliothek der Umwandlungsfunktionen selbst kann angepasst werden. Noch wichtiger ist, dass das Design eines großen Programms die Umwandlung einschränken kann.

Umwandlung von C String nach std::string

Eine häufige Quelle für verschwendete Computerzyklen ist die unnötige Konvertierung von nullterminierten Zeichenketten in std::string. Zum Beispiel:

std::string MyClass::Name() const {
    return "MyClass";
}

Diese Funktion muss die Stringkonstante MyClass in eine std::string umwandeln, indem sie Speicher zuweist und die Zeichen in die std::string kopiert. C++ führt diese Umwandlung automatisch durch, da std::string einen Konstruktor hat, der ein char* Argument annimmt.

Die Umwandlung in std::string ist unnötig. std::string hat einen Konstruktor, der ein Argument char* akzeptiert, so dass die Umwandlung automatisch erfolgt, wenn der von Name() zurückgegebene Wert einem String zugewiesen oder an eine Funktion übergeben wird, die ein String-Argument akzeptiert. Die vorherige Funktion hätte genauso gut wie folgt geschrieben werden können:

char const* MyClass::Name() const {
    return "MyClass";
}

Dadurch wird die Umwandlung des zurückgegebenen Wertes auf den Zeitpunkt verschoben, an dem er tatsächlich verwendet wird. Zum Zeitpunkt der Verwendung ist die Umwandlung oft nicht nötig:

char const* p = myInstance->Name(); // no conversion
std::string s = myInstance->Name(); // conversion to std::string
std::cout << myInstance->Name();    // no conversion

Ein großes Problem bei der Konvertierung von Zeichenketten ist, dass ein großes Softwaresystem aus mehreren Schichten bestehen kann. Wenn eine Schicht eine std::string und die darunter liegende Schicht eine char* nimmt, kann es einen Code geben, der die Umwandlung in std::string umkehrt:

void HighLevelFunc(std::string s) {
    LowLevelFunc(s.c_str());
}

Konvertierung zwischen Zeichenkodierungen

Moderne C++-Programme müssen z. B. einen literalen C-String (ASCII, in vorzeichenbehafteten Bytes) mit einem UTF-8-String (vorzeichenlos, variable Bytes pro Zeichen) von einem Webbrowser vergleichen oder ausgegebene Zeichenketten von einem XML-Parser, der UTF-16-Wortströme (mit oder ohne Endian-Bytes) erzeugt, in UTF-8 konvertieren. Die Anzahl der möglichen Kombinationen ist erschreckend.

Der beste Weg, um Konvertierungen zu vermeiden, ist, ein einziges Format für alle Strings zu wählen und alle Strings in diesem Format zu speichern. Vielleicht möchtest du spezielle Vergleichsfunktionen zwischen deinem gewählten Format und null-terminierten Strings im C-Stil bereitstellen, damit sie nicht konvertiert werden müssen. Ich mag UTF-8, weil es alle Unicode-Codepunkte darstellen kann, direkt mit C-Strings vergleichbar ist (für Gleichheit) und von den meisten Browsern erzeugt wird.

In großen und eilig geschriebenen Programmen kann es vorkommen, dass eine Zeichenkette von einem ursprünglichen Format in ein neues Format umgewandelt wird und dann wieder in ihr ursprüngliches Format zurückkehrt, während sie die verschiedenen Ebenen der Software durchläuft. Die Lösung für dieses Problem besteht darin, die Mitgliedsfunktionen an den Klassenschnittstellen so umzuschreiben, dass sie denselben Typ von Zeichenketten akzeptieren. Leider ist diese Aufgabe so, als würde man einem C++-Programm const-korrektheit hinzufügen. Die Änderung wirkt sich auf das gesamte Programm aus, so dass es schwierig ist, den Umfang der Änderung zu kontrollieren.

Zusammenfassung

  • Strings sind teuer, weil sie dynamisch zugewiesen werden, sich wie Werte in Ausdrücken verhalten und ihre Implementierung viel Kopierarbeit erfordert.

  • Die Behandlung von Strings als Objekte anstelle von Werten reduziert die Häufigkeit der Zuweisung und des Kopierens.

  • Das Reservieren von Platz in einem String reduziert den Overhead bei der Zuweisung.

  • Die Übergabe einer const Referenz auf eine Zeichenkette an eine Funktion ist fast dasselbe wie die Übergabe des Wertes, kann aber effizienter sein.

  • Die Übergabe einer Ergebniszeichenkette aus einer Funktion als Referenz verwendet die Speicherung des eigentlichen Arguments wieder, was potenziell effizienter ist als die Zuweisung von neuem Speicher.

  • Eine Optimierung, die nur manchmal den Zuweisungs-Overhead beseitigt, ist immer noch eine Optimierung.

  • Manchmal ist ein anderer Algorithmus einfacher zu optimieren oder von Natur aus effizienter.

  • Die Klassenimplementierungen der Standardbibliothek sind universell einsetzbar und einfach. Sie sind nicht unbedingt leistungsfähig oder optimal für einen bestimmten Zweck.

Get Optimiertes C++ now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial