Les machines virtuelles de langages de programmation sont devenues très répandues au cours des dernières décennies. Beaucoup de temps s'est écoulé depuis la présentation de Java Virtual Machine dans la seconde moitié des années 90, et il est sûr de dire que les interprètes de code octet ne sont pas l'avenir, mais le présent.
Mais cette technique, à mon avis, est presque universelle, et la compréhension des principes de base du développement d'un interprète est utile non seulement au créateur du prochain challenger pour le titre "Langue de l'année" selon TIOBE , mais à tout programmeur en général.
En un mot, si vous êtes intéressé à savoir comment nos langages de programmation préférés additionnent les nombres, ce que les développeurs de machines virtuelles discutent toujours et comment faire correspondre sans douleur les chaînes et les expressions régulières, je demande cat.
Première partie, introduction (actuelle)
Deuxième partie, optimisation
Troisième partie, appliquée
Contexte
L'un des systèmes auto-écrits du département Business Intelligence de notre entreprise possède une interface sous la forme d'un langage de requête simple. Dans la première version du système, ce langage était interprété à la volée, sans compilation, directement depuis la ligne d'entrée avec la requête. La deuxième version de l'analyseur fonctionnera déjà avec le bytecode intermédiaire, ce qui vous permettra de séparer le langage de requête de son exécution et de simplifier considérablement le code.
Dans le processus de travail sur la deuxième version du système, j'ai eu des vacances pendant lesquelles pendant une heure ou deux chaque jour, j'étais distrait des affaires familiales pour étudier des documents sur l'architecture et la performance des interprètes de bytecode. J'ai décidé de partager les notes et les exemples d'interprètes qui en résultent avec les lecteurs de Habr sous la forme d'une série d'articles.
La première d'entre elles présente cinq petites machines virtuelles (jusqu'à des centaines de lignes de code C simple), chacune révélant un certain aspect du développement de tels interprètes.
Où sont passés les codes d'octets dans les langages de programmation?
Un grand nombre de machines virtuelles, les jeux d'instructions virtuelles les plus diversifiés des dernières décennies, ont été inventés. Wikipedia affirme que les premiers langages de programmation ont commencé à se compiler en diverses représentations intermédiaires simplifiées dans les années 60 du siècle dernier. Certains de ces premiers codes d'octet ont été convertis en codes machine et exécutés par de vrais processeurs, tandis que d'autres ont été interprétés à la volée par des processeurs virtuels.
La popularité des ensembles d'instructions virtuelles en tant que représentation intermédiaire du code est due à trois raisons:
- Les programmes de bytecode sont facilement portés sur de nouvelles plateformes.
- Les interprètes de bytecode sont plus rapides que les interprètes de l'arbre de syntaxe du code.
- Vous pouvez développer une machine virtuelle simple en quelques heures seulement.
Faisons quelques machines virtuelles C simples et utilisons ces exemples pour mettre en évidence les principaux aspects techniques de la mise en œuvre des machines virtuelles.
Des exemples de codes complets sont disponibles sur GitHub . Des exemples peuvent être compilés avec n'importe quel GCC relativement récent:
gcc interpreter-basic-switch.c -o interpreter ./interpreter
Tous les exemples ont la même structure: vient d'abord le code de la machine virtuelle elle-même, puis la fonction principale avec des assertions qui vérifient le fonctionnement du code. J'ai essayé de commenter clairement les opcodes et les endroits clés des interprètes. J'espère que cet article sera compréhensible même pour les personnes qui n'écrivent pas quotidiennement en C.
L'interprète de bytecode le plus simple au monde
Comme je l'ai dit, l'interprète le plus simple est très facile à faire. Les commentaires sont juste derrière la liste, mais commençons directement par le code:
struct { uint8_t *ip; uint64_t accumulator; } vm; typedef enum { OP_INC, OP_DEC, OP_DONE } opcode; typedef enum interpret_result { SUCCESS, ERROR_UNKNOWN_OPCODE, } interpret_result; void vm_reset(void) { puts("Reset vm state"); vm = (typeof(vm)) { NULL }; } interpret_result vm_interpret(uint8_t *bytecode) { vm_reset(); puts("Start interpreting"); vm.ip = bytecode; for (;;) { uint8_t instruction = *vm.ip++; switch (instruction) { case OP_INC: { vm.accumulator++; break; } case OP_DEC: { vm.accumulator--; break; } case OP_DONE: { return SUCCESS; } default: return ERROR_UNKNOWN_OPCODE; } } return SUCCESS; }
Il y a moins d'une centaine de lignes, mais tous les attributs caractéristiques d'une machine virtuelle sont représentés. La machine a un seul registre ( vm.accumulator ), trois opérations (incrément de registre, décrément de registre et achèvement de l'exécution du programme) et un pointeur sur l'instruction en cours ( vm.ip ).
Chaque opération ( code d'opération ou code d'opération ) est codée sur un octet et la planification est effectuée à l'aide du switch habituel dans la fonction vm_interpret . Les branches du switch contiennent la logique des opérations, c'est-à-dire qu'elles changent l'état du registre ou terminent l'exécution du programme.
Les opérations sont transférées à la fonction vm_interpret sous la forme d'un tableau d'octets - un bytecode (Eng. Bytecode ) - et sont exécutées séquentiellement jusqu'à ce que l'opération d' OP_DONE machine virtuelle ( OP_DONE ) soit OP_DONE .
Un aspect clé d'une machine virtuelle est la sémantique, c'est-à-dire l'ensemble des opérations qui y sont possibles. Dans ce cas, il n'y a que deux opérations et elles modifient la valeur d'un seul registre.
Certains chercheurs ( Virtual-machine Abstraction and Optimization Techniques , 2009) proposent de diviser les machines virtuelles en machines de haut niveau et de bas niveau selon la proximité de la sémantique de la machine virtuelle avec la sémantique de la machine physique sur laquelle le bytecode sera exécuté.
Dans le cas extrême, le bytecode des machines virtuelles de bas niveau peut répéter complètement le code machine de la machine physique avec de la RAM simulée, un ensemble complet de registres, des instructions pour travailler avec la pile, etc. La machine virtuelle Bochs , par exemple, répète le jeu d'instructions d'architecture x86.
Et vice versa: les opérations des machines virtuelles de haut niveau reflètent étroitement la sémantique d'un langage de programmation spécialisé compilé en bytecode. Alors travaillez, par exemple, SQLite, Gawk et de nombreuses versions de Prolog.
Les postes intermédiaires sont occupés par des interprètes de langages de programmation à usage général ayant des éléments de niveaux élevé et faible. La machine virtuelle Java la plus populaire a à la fois des instructions de bas niveau pour travailler avec la pile et une prise en charge intégrée pour la programmation orientée objet avec allocation automatique de mémoire.
Le code ci-dessus est plus susceptible d'être le plus primitif des machines virtuelles de bas niveau: chaque instruction virtuelle est un wrapper sur une ou deux instructions physiques, le registre virtuel est entièrement cohérent avec un registre du processeur "iron".
Arguments de l'instruction Bytecode
Nous pouvons dire que le seul registre dans notre exemple de machine virtuelle est à la fois un argument et la valeur de retour de toutes les instructions exécutées. Cependant, nous pouvons trouver utile de passer des arguments dans les instructions. Une façon consiste à les mettre directement en bytecode.
Nous allons développer l'exemple en introduisant des instructions (OP_ADDI, OP_SUBI) qui prennent un argument sous la forme d'un octet suivant immédiatement l'opcode:
struct { uint8_t *ip; uint64_t accumulator; } vm; typedef enum { OP_INC, OP_DEC, OP_ADDI, OP_SUBI, OP_DONE } opcode; typedef enum interpret_result { SUCCESS, ERROR_UNKNOWN_OPCODE, } interpret_result; void vm_reset(void) { puts("Reset vm state"); vm = (typeof(vm)) { NULL }; } interpret_result vm_interpret(uint8_t *bytecode) { vm_reset(); puts("Start interpreting"); vm.ip = bytecode; for (;;) { uint8_t instruction = *vm.ip++; switch (instruction) { case OP_INC: { vm.accumulator++; break; } case OP_DEC: { vm.accumulator--; break; } case OP_ADDI: { uint8_t arg = *vm.ip++; vm.accumulator += arg; break; } case OP_SUBI: { uint8_t arg = *vm.ip++; vm.accumulator -= arg; break; } case OP_DONE: { return SUCCESS; } default: return ERROR_UNKNOWN_OPCODE; } } return SUCCESS; }
De nouvelles instructions (voir la fonction vm_interpret ) lisent leur argument dans le bytecode et l'ajoutent au registre / le soustraient du registre.
Un tel argument est appelé un argument immédiat , car il se trouve directement dans le tableau d'opcode. La principale limitation de notre implémentation est que l'argument est un seul octet et ne peut prendre que 256 valeurs.
Dans notre machine virtuelle, la plage de valeurs d'argument d'instructions possibles ne joue pas un grand rôle. Mais si la machine virtuelle sera utilisée comme interprète du vrai langage, alors il est logique de compliquer le bytecode en ajoutant une table de constantes distincte du tableau des opcodes et des instructions avec un argument direct correspondant à l'adresse de cet argument dans la table des constantes.
Machine à empiler
Les instructions de notre machine virtuelle simple fonctionnent toujours avec un seul registre et ne peuvent en aucun cas se transmettre des données. De plus, l'argument de l'instruction ne peut être qu'immédiat et, par exemple, l'opération d'addition ou de multiplication prend deux arguments.
Autrement dit, nous n'avons aucun moyen d'évaluer des expressions complexes. Pour résoudre ce problème, une machine empilée est nécessaire, c'est-à-dire une machine virtuelle avec une pile intégrée:
#define STACK_MAX 256 struct { uint8_t *ip; uint64_t stack[STACK_MAX]; uint64_t *stack_top; uint64_t result; } vm; typedef enum { OP_PUSHI, OP_ADD, OP_SUB, OP_DIV, OP_MUL, OP_POP_RES, OP_DONE, } opcode; typedef enum interpret_result { SUCCESS, ERROR_DIVISION_BY_ZERO, ERROR_UNKNOWN_OPCODE, } interpret_result; void vm_reset(void) { puts("Reset vm state"); vm = (typeof(vm)) { NULL }; vm.stack_top = vm.stack; } void vm_stack_push(uint64_t value) { *vm.stack_top = value; vm.stack_top++; } uint64_t vm_stack_pop(void) { vm.stack_top--; return *vm.stack_top; } interpret_result vm_interpret(uint8_t *bytecode) { vm_reset(); puts("Start interpreting"); vm.ip = bytecode; for (;;) { uint8_t instruction = *vm.ip++; switch (instruction) { case OP_PUSHI: { uint8_t arg = *vm.ip++; vm_stack_push(arg); break; } case OP_ADD: { uint64_t arg_right = vm_stack_pop(); uint64_t arg_left = vm_stack_pop(); uint64_t res = arg_left + arg_right; vm_stack_push(res); break; } case OP_SUB: { uint64_t arg_right = vm_stack_pop(); uint64_t arg_left = vm_stack_pop(); uint64_t res = arg_left - arg_right; vm_stack_push(res); break; } case OP_DIV: { uint64_t arg_right = vm_stack_pop(); if (arg_right == 0) return ERROR_DIVISION_BY_ZERO; uint64_t arg_left = vm_stack_pop(); uint64_t res = arg_left / arg_right; vm_stack_push(res); break; } case OP_MUL: { uint64_t arg_right = vm_stack_pop(); uint64_t arg_left = vm_stack_pop(); uint64_t res = arg_left * arg_right; vm_stack_push(res); break; } case OP_POP_RES: { uint64_t res = vm_stack_pop(); vm.result = res; break; } case OP_DONE: { return SUCCESS; } default: return ERROR_UNKNOWN_OPCODE; } } return SUCCESS; }
Dans cet exemple, il y a déjà plus d'opérations et presque toutes ne fonctionnent qu'avec la pile. OP_PUSHI pousse son argument immédiat sur la pile. Les instructions OP_ADD, OP_SUB, OP_DIV, OP_MUL sont extraites d'une pile de valeurs, calculent le résultat et le repoussent sur la pile. OP_POP_RES supprime la valeur de la pile et la place dans le registre des résultats, destiné aux résultats de la machine virtuelle.
Pour l'opération de division (OP_DIV), une erreur de division par zéro est interceptée, ce qui arrête la machine virtuelle.
Les capacités d'une telle machine sont beaucoup plus larges que la précédente avec un seul registre et permettent, par exemple, de calculer des expressions arithmétiques complexes. Un autre (et important!) Avantage est la simplicité de compilation des langages de programmation dans le code octet de la machine de pile.
Enregistrer la machine
En raison de leur simplicité, les machines virtuelles empilées sont les plus utilisées parmi les développeurs de langages de programmation; les mêmes JVM et VM Python les utilisent exactement.
Cependant, ces machines ont des inconvénients: elles doivent ajouter des instructions spéciales pour travailler avec la pile, lors du calcul des expressions, tous les arguments passent à plusieurs reprises dans une seule structure de données, de nombreuses instructions supplémentaires apparaîtront inévitablement dans le code de la pile.
Pendant ce temps, l'exécution de chaque instruction supplémentaire entraîne le coût de l'ordonnancement, c'est-à-dire le décodage de l'opcode et le passage au corps des instructions.
Une alternative aux machines empilées consiste à enregistrer les machines virtuelles. Ils ont un bytecode plus complexe: le nombre d'arguments de registre et le numéro de résultat de registre sont explicitement codés dans chaque instruction. Par conséquent, au lieu d'une pile, un ensemble étendu de registres est utilisé comme stockage de valeurs intermédiaires.
#define REGISTER_NUM 16 struct { uint16_t *ip; uint64_t reg[REGISTER_NUM]; uint64_t result; } vm; typedef enum { OP_LOADI, OP_ADD, OP_SUB, OP_DIV, OP_MUL, OP_MOV_RES, OP_DONE, } opcode; typedef enum interpret_result { SUCCESS, ERROR_DIVISION_BY_ZERO, ERROR_UNKNOWN_OPCODE, } interpret_result; void vm_reset(void) { puts("Reset vm state"); vm = (typeof(vm)) { NULL }; } void decode(uint16_t instruction, uint8_t *op, uint8_t *reg0, uint8_t *reg1, uint8_t *reg2, uint8_t *imm) { *op = (instruction & 0xF000) >> 12; *reg0 = (instruction & 0x0F00) >> 8; *reg1 = (instruction & 0x00F0) >> 4; *reg2 = (instruction & 0x000F); *imm = (instruction & 0x00FF); } interpret_result vm_interpret(uint16_t *bytecode) { vm_reset(); puts("Start interpreting"); vm.ip = bytecode; uint8_t op, r0, r1, r2, immediate; for (;;) { uint16_t instruction = *vm.ip++; decode(instruction, &op, &r0, &r1, &r2, &immediate); switch (op) { case OP_LOADI: { vm.reg[r0] = immediate; break; } case OP_ADD: { vm.reg[r2] = vm.reg[r0] + vm.reg[r1]; break; } case OP_SUB: { vm.reg[r2] = vm.reg[r0] - vm.reg[r1]; break; } case OP_DIV: { if (vm.reg[r1] == 0) return ERROR_DIVISION_BY_ZERO; vm.reg[r2] = vm.reg[r0] / vm.reg[r1]; break; } case OP_MUL: { vm.reg[r2] = vm.reg[r0] * vm.reg[r1]; break; } case OP_MOV_RES: { vm.result = vm.reg[r0]; break; } case OP_DONE: { return SUCCESS; } default: return ERROR_UNKNOWN_OPCODE; } } return SUCCESS; }
L'exemple montre une machine à registres avec 16 registres. Les instructions occupent chacune 16 bits et sont codées de trois manières:
- 4 bits par opcode + 4 bits par nom de registre + 8 bits par argument.
- 4 bits par opcode + trois fois 4 bits par nom de registre.
- 4 bits par opcode + 4 bits par nom de registre unique + 8 bits inutilisés.
Notre petite machine virtuelle a très peu d'opérations, donc quatre bits (ou 16 opérations possibles) par opcode suffisent largement. L'opération détermine ce que représentent exactement les bits restants de l'instruction.
Le premier type de codage (4 + 4 + 8) est nécessaire pour charger des données dans des registres avec l'opération OP_LOADI. Le deuxième type (4 + 4 + 4 + 4) est utilisé pour les opérations arithmétiques, qui devraient savoir où prendre une paire d'arguments et où ajouter le résultat du calcul. Et enfin, la dernière forme (4 + 4 + 8 bits inutiles) est utilisée pour les instructions avec un seul registre comme argument, dans notre cas c'est OP_MOV_RES.
Pour encoder et décoder des instructions, nous avons maintenant besoin d'une logique spéciale (fonction de decode ). En revanche, la logique des instructions, grâce à l'indication explicite de l'emplacement des arguments, devient plus facile - les opérations avec la pile disparaissent.
Principales caractéristiques: dans le bytecode des machines à registres, il y a moins d'instructions, les instructions individuelles sont plus larges, la compilation dans un tel bytecode est plus difficile - le compilateur doit décider comment utiliser les registres disponibles.
Il convient de noter qu'en pratique, dans les registres de machines virtuelles, il y a généralement une pile où, par exemple, les arguments de fonction sont placés; les registres sont utilisés pour calculer des expressions individuelles. Même s'il n'y a pas de pile explicite, un tableau est utilisé pour créer la pile, jouant le même rôle que la RAM dans les machines physiques.
Machines à empiler et à enregistrer, comparaison
Il existe une étude intéressante ( Virtual machine showdown: Stack versus registers , 2008) qui a eu une grande influence sur tous les développements ultérieurs dans le domaine des machines virtuelles pour les langages de programmation. Ses auteurs ont proposé une méthode de traduction directe du code de pile d'une machine virtuelle Java standard en un code de registre et comparé les performances.
La méthode n'est pas anodine: le code est d'abord traduit, puis optimisé de manière assez compliquée. Mais une comparaison ultérieure des performances du même programme a montré que les cycles de processeur supplémentaires consacrés aux instructions de décodage sont entièrement compensés par une diminution du nombre total d'instructions. En général, en bref, la machine à registres était plus efficace que la pile.
Comme déjà mentionné ci-dessus, cette efficacité a un prix assez tangible: le compilateur doit allouer les registres lui-même et un optimiseur avancé est en outre souhaitable.
Le débat sur la meilleure architecture n'est pas terminé. Si nous parlons de compilateurs Java, le bytecode Dalvik VM, qui fonctionnait jusqu'à récemment sur tous les appareils Android, était enregistré; mais le titre JVM a conservé une pile d'instructions. La machine virtuelle Lua utilise une machine d'enregistrement, mais la machine virtuelle Python est toujours empilable. Et ainsi de suite.
Bytecode dans les interpréteurs d'expressions régulières
Enfin, pour nous distraire des machines virtuelles de bas niveau, regardons un interpréteur spécialisé qui vérifie les chaînes pour la correspondance des expressions régulières:
typedef enum { OP_CHAR, OP_OR, OP_JUMP, OP_MATCH, } opcode; typedef enum match_result { MATCH_OK, MATCH_FAIL, MATCH_ERROR, } match_result; match_result vm_match_recur(uint8_t *bytecode, uint8_t *ip, char *sp) { for (;;) { uint8_t instruction = *ip++; switch (instruction) { case OP_CHAR:{ char cur_c = *sp; char arg_c = (char)*ip ; if (arg_c != cur_c) return MATCH_FAIL; ip++; sp++; continue; } case OP_JUMP:{ uint8_t offset = *ip; ip = bytecode + offset; continue; } case OP_OR:{ uint8_t left_offset = *ip++; uint8_t right_offset = *ip; uint8_t *left_ip = bytecode + left_offset; if (vm_match_recur(bytecode, left_ip, sp) == MATCH_OK) return MATCH_OK; ip = bytecode + right_offset; continue; } case OP_MATCH:{ return MATCH_OK; } } return MATCH_ERROR; } } match_result vm_match(uint8_t *bytecode, char *str) { printf("Start matching a string: %s\n", str); return vm_match_recur(bytecode, bytecode, str); }
L'instruction principale est OP_CHAR. Elle prend son argument immédiat et le compare avec le caractère actuel de la chaîne ( char *sp ). En cas de coïncidence des caractères attendus et actuels dans la ligne, la transition vers l'instruction suivante et le caractère suivant se produit.
La machine comprend également l'opération de saut (OP_JUMP), qui prend un seul argument immédiat. L'argument signifie le décalage absolu dans le bytecode, d'où continuer le calcul.
La dernière opération importante est OP_OR. Elle prend deux décalages, essayant d'appliquer le code d'abord sur le premier, puis, en cas d'erreur, sur le second. Elle le fait avec un appel récursif, c'est-à-dire que l'instruction fait un tour dans la profondeur de l'arbre de toutes les variantes possibles de l'expression régulière.
Étonnamment, quatre opcodes et soixante-dix lignes de code suffisent pour exprimer des expressions régulières comme "abc", "a? Bc", "(ab | bc) d", "a * bc". Cette machine virtuelle n'a même pas d'état explicite, car tout ce dont vous avez besoin - pointeurs vers le début du flux d'instructions, l'instruction en cours et le caractère en cours - est transmis en tant qu'arguments à la fonction récursive.
Si vous êtes intéressé par les détails du travail des moteurs d'expression régulière, vous pouvez d'abord lire une série d'articles de Russ Cox, l'auteur du moteur d'expression régulière de Google RE2 .
Résumé
Résumons.
Pour les langages de programmation à usage général, en règle générale, deux architectures sont utilisées: empiler et enregistrer.
Dans le modèle de pile, la structure de données principale et la méthode de transmission des arguments entre les instructions sont la pile. Dans le modèle de registre, un ensemble de registres est utilisé pour calculer les expressions, mais une pile explicite ou implicite est toujours utilisée pour stocker les arguments de fonction.
La présence d'une pile explicite et d'un ensemble de registres rapproche ces machines des machines de bas niveau et même physiques. L'abondance d'instructions de bas niveau dans un tel bytecode signifie qu'une dépense importante de ressources du processeur physique tombe sur le décodage et l'ordonnancement des instructions virtuelles.
D'un autre côté, les instructions de haut niveau jouent un grand rôle dans les machines virtuelles populaires. En Java, par exemple, ce sont des instructions pour les appels de fonctions polymorphes, l'allocation d'objets et le garbage collection.
Des machines virtuelles de haut niveau - par exemple, des interprètes de codes d'octets de langages avec une sémantique développée et loin de fer - la plupart du temps ne passent pas dans le répartiteur ou le décodeur, mais dans le corps des instructions et, par conséquent, sont relativement efficaces.
Recommandations pratiques:
- Si vous avez besoin d'exécuter un bytecode et de le faire dans un délai raisonnable, essayez alors d'utiliser les instructions les plus proches de votre tâche; plus le niveau sémantique est élevé, mieux c'est. Cela réduira les coûts de planification et simplifiera la génération de code.
- Si vous avez besoin de plus de flexibilité et d'une sémantique hétérogène, vous devez au moins essayer de mettre en évidence le dénominateur commun dans le bytecode afin que les instructions résultantes soient à un niveau moyen conditionnel.
- Si à l'avenir, il peut être nécessaire de calculer des expressions, de créer une machine empilée, cela réduira les maux de tête lors de la compilation de code d'octets.
- Si aucune expression n'est attendue, créez une machine à registres triviale, ce qui évitera le coût de la pile et simplifiera les instructions elles-mêmes.
Dans les articles suivants, je vais discuter des implémentations pratiques des machines virtuelles dans les langages de programmation populaires et expliquer pourquoi le département Business Intelligence Badoo avait besoin d'un bytecode.