Skip to content
Computer Internals

Niveau 2 · Chapitre 2.8

Machines virtuelles à bytecode et ramasse-miettes

L’intérieur d’un environnement d’exécution : un interpréteur de bytecode écrit en C qui exécute de vrais opcodes JVM dans le simulateur, ce qu’il coûte par instruction, machines à pile contre machines à registres et fonctionnement de la répartition — puis le ramasse-miettes : comptage de références, un collecteur « marquer et balayer » à exécuter pas à pas, et les collecteurs générationnels de V8 et de la JVM.

Le premier chapitre de ce niveau a présenté les trois façons d’exécuter un programme : le compiler, l’interpréter, ou le compiler à la volée. Celui-ci ouvre l’interpréteur. Des langages comme Java, Python, JavaScript ou C# s’exécutent sur un environnement d’exécution (runtime), un programme qui fournit deux choses que le C vous laisse : une machine virtuelle qui exécute du bytecode, et un ramasse-miettes (garbage collector) qui libère la mémoire automatiquement. Ce sont deux programmes ordinaires, et dans leur forme la plus simple, chacun tient en quelques dizaines de lignes de C.

Une machine virtuelle sur une page de C

Une machine virtuelle à bytecode est une boucle : lire l’instruction de bytecode suivante, la décoder, l’exécuter, recommencer — le cycle lecture-décodage-exécution d’un vrai CPU, réalisé en logiciel. En voici une, avec sa propre pile d’opérandes et ses variables locales, qui exécute un programme en vrai bytecode JVM. Les instructions viennent du sous-ensemble que Tanenbaum appelle IJVM, avec les mêmes numéros d’opcode que la machine virtuelle Java : 0x10 est BIPUSH, 0x60 est IADD, 0xA7 est GOTO.

Le bytecode, assemblé à la main, calcule la même fonction que la démo du premier chapitre : s = 0; for (i = 0; i != n; i++) s += i * 2; return s;, où i * 2 s’écrit i + i, car IJVM n’a pas de multiplication.

Live · Un interpréteur de bytecode JVM, exécuté par le CPU simulé

À essayer : Appuyez sur Step pour exécuter une instruction, Run pour animer ou Continue pour aller au bout ; les boutons L2 à L7 changent de niveau, vers le bas ou le haut.

C source — click a line number for a breakpoint
  1. // total(n): s = 0; for (i = 0; i != n; i++) s += i + i; return s;
  2. unsigned char code[] = {
  3. 0x10, 0, // 0 BIPUSH 0
  4. 0x36, 1, // 2 ISTORE 1 s = 0
  5. 0x10, 0, // 4 BIPUSH 0
  6. 0x36, 2, // 6 ISTORE 2 i = 0
  7. 0x15, 2, // 8 ILOAD 2
  8. 0x15, 0, // 10 ILOAD 0
  9. 0x9f, 0x00, 18, // 12 IF_ICMPEQ +18 i == n: go to 30
  10. 0x15, 1, // 15 ILOAD 1
  11. 0x15, 2, // 17 ILOAD 2
  12. 0x59, // 19 DUP
  13. 0x60, // 20 IADD i + i
  14. 0x60, // 21 IADD s + (i + i)
  15. 0x36, 1, // 22 ISTORE 1
  16. 0x84, 2, 1, // 24 IINC 2 1 i++
  17. 0xa7, 0xff, 0xed, // 27 GOTO -19 back to 8
  18. 0x15, 1, // 30 ILOAD 1
  19. 0xac // 32 IRETURN
  20. };
  22. int run(int n) {
  23. int stack[8];
  24. int local[4];
  25. int sp = 0;
  26. int pc = 0;
  27. local[0] = n;
  28. while (1) {
  29. int op = code[pc];
  30. switch (op) {
  31. case 0x10: // BIPUSH byte
  32. stack[sp++] = (signed char)code[pc + 1];
  33. pc += 2;
  34. break;
  35. case 0x15: // ILOAD varnum
  36. stack[sp++] = local[code[pc + 1]];
  37. pc += 2;
  38. break;
  39. case 0x36: // ISTORE varnum
  40. local[code[pc + 1]] = stack[--sp];
  41. pc += 2;
  42. break;
  43. case 0x59: // DUP
  44. stack[sp] = stack[sp - 1];
  45. sp++;
  46. pc += 1;
  47. break;
  48. case 0x60: // IADD
  49. sp--;
  50. stack[sp - 1] = stack[sp - 1] + stack[sp];
  51. pc += 1;
  52. break;
  53. case 0x84: // IINC varnum const
  54. local[code[pc + 1]] += (signed char)code[pc + 2];
  55. pc += 3;
  56. break;
  57. case 0x9f: // IF_ICMPEQ offset
  58. sp -= 2;
  59. if (stack[sp] == stack[sp + 1])
  60. pc += (short)(code[pc + 1] << 8 | code[pc + 2]);
  61. else
  62. pc += 3;
  63. break;
  64. case 0xa7: // GOTO offset
  65. pc += (short)(code[pc + 1] << 8 | code[pc + 2]);
  66. break;
  67. case 0xac: // IRETURN
  68. return stack[--sp];
  69. }
  70. }
  71. }
  73. int main() {
  74. return run(5);
  75. }
step 0
Loading emulator…
Your program as you wrote it: the current line, its variables by name, and its output.

Appuyez sur Continue pour l’exécuter : il renvoie 20, la même réponse que la version compilée. Avancez pas à pas sur quelques tours de la boucle while en observant pc, sp, stack et local dans le panneau des variables : la machine virtuelle a son propre compteur de programme, son propre pointeur de pile et ses propres registres, rangés en mémoire ordinaire. Le vrai CPU exécute l’interpréteur ; l’interpréteur exécute le bytecode.

Tout ici reflète le matériel. Les décalages de branchement sont des nombres signés sur 16 bits relatifs à l’instruction de branchement elle-même, donc GOTO -19 à l’adresse 27 revient en 8, et (short)(hi << 8 | lo) les décode en gros-boutiste, comme l’exige la JVM. La microarchitecture Mic-1 de Tanenbaum interprète exactement ce jeu d’instructions, en microcode au lieu de C : le chapitre sur la microprogrammation montre comment elle se répartit sur l’octet d’opcode en une seule étape, là où ce switch a besoin d’une chaîne de comparaisons.

Ce que coûte l’interprétation

Le programme en bytecode exécute 64 instructions de bytecode. Le CPU simulé, qui exécute l’interpréteur, exécute environ 3 100 instructions machine pour y parvenir — près de 50 instructions machine par instruction de bytecode, ici avec un compilateur sans optimisation. Le même total(5) compilé directement en code machine prenait 81 instructions dans le premier chapitre.

Le surcoût vient d’un travail que la version compilée ne fait jamais : lire chaque opcode en mémoire, le décoder à travers le switch, garder stack, local, sp et pc en mémoire plutôt qu’en registres, et remonter en haut de la boucle. Les vrais interpréteurs sont écrits bien plus soigneusement que celui-ci, et compilés avec optimisations, donc le rapport diminue beaucoup. Mais il n’atteint jamais zéro, ce qui explique l’écart d’environ 20× entre CPython et le C au premier chapitre, et l’existence des compilateurs JIT.

Machines à pile et machines à registres

Cette machine virtuelle est une machine à pile : IADD ne prend pas d’opérandes, car ce sont toujours les deux entrées au sommet de la pile. La JVM, CPython, WebAssembly et .NET fonctionnent ainsi. Le bytecode est compact et simple à produire, mais il faut beaucoup d’instructions, puisque chaque valeur doit être empilée avant usage.

Une machine à registres nomme au contraire ses opérandes, comme un vrai CPU : Lua 5 et la machine virtuelle Dalvik d’Android utilisent des instructions comme ADD r1, r2, r3, et Ignition, l’interpréteur de V8, est une machine à registres avec accumulateur (les Ldar et Star du listing du premier chapitre). Chaque instruction est plus grosse, mais il y en a moins, donc moins de répartitions. Pour un interpréteur, la répartition est le coût dominant.

La répartition

Le switch de cette machine virtuelle a neuf cas répartis de 0x10 à 0xAC, trop clairsemés pour une table de sauts, donc le compilateur produit une chaîne d’au plus neuf comparaisons pour chaque instruction de bytecode : le chapitre sur le flot de contrôle a montré pourquoi. Les vraies machines virtuelles utilisent des numéros d’opcode denses, de 0 à environ 200, donc leur switch devient une table de sauts : un saut indirect par instruction de bytecode.

L’étape suivante est le code enfilé (threaded code) : au lieu de remonter à un unique switch en haut de la boucle, le traitement de chaque instruction se termine par son propre saut indirect vers le traitement suivant. CPython le fait quand le compilateur prend en charge le « computed goto » (une extension de GCC, également présente dans clang). Un saut indirect par traitement, au lieu d’un saut unique partagé par tous, donne de bien meilleures chances au prédicteur de branchements : il peut apprendre qu’un ILOAD est souvent suivi d’un autre ILOAD. CPython 3.14 a ajouté, en option, un interpréteur fondé sur des appels terminaux entre traitements, pour la même raison.

Le ramasse-miettes

Le chapitre sur le tas s’est terminé sur les bugs du free manuel : fuites, utilisation après libération, double libération. Un ramasse-miettes les élimine en rendant la libération automatique : l’environnement d’exécution libère un objet dès que le programme ne peut plus l’atteindre. Il existe deux familles d’approches.

Le comptage de références

Chaque objet tient le compte des références qui pointent vers lui. Chaque affectation met les compteurs à jour, et quand un compteur tombe à zéro, l’objet est libéré immédiatement. CPython fonctionne ainsi, et on peut voir le compteur :

>>> a = Node()
>>> sys.getrefcount(a)     # a, plus l’argument de getrefcount lui-même
2
>>> b = a
>>> sys.getrefcount(b)
3

Le comptage de références libère la mémoire aussi tôt que possible, et de façon prévisible. Mais il coûte du travail à chaque affectation, et il a un angle mort : les cycles. Si x pointe vers y et y pointe vers x, les deux compteurs restent à 1 même après que le programme les a abandonnés, et ils ne sont jamais libérés. CPython exécute donc aussi un collecteur de cycles séparé : après x.other = y; y.other = x; del x, y, un appel à gc.collect() signale 2 objets inaccessibles trouvés et libérés. Swift et le shared_ptr du C++ utilisent aussi le comptage de références, et laissent les cycles au programmeur, avec des références faibles.

Le traçage : marquer et balayer

Un collecteur traçant prend le point de vue inverse. Il ne suit pas du tout les affectations. De temps en temps, il part des racines — les variables globales et les variables sur la pile de chaque thread — et suit chaque pointeur, en marquant chaque objet atteint. Tout ce qui n’est pas marqué est un déchet, quelle que soit la façon dont il est relié, cycles compris. Puis il balaie : il parcourt tout le tas et libère les objets non marqués.

Voici un collecteur « marquer et balayer » complet, sur un tas de huit objets. Le programme construit A → B → C, plus deux objets D et E qui pointent l’un vers l’autre, puis abandonne ses références à C, D et E :

Live · Marquer et balayer, avec un cycle

À essayer : Appuyez sur Step pour exécuter une instruction, Run pour animer ou Continue pour aller au bout ; les boutons L2 à L7 changent de niveau, vers le bas ou le haut.

C source — click a line number for a breakpoint
  1. struct Obj {
  2. int used;
  3. int marked;
  4. struct Obj *a;
  5. struct Obj *b;
  6. };
  8. struct Obj heap[8];
  9. struct Obj *root;
  11. struct Obj *new_obj(void) {
  12. for (int i = 0; i < 8; i++) {
  13. if (!heap[i].used) {
  14. heap[i].used = 1;
  15. heap[i].a = 0;
  16. heap[i].b = 0;
  17. return &heap[i];
  18. }
  19. }
  20. return 0;
  21. }
  23. void mark(struct Obj *o) {
  24. if (o == 0 || o->marked)
  25. return;
  26. o->marked = 1;
  27. mark(o->a);
  28. mark(o->b);
  29. }
  31. int sweep(void) {
  32. int freed = 0;
  33. for (int i = 0; i < 8; i++) {
  34. if (heap[i].used && !heap[i].marked) {
  35. heap[i].used = 0;
  36. freed++;
  37. }
  38. heap[i].marked = 0;
  39. }
  40. return freed;
  41. }
  43. int main() {
  44. root = new_obj(); // A
  45. root->a = new_obj(); // A -> B
  46. root->a->a = new_obj(); // B -> C
  47. struct Obj *x = new_obj(); // D
  48. struct Obj *y = new_obj(); // E
  49. x->a = y; // D -> E
  50. y->a = x; // E -> D: a cycle
  51. x = 0;
  52. y = 0; // nothing points to D or E any more, except each other
  53. root->a->a = 0; // and nothing points to C
  54. mark(root);
  55. return sweep();
  56. }
step 0
Loading emulator…
Your program as you wrote it: the current line, its variables by name, and its output.

Il renvoie 3 : C, D et E sont libérés. Le marquage part de root, atteint A et B, et s’arrête, donc le cycle D ↔ E n’est jamais marqué — une conclusion à laquelle le comptage de références n’aurait jamais pu arriver. Observez les champs used et marked du tableau heap dans le panneau des globales pendant l’exécution de mark et de sweep. mark est récursive : c’est aussi un bon endroit pour observer la pile d’appels.

Les vrais collecteurs

Les collecteurs de production ajoutent trois idées à ce squelette :

  • Déplacer et compacter. Au lieu de laisser des trous, un collecteur par copie déplace chaque objet vivant dans une zone neuve, en les tassant, et met à jour chaque pointeur vers lui. L’allocation devient alors une simple incrémentation de pointeur, aussi rapide qu’une pile.
  • Les générations. La plupart des objets meurent jeunes : chaînes temporaires, itérateurs, résultats intermédiaires. Les collecteurs générationnels allouent les nouveaux objets dans une petite zone jeune, qu’ils collectent souvent et à peu de frais, et ne collectent l’ancienne génération qu’occasionnellement. V8 le montre avec node --trace-gc : une boucle qui alloue 2 millions d’objets éphémères déclenche 41 collectes Scavenge de la jeune génération, de 0,1 à 0,5 ms chacune, et aucune collecte complète Mark-Compact de tout le tas.
  • La concurrence. Arrêter tous les threads pendant le traçage du tas donne des pauses proportionnelles au tas. Les collecteurs modernes font l’essentiel du marquage en parallèle du programme. Le collecteur par défaut de la JVM, G1, vise des pauses de quelques centaines de millisecondes au plus, et ZGC les maintient sous la milliseconde, même sur des tas de plusieurs gigaoctets.

Le compromis est le même que partout dans ce niveau : le ramasse-miettes coûte du temps CPU et de la marge mémoire, et en échange le programme ne peut ni oublier un objet ni utiliser un objet déjà libéré.

À retenir

  • Une machine virtuelle à bytecode est une boucle lecture-décodage-exécution en logiciel, avec son propre compteur de programme, sa pile et ses locales. La démo exécute de vrais opcodes JVM (IJVM) et renvoie le même 20 que le code compilé.
  • Interpréter coûte des dizaines d’instructions machine par instruction de bytecode — environ 50 ici — pour la lecture, le décodage, la répartition et l’état de la machine virtuelle gardé en mémoire. Les JIT existent pour supprimer ce surcoût.
  • Les machines à pile (JVM, CPython, WebAssembly) ont un bytecode compact ; les machines à registres (Lua, Dalvik, Ignition de V8) exécutent moins d’instructions. La répartition s’optimise avec des tables de sauts et le code enfilé.
  • Le comptage de références libère un objet dès que son compteur atteint zéro, mais ne peut pas libérer seul les cycles.
  • Les collecteurs traçants marquent tout ce qui est accessible depuis les racines et balaient le reste, cycles compris.
  • Les vrais collecteurs compactent, répartissent les objets en générations, et travaillent en parallèle du programme pour garder des pauses courtes.

Dans ce niveau

  1. 2.1Langages compilés, interprétés et compilés à la volée (JIT)
  2. 2.2Du code source au binaire qui s’exécute
  3. 2.3Variables, types et disposition en mémoire
  4. 2.4Pointeurs et tableaux
  5. 2.5Fonctions, appels et la pile
  6. 2.6Structures, malloc et le tas
  7. 2.7Flot de contrôle : if, boucles, switch
  8. 2.8Machines virtuelles à bytecode et ramasse-miettes