Zero-Copy In-Place String-Splitting in C

Nehmen wir an, du hast einen String:

split_examples.cpp

char* s = "1,23,456,7890";

char* s = "1,23,456,7890";

Du möchtest diesen String bei jedem Komma splitten, um seine Teile als C-Strings zu erhalten (wobei die Anzahl der Teile variabel ist):

boost_split_example.cpp

char* s1 = "1";
char* s2 = "23";
char* s3 = "456";
char* s4 = "7890";

char* s1 = "1";
char* s2 = "23";
char* s3 = "456";
char* s4 = "7890";

Boost

Eine einfache Strategie ist die Verwendung von boost::algorithm::split wie\u0000this:

boost_split_snippet.cpp

std::vector<std::string> strs;
boost::split(strs, s, boost::is_any_of(","));

std::vector<std::string> strs;
boost::split(strs, s, boost::is_any_of(","));

Vollständiges Beispiel

Obwohl einfach, hat dieser Ansatz schwerwiegende Nachteile. Er ist nicht nur nur in C++ verfügbar, sondern erhöht auch erheblich die Kompilierzeit und Binärgröße durch das Einbinden eines großen Teils der Boost-Bibliothek, obwohl boost::algorithm eine reine Header-Only-Bibliothek ist.

Wichtiger noch ist, besonders für Embedded- und Industriepysteme, dass er viele Zwischenobjekte erzeugt: Mehrere Kopien jedes Teils des Strings plus std::string-Metadaten, den std::vector<std::string>. Während dies manchmal akzeptabel oder sogar aus verschiedenen Gründen gewünscht ist, ist es hinsichtlich CPU- und Speichernutzung schrecklich ineffizient.

Außerdem führen selbst einfachste Fehler wie das Vertauschen der ersten beiden Argumente: boost::split(s, strs, boost::is_any_of(",")) zu einer grauenhaften Liste von Fehlermeldungen, die selbst für erfahrene Entwickler schwer zu verstehen sind.

In-Place-Strategien

Schauen wir uns effizientere Strategien an. Beachte, dass s oben den Typ char* hat (im Gegensatz zu const char*).

Dies bedeutet, dass wir den Inhalt des Strings modifizieren können, z.B. um die Effizienz unserer Algorithmen zu verbessern. In vielen Fällen müssen wir den String (oder Teile davon) nicht kopieren, um ihn zu verarbeiten.

Algorithmen, die diese Strategie verwenden, werden In-Place-Algorithmen genannt. Sei dir bewusst, dass bei Verwendung solcher Algorithmen der String durch starke Modifikation wahrscheinlich zerstört wird und daher für andere Algorithmen unbrauchbar sein kann. Die unsachgemäße Verwendung von In-Place-Algorithmen hat in der Vergangenheit oft zu Sicherheitsproblemen und Bugs geführt.

Zero-Copy-Algorithmen

Bevor wir uns einen effizienten Splitting-Algorithmus ansehen, müssen wir uns eine weitere vorteilhafte Eigenschaft eines Algorithmus ansehen

Erinnerst du dich, als wir definiert haben

pointer_example.c

char* s3 = "456";

char* s3 = "456";

Hier zeigt s3 auf den String "456" — jedoch ist dieses "456" nicht identisch mit dem 456 in unserem ursprünglichen String:

count_delimiters.cpp

//              |||
char* s = "1,23,456,7890";

//              |||
char* s = "1,23,456,7890";

Während beide die gleichen drei Zeichen enthalten, wird "456" mehrfach im Speicher abgelegt — verschwendet also Speicher.

Während 3 Bytes verschwendeter Speicher nicht viel ist, führen viele reale Anwendungsfälle zu hunderten Kilobytes bis Gigabytes verschwendeten Speicherplatz, weil derselbe String mehrfach gespeichert wird. Dies ist noch schwerwiegender in Embedded-Anwendungen, wo Speicher knapp ist.

Zero-Copy-Algorithmen vermeiden dieses Effizienzproblem, indem sie das Kopieren von Speicher vermeiden, es sei denn, es ist absolut notwendig. Da sie oft komplizierter sind als ihre klassischen Gegenstücke, werden sie meistens in Anwendungen eingesetzt, bei denen Effizienz und Latenz wichtig sind, wie Netzwerk-Stacks und wissenschaftliche Software.

Zero-Copy In-Place String-Splitting

Hier ist die grundlegende Idee: Unsere Voraussetzung ist, dass C-Strings durch NUL-Zeichen begrenzt sind (d.h. sie enden beim ersten NUL-Zeichen).

Wir können einen Zero-Copy-Algorithmus erstellen, indem wir s3 auf die "456"-Instanz innerhalb von s mittels Zeigerarithmetik zeigen lassen.

split_result_example.c

char* s3 = s + 5;

char* s3 = s + 5;

Wenn wir jedoch s3 ausgeben:

split_zero_copy_impl.c

printf("%s", s3)

printf("%s", s3)

erhalten wir 456,7890 statt 456. Dies liegt daran, dass das erste NUL-Zeichen nach s + 5 nicht am Ende von 456 steht, sondern am Ende von s.

Wir können dieses Problem lösen, indem wir einen In-Place-Algorithmus verwenden, um jedes Vorkommen unseres Delimiters (,) durch ein NUL-Zeichen zu ersetzen, was dazu führt, dass s äquivalent ist\u0000to

split_example_escaped.cpp

char* s = "1\023\0456\07890";

char* s = "1\023\0456\07890";

Durch Definieren von s3 wie zuvor:

split_pointer_example.c

char* s3 = s + 5;

char* s3 = s + 5;

können wir sehen, dass das erste NUL-Zeichen nach s + 5 genau am Ende von "456" steht.

Aber wir haben auch gesagt, dass die Anzahl der Teile variabel ist — wie können wir also das Ergebnis einer Split-Operation in einem C-Datentyp darstellen (d.h. ein grobes Äquivalent zum C++ std::vector).

std::vector-Instanzen werden durch einfaches Neuzuordnen eines größeren Speicher-Arrays angepasst — dies ist unglaublich bequem, aber auch ineffizient aus Gründen, die über den Rahmen dieses Artikels hinausgehen.

Beim Schreiben von effizientem C können wir es nicht so bequem machen. Unser Ergebnis hat den Typ char**: Es enthält eine Liste von char*, von denen jeder auf einen Abschnitt des ursprünglichen Strings zeigt. Die Anzahl der Elemente in dieser Liste wird in einer separaten Variable gespeichert.

Um aber die richtige Größe des char** zu allozieren, müssen wir zuerst die Anzahl der Delimiter zählen

count_delimiters.cpp

int numDelimiters = 0;
char* pos = s;
while(*pos++ != '\0') { //Until the end of the string
    if(*pos == ',') {
        numDelimiters++;
    }
}

int numDelimiters = 0;
char* pos = s;
while(*pos++ != '\0') { //Until the end of the string
    if(*pos == ',') {
        numDelimiters++;
    }
}

Mit dieser Information wissen wir genau, wie viele Elemente wir benötigen — daher können wir das Array allozieren

allocate_split_result.c

char** splitResult = (char**)malloc((numDelimiters + 1) * sizeof(char*));

char** splitResult = (char**)malloc((numDelimiters + 1) * sizeof(char*));

Aufgrund der Zero-Copy-Natur unseres Algorithmus ist dies der einzige Speicher (neben s), den wir benötigen!

Beachte, dass C keine automatische Heap-Verwaltung hat und du daher free(splitResult) aufrufen musst, sobald du damit fertig bist.

Nun können wir den letzten (aber schwierigsten) Teil implementieren: Delimiter durch NUL-Zeichen ersetzen und den richtigen Startindex für jeden Treffer finden — alles in einem Durchgang.

Eine wichtige Teilaufgabe ist es, ein Vorkommen des Delimiter-Zeichens in s oder einem Suffix davon zu finden. Glücklicherweise gibt es dafür eine Standard-C-Bibliotheksfunktion: strchr.

split_loop.c

//Erste Teilzeichenkette beginnt am Anfang von s
splitResult[0] = s;
//Weitere Teilzeichenketten finden
int i = 1;
char* hit = s;
while((hit = strchr(hit, ',')) != NULL) { //Nächsten Delimiter finden
    //In-Place-Ersetzung des Delimiters
    *hit++ = '\0';
    //Nächste Teilzeichenkette beginnt direkt nach dem Treffer
    splitResult[i++] = hit;
}

//Erste Teilzeichenkette beginnt am Anfang von s
splitResult[0] = s;
//Weitere Teilzeichenketten finden
int i = 1;
char* hit = s;
while((hit = strchr(hit, ',')) != NULL) { //Nächsten Delimiter finden
    //In-Place-Ersetzung des Delimiters
    *hit++ = '\0';
    //Nächste Teilzeichenkette beginnt direkt nach dem Treffer
    splitResult[i++] = hit;
}

Nun können wir all diesen Code in ein paar Funktionen packen:

split_functions.c

/**
 * Zählt die Anzahl der Vorkommen von c in s
 */
int countChar(const char* s, char c) {
    int n = 0;
    while(*s++ != '\0') { //Until the end of the string
        if(*s == c) {
            n++;
        }
    }
    return n;
}

/**
 * Splittet den String bei Delimitern mit einem Zero-Copy-In-Place-Algorithmus
 * @param s Der zu splittende String (jeder Delimiter wird durch NUL ersetzt)
 * @param delimiter Das Delimiter-Zeichen, bei dem gesplittet wird
 * @param size Die Größe des Rückgabe-Arrays w
 * @return Eine Liste von char* (Größe gespeichert in *size), die auf alle Split-Ergebnisse in Reihenfolge zeigt
 */
char** splitZeroCopyInPlace(char* s, char delimiter, int* size) {
    int numDelimiters = countChar(s, delimiter);
    //Speicher allozieren
    char** splitResult = (char**)malloc((numDelimiters + 1) * sizeof(char*));

    //Erste Teilzeichenkette beginnt am Anfang von s
    splitResult[0] = s;
    //Weitere Teilzeichenketten finden
    int i = 1;
    char* hit = s;
    while((hit = strchr(hit, ',')) != NULL) { //Nächsten Delimiter finden
        //In-Place-Ersetzung des Delimiters
        *hit++ = '\0';
        //Nächste Teilzeichenkette beginnt direkt nach dem Treffer
        splitResult[i++] = hit;
    }
    *size = numDelimiters + 1;
    return splitResult;
}

/**
 * Zählt die Anzahl der Vorkommen von c in s
 */
int countChar(const char* s, char c) {
    int n = 0;
    while(*s++ != '\0') { //Until the end of the string
        if(*s == c) {
            n++;
        }
    }
    return n;
}

/**
 * Splittet den String bei Delimitern mit einem Zero-Copy-In-Place-Algorithmus
 * @param s Der zu splittende String (jeder Delimiter wird durch NUL ersetzt)
 * @param delimiter Das Delimiter-Zeichen, bei dem gesplittet wird
 * @param size Die Größe des Rückgabe-Arrays w
 * @return Eine Liste von char* (Größe gespeichert in *size), die auf alle Split-Ergebnisse in Reihenfolge zeigt
 */
char** splitZeroCopyInPlace(char* s, char delimiter, int* size) {
    int numDelimiters = countChar(s, delimiter);
    //Speicher allozieren
    char** splitResult = (char**)malloc((numDelimiters + 1) * sizeof(char*));

    //Erste Teilzeichenkette beginnt am Anfang von s
    splitResult[0] = s;
    //Weitere Teilzeichenketten finden
    int i = 1;
    char* hit = s;
    while((hit = strchr(hit, ',')) != NULL) { //Nächsten Delimiter finden
        //In-Place-Ersetzung des Delimiters
        *hit++ = '\0';
        //Nächste Teilzeichenkette beginnt direkt nach dem Treffer
        splitResult[i++] = hit;
    }
    *size = numDelimiters + 1;
    return splitResult;
}

Siehe das vollständige Beispiel für Verwendungshinweise.

Was ist mit strtok()

Es gibt tatsächlich eine Standard-C-Bibliotheksfunktion, die unserem Algorithmus bemerkenswert ähnlich ist: strtok(). Sie verwendet ebenfalls einen In-Place-Ansatz (der ursprüngliche String wird modifiziert).

Ein bemerkenswerter Unterschied ist, dass strtok() das Splitten an mehreren Delimiter-Zeichen unterstützt, z.B. , und ;. Je nach Implementierung kann dies etwas langsamer sein als unser maßgeschneiderter Algorithmus oben.

Jedoch ist strtok() nicht ohne Risiken: Sie ist nicht Thread-sicher. Es gibt eine nur-POSIX-Version (im Gegensatz zum C-Standard) namens strtok_r(), die ihren Zustand in einem benutzerdefinierten Zeiger speichert.

Es gibt eine weitere Einschränkung. Zitiert aus der Manpage:

strtok_behavior.txt

A sequence of two or more contiguous delimiter bytes
in the parsed string is considered to be a single delimiter.

A sequence of two or more contiguous delimiter bytes
in the parsed string is considered to be a single delimiter.

Diese Eigenschaft wird Token-Kompression genannt. Oft ist sie gewünscht — aber in vielen realen Anwendungsfällen ist sie ein großes Problem für einige Randfälle und könnte schwer zu erkennen sein, sobald eingesetzt.

Betrachte die folgenden CSV-Strings (mit dem Ergebnis unseres obigen Algorithmus im Kommentar):

strtok_examples.c

const char* a = "1,,2,3,4"; // ["1","","2","3","4"]
const char* b = "1,2,,3,4"; // ["1","2","","3","4"]

const char* a = "1,,2,3,4"; // ["1","","2","3","4"]
const char* b = "1,2,,3,4"; // ["1","2","","3","4"]

Mit strtok() (und strtok_r()) liefern a und b genau das gleiche Ergebnis:

strtok_result.c

["1","2","","3","4"]

["1","2","","3","4"]

Darüber hinaus werden Delimiter am Anfang und am Ende des Strings ignoriert. Ein Beispiel, wo dies ein Problem sein könnte:

strtok_edge_cases.c

const char* a = ",1,2,3,4"; // ["","1","2","3","4"]
const char* b = "1,2,3,4,"; // ["1","2","3","4",""]

const char* a = ",1,2,3,4"; // ["","1","2","3","4"]
const char* b = "1,2,3,4,"; // ["1","2","3","4",""]

Das Ergebnis für beide Varianten mit strtok() ist

strtok_edge_result.c

["1","2","3","4"]

["1","2","3","4"]

Zusammenfassend hat strtok() Anwendungsfälle — für einige davon ist unser Algorithmus nicht geeignet — aber sie kommt nicht ohne wesentliche Einschränkungen, deren sich der Benutzer bewusst sein muss.

Check out similar posts by category: C/C++

If this post helped you, please consider buying me a coffee or donating via PayPal to support research & publishing of new posts on TechOverflow

Buy me a coffee