Éliminer le Garbage Collector : la méthode RAII

Au début, il y avait C. En C, il existe trois types d'allocation de mémoire : statique, automatique et dynamique. Les variables statiques sont les constantes intégrées dans le fichier source, et comme elles ont des tailles connues et ne changent jamais, elles ne sont pas si intéressantes. L'allocation automatique peut être considérée comme une allocation de pile - l'espace est alloué lorsqu'un bloc lexical est entré et libéré lorsque ce bloc est quitté. Sa caractéristique la plus importante est directement liée à cela. Jusqu'à C99, les variables allouées automatiquement devaient avoir leur taille connue au moment de la compilation. Cela signifie que toute chaîne, liste, carte et toute structure dérivée de celles-ci devaient vivre sur le tas, en mémoire dynamique.

La mémoire dynamique était explicitement allouée et libérée par le programmeur à l'aide de quatre opérations fondamentales : malloc, realloc, calloc et free. Les deux premiers d'entre eux n'effectuent aucune initialisation, la mémoire peut contenir des crudités. Tous sauf Free peuvent échouer. Dans ce cas, ils renvoient un pointeur nul, dont l'accès est un comportement indéfini ; dans le meilleur des cas, votre programme explose. Dans le pire des cas, votre programme semble fonctionner pendant un certain temps, traitant les données inutiles avant d'exploser.

Faire les choses de cette façon est un peu pénible parce que vous, le programmeur, êtes seul responsable du maintien d'un tas d'invariants qui font exploser votre programme lorsqu'il est violé. Il doit y avoir un appel malloc avant que la variable soit accessible. Vous devez vérifier que malloc est retourné avec succès avant d'utiliser votre variable. Il doit exister exactement un appel libre par malloc dans le chemin d'exécution. Si zéro, fuite de mémoire. S'il y en a plusieurs, votre programme explose. Il ne peut y avoir aucune tentative d'accès à la variable après sa libération. Voyons un exemple de ce à quoi cela ressemble réellement :

 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

Ce code, aussi simple soit-il, contient déjà un anti-modèle et une décision discutable. Dans la vraie vie, vous ne devriez jamais écrire le nombre d'octets sous forme de littéraux, mais plutôt utiliser la fonction sizeof . De même, nous allouons le tableau char * exactement à la taille de la chaîne dont nous avons besoin deux fois (un de plus que la longueur de la chaîne, pour tenir compte de la terminaison nulle), ce qui est une opération assez coûteuse. Un programme plus sophistiqué peut construire un tampon de chaîne plus grand, permettant à la taille de la chaîne d'augmenter.

L'invention du RAII : un nouvel espoir

Toute cette gestion manuelle était pour le moins désagréable. Au milieu des années 80, Bjarne Stroustrup a inventé un nouveau paradigme pour son tout nouveau langage, le C++. Il l'a appelé Resource Acquisition Is Initialization, et les idées fondamentales étaient les suivantes : les objets peuvent être spécifiés pour avoir des constructeurs et des destructeurs qui sont appelés automatiquement aux moments appropriés par le compilateur, cela fournit un moyen beaucoup plus pratique de gérer la mémoire d'un objet donné nécessite, et la technique est également utile pour les ressources qui ne sont pas de la mémoire.

Cela signifie que l'exemple ci-dessus, en C++, est beaucoup plus propre :

 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

Pas de gestion manuelle de la mémoire en vue ! L'objet chaîne est construit, a une méthode surchargée appelée et est automatiquement détruit lorsque la fonction se termine. Malheureusement, cette même simplicité peut entraîner d'autres complications. Regardons un exemple en détail :

 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.

Tout cela semble assez simple. Les lignes vectorielles sont remplies, renvoyées et appelées. Cependant, étant des programmeurs efficaces soucieux des performances, quelque chose à ce sujet nous dérange : dans l'instruction return, le vecteur est copié dans un nouveau vecteur en raison de la sémantique de valeur en jeu, peu de temps avant sa destruction.

Pour les données volumineuses, cela peut coûter cher. Optimisons cela et renvoyons simplement un pointeur. Il y a quelques changements de syntaxe, mais sinon c'est le même 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)

Aie! Maintenant que lines est un pointeur, nous pouvons voir que les variables automatiques fonctionnent comme annoncé : le vecteur est détruit lorsque sa portée est quittée, laissant le pointeur pointer vers un emplacement en avant dans la pile. Un défaut de segmentation est simplement une tentative d'accès à une mémoire illégale, et nous aurions donc vraiment dû nous y attendre. Pourtant, nous voulons récupérer les lignes du fichier à partir de notre fonction d'une manière ou d'une autre, et la chose naturelle est de simplement déplacer notre variable hors de la pile et dans le tas. Ceci est fait avec le nouveau mot-clé. Nous pouvons simplement éditer une ligne de notre fichier, où nous définissons les lignes :

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

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

Malheureusement, bien que cela semble fonctionner parfaitement, il y a toujours un défaut : il y a une fuite de mémoire. En C++, les pointeurs vers le tas doivent être supprimés manuellement lorsqu'ils ne sont plus nécessaires ; sinon, cette mémoire devient indisponible une fois que le dernier pointeur est hors de portée et n'est pas récupéré tant que le système d'exploitation ne le gère pas à la fin du processus. Le C++ moderne idiomatique utiliserait ici un unique_ptr, qui implémente le comportement souhaité. Il supprime l'objet pointé lorsque le pointeur tombe hors de portée. Cependant, ce comportement ne faisait pas partie du langage avant C++11.

Dans cet exemple, cela peut être facilement corrigé :

 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; }

Malheureusement, à mesure que les programmes s'étendent au-delà de l'échelle des jouets, il devient rapidement plus difficile de déterminer où et quand exactement un pointeur doit être supprimé. Lorsqu'une fonction renvoie un pointeur, le possédez-vous maintenant ? Devez-vous le supprimer vous-même lorsque vous en avez terminé, ou appartient-il à une structure de données qui sera entièrement libérée plus tard ? Vous vous trompez d'une manière et des fuites de mémoire, vous vous trompez de l'autre et vous avez corrompu la structure de données en question et probablement d'autres, car ils tentent de déréférencer des pointeurs qui ne sont plus valides.

"Dans le Garbage Collector, flyboy!"

Les Garbage Collectors ne sont pas une nouvelle technologie. Ils ont été inventés en 1959 par John McCarthy pour Lisp. Avec Smalltalk-80 en 1980, la collecte des ordures a commencé à entrer dans le courant dominant. Cependant, les années 1990 ont représenté le véritable épanouissement de la technique : entre 1990 et 2000, un grand nombre de langages ont été publiés, qui utilisaient tous un ramasse-miettes d'une sorte ou d'une autre : Haskell, Python, Lua, Java, JavaScript, Ruby, OCaml , et C# sont parmi les plus connus.

Qu'est-ce que la collecte des ordures ? En bref, c'est un ensemble de techniques utilisées pour automatiser la gestion manuelle de la mémoire. Il est souvent disponible sous forme de bibliothèque pour les langages à gestion manuelle de la mémoire tels que C et C++, mais il est beaucoup plus couramment utilisé dans les langages qui en ont besoin. Le grand avantage est que le programmeur n'a tout simplement pas besoin de penser à la mémoire ; tout est abstrait. Par exemple, l'équivalent Python de notre code de lecture de fichiers ci-dessus est simplement ceci :

 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.

Le tableau de lignes apparaît lors de sa première affectation et est renvoyé sans copie dans la portée appelante. Il est nettoyé par le Garbage Collector quelque temps après être sorti de cette portée, car le moment est indéterminé. Une remarque intéressante est qu'en Python, RAII pour les ressources non mémoire n'est pas idiomatique. C'est autorisé - nous aurions pu simplement écrire fp = open(file_name) au lieu d'utiliser un bloc with , et laisser le GC nettoyer ensuite. Mais le modèle recommandé est d'utiliser un gestionnaire de contexte lorsque cela est possible afin qu'ils puissent être publiés à des moments déterministes.

Aussi agréable qu'il soit d'abstraire la gestion de la mémoire, il y a un coût. Dans le garbage collection de comptage de références, toutes les sorties d'affectation et de portée de variable gagnent un petit coût pour mettre à jour les références. Dans les systèmes de marquage et de balayage, à des intervalles imprévisibles, toute l'exécution du programme est interrompue pendant que le GC nettoie la mémoire. Ceci est souvent appelé un événement stop-the-world. Les implémentations comme Python, qui utilisent les deux systèmes, souffrent des deux pénalités. Ces problèmes réduisent l'adéquation des langages récupérés par le ramasse-miettes dans les cas où les performances sont critiques ou où des applications en temps réel sont nécessaires. On peut voir la pénalité de performance en action même sur ces programmes jouets :

 $ 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

La version Python prend presque trois fois plus de temps réel que la version C++. Bien que toute cette différence ne puisse pas être attribuée à la collecte des ordures, elle reste considérable.

Propriété : RAII se réveille

C'est la fin, alors ? Tous les langages de programmation doivent-ils choisir entre performance et facilité de programmation ? Non! La recherche sur les langages de programmation se poursuit et nous commençons à voir les premières implémentations de la prochaine génération de paradigmes de langage. Le langage appelé Rust est particulièrement intéressant. Il promet une ergonomie de type Python et une vitesse de type C tout en rendant impossibles les pointeurs suspendus, les pointeurs nuls et autres - ils ne compileront pas. Comment peut-il faire ces revendications?

La technologie de base qui permet ces revendications impressionnantes s'appelle le vérificateur d'emprunt, un vérificateur statique qui s'exécute à la compilation, rejetant le code qui pourrait causer ces problèmes. Cependant, avant d'aller trop loin dans les implications, nous devrons parler des prérequis.

La possession

Rappelez-vous que dans notre discussion sur les pointeurs en C++, nous avons abordé la notion de propriété, qui signifie en gros "qui est responsable de la suppression de cette variable". Rust formalise et renforce ce concept. Chaque liaison de variable est propriétaire de la ressource qu'elle lie, et le vérificateur d'emprunt s'assure qu'il existe exactement une liaison qui détient la propriété globale de la ressource. C'est-à-dire que l'extrait suivant du Rust Book ne sera pas compilé :

 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]); ^

Les affectations dans Rust ont une sémantique de déplacement par défaut - elles transfèrent la propriété. Il est possible de donner une sémantique de copie à un type, et cela se fait déjà pour les primitives numériques, mais c'est inhabituel. De ce fait, à partir de la troisième ligne de code, v2 possède le vecteur en question et il n'est plus accessible en tant que v. Pourquoi est-ce utile ? Lorsque chaque ressource a exactement un propriétaire, elle a également un moment unique auquel elle tombe hors de portée, qui peut être déterminée au moment de la compilation. Cela signifie à son tour que Rust peut tenir la promesse de RAII, en initialisant et en détruisant les ressources de manière déterministe en fonction de leur portée, sans jamais utiliser de ramasse-miettes ni exiger que le programmeur libère quoi que ce soit manuellement.

Comparez cela à la récupération de place avec comptage de références. Dans une implémentation RC, tous les pointeurs ont au moins deux éléments d'information : l'objet pointé et le nombre de références à cet objet. L'objet est détruit lorsque ce nombre atteint 0. Cela double les besoins en mémoire du pointeur et ajoute un petit coût à son utilisation, car le nombre est automatiquement incrémenté, décrémenté et vérifié. Le système de propriété de Rust offre la même garantie, que les objets sont automatiquement détruits lorsqu'ils manquent de références, mais il le fait sans aucun coût d'exécution. La propriété de chaque objet est analysée et les appels de destruction insérés au moment de la compilation.

Emprunt

Si la sémantique de déplacement était le seul moyen de transmettre des données, les types de retour de fonction deviendraient très compliqués, très rapides. Si vous vouliez écrire une fonction qui utilisait deux vecteurs pour produire un entier, qui ne détruisait pas les vecteurs par la suite, vous deviez les inclure dans la valeur de retour. Bien que cela soit techniquement possible, c'est terrible à utiliser :

 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);

Au lieu de cela, Rust a le concept d'emprunt. Vous pouvez écrire la même fonction ainsi, et elle empruntera la référence aux vecteurs, la rendant au propriétaire lorsque la fonction se terminera :

 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 et v2 retournent leur propriété à la portée d'origine après le retour de fn foo, tombant hors de la portée et étant automatiquement détruits lorsque la portée contenante se termine.

Il convient de mentionner ici qu'il existe des restrictions sur l'emprunt, appliquées par le vérificateur d'emprunt au moment de la compilation, que le Rust Book met très succinctement :

Tout emprunt doit avoir une portée ne dépassant pas celle du propriétaire. Deuxièmement, vous pouvez avoir l'un ou l'autre de ces deux types d'emprunts, mais pas les deux en même temps :

une ou plusieurs références (&T) à une ressource

exactement une référence mutable (&mut T)

Ceci est remarquable car il constitue un aspect essentiel de la protection de Rust contre les courses aux données. En empêchant plusieurs accès modifiables à une ressource donnée au moment de la compilation, cela garantit que le code ne peut pas être écrit dans lequel le résultat est indéterminé car cela dépend du thread arrivé en premier sur la ressource. Cela évite des problèmes tels que l'invalidation de l'itérateur et l'utilisation après la libération.

Le vérificateur d'emprunt en termes pratiques

Maintenant que nous connaissons certaines des fonctionnalités de Rust, regardons comment nous implémentons le même compteur de ligne de fichier que nous avons vu auparavant :

 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); } }

Au-delà des éléments déjà commentés dans le code source, il convient de parcourir et de retracer les durées de vie des différentes variables. file_name et file_lines durent jusqu'à la fin de main(); leurs destructeurs sont alors appelés sans surcoût, en utilisant le même mécanisme que les variables automatiques de C++. Lors de l'appel read_lines_from_file , file_name est prêté de manière immuable à cette fonction pour sa durée. Dans read_lines_from_file , buffer agit de la même manière, détruit lorsqu'il tombe hors de portée. lines , d'autre part, persiste et est renvoyé avec succès à main . Pourquoi?

La première chose à noter est que, comme Rust est un langage basé sur des expressions, l'appel de retour peut ne pas ressembler à un premier. Si la dernière ligne d'une fonction omet le point-virgule final, cette expression est la valeur de retour. La deuxième chose est que les valeurs de retour reçoivent un traitement spécial. Ils sont supposés vouloir vivre au moins aussi longtemps que l'appelant de la fonction. La note finale est qu'en raison de la sémantique de déplacement impliquée, aucune copie n'est nécessaire pour transmuter Ok(lines) en Ok(file_lines) , le compilateur fait simplement pointer la variable sur le bit de mémoire approprié.

"Ce n'est qu'à la fin que vous réalisez le véritable pouvoir de RAII."

La gestion manuelle de la mémoire est un cauchemar que les programmeurs ont inventé des moyens d'éviter depuis l'invention du compilateur. RAII était un modèle prometteur, mais paralysé en C++ car il ne fonctionnait tout simplement pas pour les objets alloués au tas sans quelques solutions de contournement étranges. Par conséquent, il y a eu une explosion de langages ramassés dans les ordures dans les années 90, conçus pour rendre la vie plus agréable pour le programmeur, même au détriment des performances.

Cependant, ce n'est pas le dernier mot dans la conception du langage. En utilisant des notions nouvelles et fortes de propriété et d'emprunt, Rust parvient à fusionner la base de portée des modèles RAII avec la sécurité de la mémoire de la récupération de place ; le tout sans jamais avoir besoin d'un éboueur pour arrêter le monde, tout en offrant des garanties de sécurité que l'on ne voit dans aucune autre langue. C'est l'avenir de la programmation système. Après tout, "l'erreur est humaine, mais les compilateurs n'oublient jamais".

Lectures complémentaires sur le blog Toptal Engineering :

• Tutoriel WebAssembly/Rust : traitement audio parfait
• Chasse aux fuites de mémoire en Java