Den Garbage Collector eliminieren: Der RAII-Weg

Am Anfang war C. In C gibt es drei Arten der Speicherzuweisung: statisch, automatisch und dynamisch. Statische Variablen sind die in die Quelldatei eingebetteten Konstanten, und da sie bekannte Größen haben und sich nie ändern, sind sie nicht besonders interessant. Die automatische Zuweisung kann als Stapelzuweisung betrachtet werden – Platz wird zugewiesen, wenn ein lexikalischer Block betreten wird, und freigegeben, wenn dieser Block verlassen wird. Seine wichtigste Eigenschaft hängt direkt damit zusammen. Bis C99 mussten automatisch zugewiesene Variablen ihre Größe zur Kompilierzeit kennen. Das bedeutet, dass alle Strings, Listen, Maps und alle davon abgeleiteten Strukturen auf dem Heap im dynamischen Speicher leben mussten.

Dynamischer Speicher wurde explizit vom Programmierer mithilfe von vier grundlegenden Operationen zugewiesen und freigegeben: malloc, realloc, calloc und free. Die ersten beiden davon führen überhaupt keine Initialisierung durch, der Speicher kann Cruft enthalten. Alle außer kostenlos können fehlschlagen. In diesem Fall geben sie einen Nullzeiger zurück, dessen Zugriff undefiniertes Verhalten ist; Im besten Fall explodiert Ihr Programm. Im schlimmsten Fall scheint Ihr Programm eine Weile zu arbeiten und Datenmüll zu verarbeiten, bevor es explodiert.

Es ist ziemlich schmerzhaft, Dinge auf diese Weise zu tun, weil Sie, der Programmierer, die alleinige Verantwortung dafür tragen, eine Reihe von Invarianten aufrechtzuerhalten, die dazu führen, dass Ihr Programm explodiert, wenn sie verletzt werden. Es muss ein malloc-Aufruf erfolgen, bevor überhaupt auf die Variable zugegriffen wird. Sie müssen überprüfen, ob malloc erfolgreich zurückgegeben wurde, bevor Sie Ihre Variable verwenden. Es muss genau ein freier Aufruf pro malloc im Ausführungspfad existieren. Wenn null, Speicherlecks. Wenn mehr als einer, explodiert Ihr Programm. Es dürfen keine Zugriffsversuche auf die Variable erfolgen, nachdem sie freigegeben wurde. Sehen wir uns ein Beispiel an, wie das tatsächlich aussieht:

 int main() { char *str = (char *) malloc(7); strcpy(str, "toptal"); printf("char array = \"%s\" @ %u\n", str, str); str = (char *) realloc(str, 11); strcat(str, ".com"); printf("char array = \"%s\" @ %u\n", str, str); free(str); return(0); }

 $ make runc gcc -oc cc ./c char * (null terminated): toptal @ 66576 char * (null terminated): toptal.com @ 66576

Dieser Code, so einfach er auch ist, enthält bereits ein Antimuster und eine fragwürdige Entscheidung. Im wirklichen Leben sollten Sie Bytezahlen niemals als Literale ausschreiben, sondern stattdessen die Funktion sizeof verwenden. In ähnlicher Weise weisen wir das char * -Array genau der Größe des Strings zu, den wir zweimal benötigen (eins mehr als die Länge des Strings, um die Nullterminierung zu berücksichtigen), was eine ziemlich teure Operation ist. Ein ausgeklügelteres Programm könnte einen größeren String-Puffer konstruieren, wodurch die String-Größe wachsen kann.

Die Erfindung von RAII: Eine neue Hoffnung

All diese manuelle Verwaltung war, gelinde gesagt, unangenehm. Mitte der 80er Jahre erfand Bjarne Stroustrup ein neues Paradigma für seine brandneue Sprache C++. Er nannte es „Resource Acquisition Is Initialization“, und die grundlegenden Erkenntnisse waren die folgenden: Objekte können so spezifiziert werden, dass sie Konstruktoren und Destruktoren haben, die automatisch zu geeigneten Zeiten vom Compiler aufgerufen werden. Dies bietet eine viel bequemere Möglichkeit, den Speicher eines bestimmten Objekts zu verwalten erfordert, und die Technik ist auch für Ressourcen nützlich, die kein Speicher sind.

Das bedeutet, dass das obige Beispiel in C++ viel sauberer ist:

 int main() { std::string str = std::string ("toptal"); std::cout << "string object: " << str << " @ " << &str << "\n"; str += ".com"; std::cout << "string object: " << str << " @ " << &str << "\n"; return(0); }

 $ g++ -o ex_1 ex_1.cpp && ./ex_1 string object: toptal @ 0x5fcaf0 string object: toptal.com @ 0x5fcaf0

Keine manuelle Speicherverwaltung in Sicht! Das String-Objekt wird konstruiert, hat eine überladene Methode, die aufgerufen wird, und wird automatisch zerstört, wenn die Funktion beendet wird. Leider kann diese Einfachheit zu anderen Komplikationen führen. Schauen wir uns ein Beispiel etwas genauer an:

 vector<string> read_lines_from_file(string &file_name) { vector<string> lines; string line; ifstream file_handle (file_name.c_str()); while (file_handle.good() && !file_handle.eof()) { getline(file_handle, line); lines.push_back(line); } file_handle.close(); return lines; } int main(int argc, char* argv[]) { // get file name from the first argument string file_name (argv[1]); int count = read_lines_from_file(file_name).size(); cout << "File " << file_name << " contains " << count << " lines."; return 0; }

 $ make cpp && ./c++ makefile g++ -o c++ c++.cpp File makefile contains 38 lines.

Das scheint alles ziemlich einfach zu sein. Die Vektorlinien werden aufgefüllt, zurückgegeben und aufgerufen. Als effiziente Programmierer, die Wert auf Performance legen, stört uns jedoch etwas daran: In der return-Anweisung wird der Vektor aufgrund der Wertesemantik kurz vor seiner Zerstörung in einen neuen Vektor kopiert.

Bei großen Datenmengen kann das teuer werden. Lassen Sie uns dies optimieren und einfach einen Zeiger zurückgeben. Es gibt ein paar Syntaxänderungen, aber ansonsten ist es derselbe Code:

 vector<string> * read_lines_from_file(string &file_name) { vector<string> * lines; string line; ifstream file_handle (file_name.c_str()); while (file_handle.good() && !file_handle.eof()) { getline(file_handle, line); lines->push_back(line); } file_handle.close(); return lines; }

 $ make cpp && ./c++ makefile g++ -o c++ c++.cpp Segmentation fault (core dumped)

Autsch! Jetzt, da lines ein Zeiger ist, können wir sehen, dass automatische Variablen wie angekündigt funktionieren: Der Vektor wird zerstört, wenn sein Gültigkeitsbereich verlassen wird, wodurch der Zeiger auf eine Vorwärtsposition im Stapel zeigt. Ein Segmentierungsfehler ist einfach ein versuchter Zugriff auf illegalen Speicher, und damit hätten wir wirklich rechnen müssen. Trotzdem wollen wir die Zeilen der Datei irgendwie von unserer Funktion zurückbekommen, und das Natürliche ist, unsere Variable einfach aus dem Stack und in den Heap zu verschieben. Dies geschieht mit dem Schlüsselwort new. Wir können einfach eine Zeile unserer Datei bearbeiten, in der wir Zeilen definieren:

 vector<string> * lines = new vector<string>;

 $ make cpp && ./c++ makefile g++ -o c++ c++.cpp File makefile contains 38 lines.

Obwohl dies perfekt zu funktionieren scheint, hat es leider immer noch einen Fehler: Es verliert Speicher. In C++ müssen Zeiger auf den Heap manuell gelöscht werden, wenn sie nicht mehr benötigt werden; Wenn nicht, wird dieser Speicher nicht mehr verfügbar, sobald der letzte Zeiger aus dem Gültigkeitsbereich fällt, und wird nicht wiederhergestellt, bis das Betriebssystem ihn verwaltet, wenn der Prozess endet. Idiomatisches modernes C++ würde hier einen unique_ptr verwenden, der das gewünschte Verhalten umsetzt. Es löscht das Objekt, auf das gezeigt wird, wenn der Zeiger den Gültigkeitsbereich verlässt. Dieses Verhalten war jedoch bis C++11 nicht Teil der Sprache.

In diesem Beispiel kann dies leicht behoben werden:

 vector<string> * read_lines_from_file(string &file_name) { vector<string> * lines = new vector<string>; string line; ifstream file_handle (file_name.c_str()); while (file_handle.good() && !file_handle.eof()) { getline(file_handle, line); lines->push_back(line); } file_handle.close(); return lines; } int main(int argc, char* argv[]) { // get file name from the first argument string file_name (argv[1]); vector<string> * file_lines = read_lines_from_file(file_name); int count = file_lines->size(); delete file_lines; cout << "File " << file_name << " contains " << count << " lines."; return 0; }

Da Programme über den Spielzeugmaßstab hinaus expandieren, wird es unglücklicherweise schnell schwieriger, darüber nachzudenken, wo und wann genau ein Zeiger gelöscht werden sollte. Wenn eine Funktion einen Zeiger zurückgibt, besitzen Sie ihn jetzt? Sollten Sie es selbst löschen, wenn Sie damit fertig sind, oder gehört es zu einer Datenstruktur, die später alle auf einmal freigegeben werden? Machen Sie es auf eine Weise falsch und Speicherlecks, machen Sie es auf der anderen falsch und Sie haben die fragliche Datenstruktur und wahrscheinlich andere beschädigt, da sie versuchen, Zeiger zu dereferenzieren, die jetzt nicht mehr gültig sind.

„In den Garbage Collector, Flyboy!“

Garbage Collectors sind keine neue Technologie. Sie wurden 1959 von John McCarthy für Lisp erfunden. Mit Smalltalk-80 im Jahr 1980 begann Garbage Collection in den Mainstream zu kommen. Die wahre Blüte der Technik stellten jedoch die 1990er Jahre dar: Zwischen 1990 und 2000 wurde eine große Anzahl von Sprachen veröffentlicht, die alle auf die eine oder andere Weise Garbage Collection verwendeten: Haskell, Python, Lua, Java, JavaScript, Ruby, OCaml , und C# gehören zu den bekanntesten.

Was ist Garbage Collection? Kurz gesagt, es handelt sich um eine Reihe von Techniken, die verwendet werden, um die manuelle Speicherverwaltung zu automatisieren. Es ist oft als Bibliothek für Sprachen mit manueller Speicherverwaltung wie C und C++ verfügbar, wird aber viel häufiger in Sprachen verwendet, die dies erfordern. Der große Vorteil ist, dass der Programmierer einfach nicht über Speicher nachdenken muss; es ist alles abstrahiert. Das Python-Äquivalent zu unserem obigen Code zum Lesen von Dateien lautet beispielsweise einfach so:

 def read_lines_from_file(file_name): lines = [] with open(file_name) as fp: for line in fp: lines.append(line) return lines if __name__ == '__main__': import sys file_name = sys.argv[1] count = len(read_lines_from_file(file_name)) print("File {} contains {} lines.".format(file_name, count))

 $ python3 python3.py makefile File makefile contains 38 lines.

Das Array von Zeilen entsteht, wenn es zum ersten Mal zugewiesen wird, und wird zurückgegeben, ohne es in den aufrufenden Bereich zu kopieren. Es wird vom Garbage Collector irgendwann bereinigt, nachdem es aus diesem Bereich herausgefallen ist, da das Timing unbestimmt ist. Ein interessanter Hinweis ist, dass RAII für Nicht-Speicherressourcen in Python nicht idiomatisch ist. Es ist erlaubt – wir hätten einfach fp = open(file_name) , anstatt einen with -Block zu verwenden, und den GC danach bereinigen lassen. Das empfohlene Muster besteht jedoch darin, nach Möglichkeit einen Kontextmanager zu verwenden, damit sie zu deterministischen Zeiten freigegeben werden können.

So schön es auch ist, die Speicherverwaltung zu abstrahieren, es entstehen Kosten. Bei der Garbage Collection mit Verweiszählung fallen für alle Variablenzuweisungen und Bereichsausgänge geringe Kosten für die Aktualisierung der Verweise an. In Mark-and-Sweep-Systemen wird in unvorhersehbaren Intervallen die gesamte Programmausführung angehalten, während der GC den Speicher bereinigt. Dies wird oft als Stop-the-World-Ereignis bezeichnet. Implementierungen wie Python, die beide Systeme verwenden, leiden unter beiden Nachteilen. Diese Probleme verringern die Eignung von Garbage Collection-Sprachen für Fälle, in denen die Leistung kritisch ist oder Echtzeitanwendungen erforderlich sind. Man kann die Leistungseinbuße sogar bei diesen Spielzeugprogrammen in Aktion sehen:

 $ make cpp && time ./c++ makefile g++ -o c++ c++.cpp File makefile contains 38 lines. real 0m0.016s user 0m0.000s sys 0m0.015s $ time python3 python3.py makefile File makefile contains 38 lines. real 0m0.041s user 0m0.015s sys 0m0.015s

Die Python-Version benötigt fast dreimal so viel Echtzeit wie die C++-Version. Obwohl nicht alle dieser Unterschiede der Garbage Collection zugeschrieben werden können, sind sie dennoch beträchtlich.

Eigentum: RAII erwacht

Ist das dann das Ende? Müssen sich alle Programmiersprachen zwischen Performance und einfacher Programmierung entscheiden? Nein! Die Erforschung von Programmiersprachen geht weiter, und wir beginnen, die ersten Implementierungen der nächsten Generation von Sprachparadigmen zu sehen. Von besonderem Interesse ist die Sprache namens Rust, die Python-ähnliche Ergonomie und C-ähnliche Geschwindigkeit verspricht, während sie baumelnde Zeiger, Nullzeiger und dergleichen unmöglich macht - sie werden nicht kompiliert. Wie kann es diese Behauptungen aufstellen?

Die Kerntechnologie, die diese beeindruckenden Behauptungen zulässt, heißt Borrow Checker, ein statischer Checker, der bei der Kompilierung ausgeführt wird und Code ablehnt, der diese Probleme verursachen könnte. Bevor wir jedoch zu tief in die Implikationen einsteigen, müssen wir über die Voraussetzungen sprechen.

Eigentum

Erinnern Sie sich, dass wir in unserer Diskussion über Zeiger in C++ den Begriff des Eigentums berührt haben, was grob gesagt bedeutet, „wer ist für das Löschen dieser Variablen verantwortlich“. Rust formalisiert und stärkt dieses Konzept. Jede Variablenbindung hat das Eigentum an der Ressource, die sie bindet, und der Borrow-Checker stellt sicher, dass es genau eine Bindung gibt, die das Gesamteigentum an der Ressource hat. Das heißt, der folgende Ausschnitt aus dem Rust Book wird nicht kompiliert:

 let v = vec![1, 2, 3]; let v2 = v; println!("v[0] is: {}", v[0]);

 error: use of moved value: `v` println!("v[0] is: {}", v[0]); ^

Zuweisungen in Rust haben standardmäßig Move-Semantik – sie übertragen den Besitz. Es ist möglich, einem Typ Kopiersemantik zu geben, und dies wird bereits für numerische Primitive getan, aber es ist ungewöhnlich. Aus diesem Grund besitzt v2 ab der dritten Codezeile den betreffenden Vektor und es kann nicht mehr als v darauf zugegriffen werden. Warum ist das nützlich? Wenn jede Ressource genau einen Besitzer hat, gibt es auch einen einzigen Moment, an dem sie aus dem Geltungsbereich fällt, was zur Kompilierzeit bestimmt werden kann. Dies bedeutet wiederum, dass Rust das Versprechen von RAII einlösen kann, Ressourcen deterministisch basierend auf ihrem Umfang zu initialisieren und zu zerstören, ohne jemals einen Garbage Collector zu verwenden oder den Programmierer zu verpflichten, irgendetwas manuell freizugeben.

Vergleichen Sie dies mit der Garbage Collection mit Referenzzählung. In einer RC-Implementierung haben alle Zeiger mindestens zwei Informationen: das Objekt, auf das gezeigt wird, und die Anzahl der Verweise auf dieses Objekt. Das Objekt wird zerstört, wenn dieser Zählwert 0 erreicht. Dies verdoppelt den Speicherbedarf des Zeigers und fügt seiner Verwendung geringfügige Kosten hinzu, da der Zählwert automatisch inkrementiert, dekrementiert und überprüft wird. Das Ownership-System von Rust bietet die gleiche Garantie, dass Objekte automatisch zerstört werden, wenn ihnen die Referenzen ausgehen, aber es tut dies ohne Laufzeitkosten. Der Besitz jedes Objekts wird analysiert und die Zerstörungsaufrufe werden zur Kompilierzeit eingefügt.

Ausleihen

Wenn Bewegungssemantik die einzige Möglichkeit wäre, Daten zu übergeben, würden Funktionsrückgabetypen sehr schnell sehr kompliziert werden. Wenn Sie eine Funktion schreiben wollten, die zwei Vektoren verwendet, um eine Ganzzahl zu erzeugen, die die Vektoren anschließend nicht zerstört, müssen Sie sie in den Rückgabewert aufnehmen. Obwohl das technisch möglich ist, ist es schrecklich zu verwenden:

 fn foo(v1: Vec<i32>, v2: Vec<i32>) -> (Vec<i32>, Vec<i32>, i32) { // do stuff with v1 and v2 // hand back ownership, and the result of our function (v1, v2, 42) } let v1 = vec![1, 2, 3]; let v2 = vec![1, 2, 3]; let (v1, v2, answer) = foo(v1, v2);

Stattdessen hat Rust das Konzept des Ausleihens. Sie können die gleiche Funktion so schreiben, und sie wird die Referenz auf die Vektoren ausleihen und sie dem Eigentümer zurückgeben, wenn die Funktion endet:

 fn foo(v1: &Vec<i32>, v2: &Vec<i32>) -> i32 { // do stuff 42 } let v1 = vec![1, 2, 3]; let v2 = vec![1, 2, 3]; let answer = foo(&v1, &v2);

v1 und v2 geben ihren Besitz an den ursprünglichen Bereich zurück, nachdem fn foo zurückgekehrt ist, fallen aus dem Bereich und werden automatisch zerstört, wenn der enthaltende Bereich beendet wird.

Es ist hier erwähnenswert, dass es Einschränkungen beim Ausleihen gibt, die vom Borrow-Checker zur Kompilierzeit durchgesetzt werden, was das Rust Book sehr prägnant formuliert:

Jede Leihe muss für einen Umfang reichen, der nicht größer ist als der des Eigentümers. Zweitens haben Sie möglicherweise die eine oder andere dieser beiden Arten von Ausleihen, aber nicht beide gleichzeitig:

eine oder mehrere Referenzen (&T) auf eine Ressource

genau eine veränderliche Referenz (&mut T)

Dies ist bemerkenswert, da es einen kritischen Aspekt von Rusts Schutz gegen Data Races darstellt. Indem mehrere änderbare Zugriffe auf eine bestimmte Ressource zur Kompilierzeit verhindert werden, wird sichergestellt, dass kein Code geschrieben werden kann, dessen Ergebnis unbestimmt ist, da es davon abhängt, welcher Thread zuerst bei der Ressource angekommen ist. Dies verhindert Probleme wie die Invalidierung des Iterators und die Verwendung nach dem Kostenlos.

Der Borrow Checker in der Praxis

Nachdem wir nun einige der Funktionen von Rust kennen, schauen wir uns an, wie wir denselben Dateizeilenzähler implementieren, den wir zuvor gesehen haben:

 fn read_lines_from_file(file_name: &str) -> io::Result<Vec<String>> { // variables in Rust are immutable by default. The mut keyword allows them to be mutated. let mut lines = Vec::new(); let mut buffer = String::new(); if let Ok(mut fp) = OpenOptions::new().read(true).open(file_name) { // We enter this block only if the file was successfully opened. // This is one way to unwrap the Result<T, E> type Rust uses instead of exceptions. // fp.read_to_string can return an Err. The try! macro passes such errors // upwards through the call stack, or continues otherwise. try!(fp.read_to_string(&mut buffer)); lines = buffer.split("\n").map(|s| s.to_string()).collect(); } Ok(lines) } fn main() { // Get file name from the first argument. // Note that args().nth() produces an Option<T>. To get at the actual argument, we use // the .expect() function, which panics with the given message if nth() returned None, // indicating that there weren't at least that many arguments. Contrast with C++, which // segfaults when there aren't enough arguments, or Python, which raises an IndexError. // In Rust, error cases *must* be accounted for. let file_name = env::args().nth(1).expect("This program requires at least one argument!"); if let Ok(file_lines) = read_lines_from_file(&file_name) { println!("File {} contains {} lines.", file_name, file_lines.len()); } else { // read_lines_from_file returned an error println!("Could not read file {}", file_name); } }

Über die bereits im Quellcode kommentierten Punkte hinaus lohnt es sich, die Lebensdauern der verschiedenen Variablen durchzugehen und zu verfolgen. file_name und file_lines dauern bis zum Ende von main(); Ihre Destruktoren werden zu diesem Zeitpunkt ohne zusätzliche Kosten aufgerufen und verwenden denselben Mechanismus wie die automatischen Variablen von C++. Beim Aufrufen read_lines_from_file wird file_name für seine Dauer unveränderlich an diese Funktion ausgeliehen. Innerhalb read_lines_from_file sich der buffer auf die gleiche Weise und wird zerstört, wenn er außerhalb des Gültigkeitsbereichs liegt. lines hingegen bleibt bestehen und wird erfolgreich an main zurückgegeben. Warum?

Das erste, was zu beachten ist, ist, dass der Rückruf zunächst nicht so aussieht, da Rust eine ausdrucksbasierte Sprache ist. Wenn in der letzten Zeile einer Funktion das abschließende Semikolon weggelassen wird, ist dieser Ausdruck der Rückgabewert. Die zweite Sache ist, dass Rückgabewerte besonders behandelt werden. Es wird davon ausgegangen, dass sie mindestens so lange leben wollen wie der Aufrufer der Funktion. Der letzte Hinweis ist, dass aufgrund der beteiligten Bewegungssemantik kein Kopieren erforderlich ist, um Ok(lines) in Ok(file_lines) , der Compiler lässt die Variable einfach auf das entsprechende Bit des Speichers zeigen.

„Erst am Ende erkennt man die wahre Kraft von RAII.“

Die manuelle Speicherverwaltung ist ein Albtraum, den Programmierer seit der Erfindung des Compilers immer wieder versuchen zu vermeiden. RAII war ein vielversprechendes Muster, aber in C++ verkrüppelt, weil es ohne einige seltsame Problemumgehungen einfach nicht für Heap-zugewiesene Objekte funktionierte. Infolgedessen gab es in den 90er Jahren eine Explosion von müllgesammelten Sprachen, die das Leben des Programmierers auch auf Kosten der Leistung angenehmer machen sollten.

Das ist jedoch nicht das letzte Wort im Sprachdesign. Durch die Verwendung neuer und starker Vorstellungen von Eigentum und Ausleihen gelingt es Rust, die Scope-basierten RAII-Muster mit der Speichersicherheit der Garbage-Collection zu verschmelzen; alles ohne jemals einen Garbage Collector zu benötigen, der die Welt anhält, während Sicherheitsgarantien gegeben werden, die in keiner anderen Sprache zu finden sind. Das ist die Zukunft der Systemprogrammierung. Schließlich gilt: „Irren ist menschlich, aber Compiler vergessen nie.“

Weiterführende Literatur im Toptal Engineering Blog:

• WebAssembly/Rust-Tutorial: Perfekte Audioverarbeitung
• Suche nach Speicherlecks in Java