"Peu importe vos efforts, vous ne pouvez pas faire un cheval de course avec un porc. Vous pouvez cependant faire un porc plus rapide" (commentaire dans le code source d'Emax)
Tout le monde sait que les porcs ne volent pas. Tout aussi populaire est l'opinion selon laquelle les interprètes de bytecode en tant que technique pour exécuter des langages de haut niveau ne peuvent pas être accélérés sans l'utilisation d'une compilation dynamique longue.
Dans la deuxième partie d'une série d'articles sur les interprètes de bytecode, j'essaierai de montrer par l'exemple d'une petite machine virtuelle FDA empilée (Pig Virtual Machine) que tout n'est pas perdu pour les porcelets assidus et ambitieux et qu'il est tout à fait possible d'accélérer dans le cadre (principalement) de la norme C le travail de ces interprètes est au moins une fois et demie.
Première partie, introduction
Deuxième partie, optimisation (actuelle)
Troisième partie, appliquée
Porcelet
Faisons connaissance.
Piglet VM est une machine empilée ordinaire basée sur un exemple de la première partie d'une série d'articles. Notre cochon ne connaît qu'un seul type de données - un mot machine 64 bits, et tous les calculs (entiers) sont effectués sur la pile avec une profondeur maximale de 256 mots machine. En plus de la pile, ce porcelet a une mémoire de travail de 65 536 mots machine. Le résultat de l'exécution du programme - un mot machine - peut être soit placé dans le registre des résultats, soit simplement envoyé vers la sortie standard (stdout).
L'état complet de la machine Piglet VM est stocké dans une seule structure:
static struct { uint8_t *ip; uint64_t stack[STACK_MAX]; uint64_t *stack_top; uint64_t memory[MEMORY_SIZE]; uint64_t result; } vm;
Ce qui précède nous permet d'attribuer cette machine à des machines virtuelles de bas niveau, la quasi-totalité de la surcharge qui incombe à la maintenance du cycle de programme principal:
interpret_result vm_interpret(uint8_t *bytecode) { vm_reset(bytecode); for (;;) { uint8_t instruction = NEXT_OP(); switch (instruction) { case OP_PUSHI: { uint16_t arg = NEXT_ARG(); PUSH(arg); break; } case OP_ADD: { uint64_t arg_right = POP(); *TOS_PTR() += arg_right; break; } case OP_DONE: { return SUCCESS; } default: return ERROR_UNKNOWN_OPCODE; } } return ERROR_END_OF_STREAM; }
Le code montre que pour chaque opcode, le piggy doit:
- Récupérez l'opcode du flux d'instructions.
- Assurez-vous que l'opcode est dans la plage valide de valeurs d'opcode (cette logique est ajoutée par le compilateur C lors de la génération du code de commutateur).
- Allez aux instructions du corps.
- Extrayez les arguments d'instruction de la pile ou décodez un argument d'instruction situé directement dans le bytecode.
- Effectuez une opération.
- S'il y a un résultat du calcul, mettez-le sur la pile.
- Déplacez le pointeur de l'instruction en cours à la suivante.
La charge utile n'est ici que dans le cinquième paragraphe, le reste est une surcharge: décodage ou récupération des arguments d'instruction de la pile (article 4), vérification de la valeur de l'opcode (article 2), retour à plusieurs reprises au début de la boucle principale et à la transition conditionnelle difficile à prévoir (article 3).
En bref, le porc a clairement dépassé l'indice de masse corporelle recommandé, et si nous voulons le mettre en forme, nous devrons faire face à tous ces excès.
Langage d'assemblage de porcs et tamis d'Eratosthène
Décidons d'abord des règles du jeu.
Écrire des programmes pour une machine virtuelle directement en C est une mauvaise idée, mais la création d'un langage de programmation est longue, nous avons donc décidé de nous limiter à un langage d'assemblage piggy.
Un programme qui calcule la somme des nombres de 1 à 65 536 dans cet assembleur ressemble à ceci:
# sum numbers from 1 to 65535 # init the current sum and the index PUSHI 1 PUSHI 1 # stack s=1, i=1 STOREI 0 # stack: s=1 # routine: increment the counter, add it to the current sum incrementandadd: # check if index is too big LOADI 0 # stack: s, i ADDI 1 # stack: s, i+1 DUP # stack: s, i+1, i+1 GREATER_OR_EQUALI 65535 # stack: s, i+1, 1 or 0 JUMP_IF_TRUE done # stack: s, i+1 DUP # stack: s, i+1, i+1 STOREI 0 # stack: s, i+1 ADD # stack: s+i+1 JUMP incrementandadd done: DISCARD PRINT DONE
Pas Python, bien sûr, mais il y a tout ce dont vous avez besoin pour le bonheur des cochons: commentaires, balises, sauts conditionnels et inconditionnels, des mnémoniques pour les instructions et la possibilité de spécifier des arguments directs aux instructions.
Complet avec la machine "Piglet VM" sont assembleur et démonteur, qui sont courageux dans l'esprit et ont beaucoup de temps libre, les lecteurs peuvent tester indépendamment au combat.
Les chiffres s'additionnent très rapidement, donc pour tester les performances, j'ai écrit un autre programme - une implémentation naïve du tamis d'Eratosthène .
En fait, le porcelet fonctionne de toute façon assez rapidement (ses instructions sont proches de celles de la machine), donc, pour obtenir des résultats clairs, je ferai chaque mesure pour une centaine de démarrages du programme.
La première version de notre porc non optimisé fonctionne comme ceci:
> ./pigletvm runtimes test/sieve-unoptimized.bin 100 > /dev/null PROFILE: switch code finished took 545ms
Une demi-seconde! La comparaison est certainement malhonnête, mais le même algorithme Python fait une centaine de courses un peu plus lentement:
> python test/sieve.py > /dev/null 4.66692185402
4,5 secondes, ou neuf fois plus lentement. Nous devons rendre hommage au porcelet - il en a la capacité! Eh bien, voyons maintenant si notre porc peut gonfler la presse.
Exercice 1: Superinstructions statiques
La première règle du code rapide est de ne pas faire trop de travail. La deuxième règle du code rapide est de ne jamais faire trop de travail. Alors, quel genre de travail supplémentaire fait Piglet VM?
Première observation: le profilage de notre programme montre qu'il existe des séquences d'instructions plus courantes que d'autres. Nous ne tourmenterons pas beaucoup notre cochon et nous limiterons à quelques instructions:
- LOADI 0, ADD - mettez sur la pile un numéro de la mémoire à l'adresse 0 et ajoutez-le au numéro en haut de la pile.
- PUSHI 65536, GREATER_OR_EQUAL - mettez un nombre sur la pile et comparez-le avec le numéro qui était précédemment en haut de la pile, en remettant le résultat de la comparaison (0 ou 1) sur la pile.
- PUSHI 1, ADD - mettez un nombre sur la pile, ajoutez-le au numéro qui était précédemment en haut de la pile et remettez le résultat de l'addition sur la pile.
Il y a un peu plus de 20 instructions dans la machine VM Piglet, et un octet entier est utilisé pour l'encodage - 256 valeurs. L'introduction de nouvelles instructions n'est pas un problème. Ce que nous ferons:
for (;;) { uint8_t instruction = NEXT_OP(); switch (instruction) { case OP_LOADADDI: { uint16_t addr = NEXT_ARG(); uint64_t val = vm.memory[addr]; *TOS_PTR() += val; break; } case OP_GREATER_OR_EQUALI:{ uint64_t arg_right = NEXT_ARG(); *TOS_PTR() = PEEK() >= arg_right; break; } case OP_ADDI: { uint16_t arg_right = NEXT_ARG(); *TOS_PTR() += arg_right; break; } }
Rien de compliqué. Voyons ce qui en est ressorti:
> ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 410ms
Ouah! Le code n'est que pour trois nouvelles instructions, et nous avons gagné une centaine de millisecondes!
Le gain ici est obtenu du fait que notre piggy ne fait pas de mouvements inutiles lors de l'exécution de telles instructions: le thread d'exécution ne tombe pas dans la boucle principale, rien n'est décodé, et les arguments des instructions ne passent pas à nouveau dans la pile.
C'est ce qu'on appelle des superinstructions statiques, car des instructions supplémentaires sont définies statiquement, c'est-à-dire par le programmeur de la machine virtuelle au stade du développement. Il s'agit d'une technique simple et efficace que toutes les machines virtuelles des langages de programmation utilisent sous une forme ou une autre.
Le principal problème des superinstructions statiques est que sans programme spécifique, il est impossible de déterminer quelles instructions doivent être combinées. Différents programmes utilisent différentes séquences d'instructions, et vous ne pouvez découvrir ces séquences qu'au stade du lancement d'un code spécifique.
L'étape suivante pourrait être la compilation dynamique de superinstructions dans le contexte d'un programme spécifique, c'est-à-dire les superinstructions dynamiques (dans les années 90 et au début des années 2000, cette technique jouait le rôle d'une compilation JIT primitive).
Il est impossible de créer des instructions à la volée dans le cadre du C ordinaire, et notre porcelet ne considère pas à juste titre qu'il s'agit d'une compétition honnête. Heureusement, j'ai quelques meilleurs exercices pour lui.
Exercice 2: vérification de la plage de valeurs d'opcode
En suivant nos règles de code rapide, nous nous posons une fois de plus l'éternelle question: que ne pouvez-vous pas faire?
Lorsque nous nous sommes familiarisés avec le périphérique de la machine VM Piglet, j'ai répertorié toutes les actions que la machine virtuelle effectue pour chaque opcode. Et le point 2 (vérifier la valeur de l'opcode pour s'adapter à la plage valide de valeurs de commutateur) est le plus suspect.
Voyons comment GCC compile la construction du commutateur:
- Une table de transition est construite, c'est-à-dire une table qui affiche la valeur de l'opcode à l'adresse du code exécutant le corps de l'instruction.
- Un code est inséré qui vérifie si l'opcode reçu se situe dans la plage de toutes les valeurs de commutateur possibles et l'envoie à l'étiquette par défaut s'il n'y a pas de gestionnaire pour l'opcode.
- Le code qui va au gestionnaire est inséré.
Mais pourquoi vérifier l'intervalle des valeurs pour chaque instruction? Nous pensons que l'opcode est soit correct - mettant fin à l'exécution par l'instruction OP_DONE, soit incorrect - dépassant le bytecode. La queue du flux d'opcodes est marquée par zéro et zéro est l'opcode de l'instruction OP_ABORT, qui termine l'exécution du bytecode avec une erreur.
Il s'avère que ce contrôle n'est pas du tout nécessaire! Et le porcelet devrait être en mesure de transmettre cette idée au compilateur. Essayons de réparer un peu l'interrupteur principal:
uint8_t instruction = NEXT_OP(); switch (instruction & 0x1f) { case 26 ... 0x1f: { return ERROR_UNKNOWN_OPCODE; } }
Sachant que nous n'avons que 26 instructions, nous imposons un masque de bits (la valeur octale 0x1f est un 0b11111 binaire couvrant la plage de valeurs de 0 à 31) sur l'opcode et ajoutons des gestionnaires aux valeurs inutilisées dans la plage de 26 à 31.
Les instructions de bits sont parmi les moins chères de l'architecture x86, et elles sont certainement moins chères que les branches conditionnelles problématiques comme celle qui utilise la vérification d'intervalle. Théoriquement, nous devrions gagner plusieurs cycles sur chaque instruction exécutable si le compilateur comprend notre indice.
Soit dit en passant, la façon de spécifier la plage de valeurs dans le cas n'est pas la norme C, mais une extension GCC. Mais pour nos besoins, ce code convient, d'autant plus qu'il n'est pas difficile de le refaire en plusieurs gestionnaires pour chacune des valeurs inutiles.
Nous essayons:
> ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 437ms PROFILE: switch code (no range check) finished took 383ms
Encore 50 millisecondes! Porcelet, c'est comme si vous vous entendiez dans vos épaules! ..
Exercice trois: sentiers
Quels autres exercices peuvent aider notre porcelet? Le plus grand gain de temps que nous avons obtenu grâce aux super instructions. Et ils réduisent le nombre de sorties du cycle principal et vous permettent de vous débarrasser des frais généraux correspondants.
Le commutateur central est le principal problème pour tout processeur avec une exécution extraordinaire des instructions. Les prédicteurs de branche modernes ont appris à bien prédire même des transitions indirectes aussi complexes, mais "étaler" les points de branche le long du code peut aider le processeur à passer rapidement d'une instruction à l'autre.
Un autre problème est la lecture octet par octet des opcodes d'instructions et des arguments directs à partir du bytecode. Les machines physiques fonctionnent avec un mot machine 64 bits et ne l'aiment pas vraiment lorsque le code fonctionne avec des valeurs inférieures.
Les compilateurs fonctionnent souvent avec des blocs de base , c'est-à-dire des séquences d'instructions sans branches ni étiquettes à l'intérieur. Le bloc de base commence soit au début du programme, soit à partir de l'étiquette, et se termine par la fin du programme, une ramification conditionnelle ou un saut direct à l'étiquette qui démarre le bloc de base suivant.
Il y a de nombreux avantages à travailler avec des unités de base, mais notre porc s'intéresse à sa caractéristique clé: les instructions au sein de l'unité de base sont exécutées séquentiellement. Ce serait génial d'isoler ces blocs de base et de suivre les instructions qu'ils contiennent sans perdre de temps à entrer dans la boucle principale.
Dans notre cas, vous pouvez même étendre la définition de l'unité de base à la piste. La piste en termes de machine Piglet VM comprendra tous les blocs de base connectés séquentiellement (c'est-à-dire en utilisant des sauts inconditionnels).
En plus de l'exécution séquentielle des instructions, il serait bien de décoder à l'avance les arguments directs des instructions.
Tout cela semble assez effrayant et ressemble à une compilation dynamique, que nous avons décidé de ne pas utiliser. Le cochon doutait même un peu de sa force, mais en pratique, cela ne s'est pas avéré si mauvais.
Réfléchissons d'abord à la façon dont vous pouvez imaginer les instructions incluses dans la piste:
struct scode { uint64_t arg; trace_op_handler *handler; };
Ici arg est l'argument pré-décodé de l'instruction, et handler est un pointeur vers une fonction qui exécute la logique de l'instruction.
Maintenant, la vue de chaque trace ressemble à ceci:
typedef scode trace[MAX_TRACE_LEN];
Autrement dit, une trace est une séquence de codes s de longueur limitée. Le cache de trace lui-même à l'intérieur de la machine virtuelle ressemble à ceci:
trace trace_cache[MAX_CODE_LEN];
Il s'agit simplement d'un tableau de traces dont la longueur ne dépasse pas la longueur de bytecode possible. La solution est paresseuse, afin d'économiser de la mémoire, il est logique d'utiliser une table de hachage.
Au début de l'interpréteur, le premier gestionnaire de chaque trace se compilera:
for (size_t trace_i = 0; trace_i < MAX_CODE_LEN; trace_i++ ) vm_trace.trace_cache[trace_i][0].handler = trace_compile_handler;
La boucle d'interpréteur principale ressemble maintenant à ceci:
while(vm_trace.is_running) { scode *code = &vm_trace.trace_cache[vm_trace.pc][0]; code->handler(code); }
Un compilateur de trace est un peu plus compliqué, et en plus de construire une trace à partir de l'instruction courante, il fait ce qui suit:
static void trace_compile_handler(scode *trace_head) { scode *trace_tail = trace_head; trace_head->handler(trace_head); }
Gestionnaire d'instructions normal:
static void op_add_handler(scode *code) { uint64_t arg_right = POP(); *TOS_PTR() += arg_right; code++; code->handler(code); }
Un gestionnaire qui ne fait aucun appel à la fin de la fonction termine chaque trace:
static void op_done_handler(scode *code) { (void) code; vm_trace.is_running = false; vm_trace.error = SUCCESS; }
Tout cela, bien sûr, est plus compliqué que l'ajout de superinstructions, mais voyons si cela nous a donné quelque chose:
> ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 427ms PROFILE: switch code (no range check) finished took 395ms PROFILE: trace code finished took 367ms
Vive, encore 30 millisecondes!
Comment ça? Au lieu de simplement naviguer dans les étiquettes, nous créons des chaînes d'appels de gestionnaires d'instructions, passons du temps sur les appels et passons des arguments, mais notre piggy parcourt toujours les pistes plus rapidement qu'un simple commutateur avec ses étiquettes.
Ce gain de performances sur piste est dû à trois facteurs:
- Il est facile de prédire les branches dispersées à différents endroits du code.
- Les arguments des gestionnaires sont toujours pré-encodés en un mot machine complet, et cela n'est fait qu'une seule fois - lors de la compilation de la trace.
- Le compilateur transforme les chaînes de fonctions en un seul appel vers la première fonction de gestionnaire, ce qui est possible grâce à l'optimisation de l' appel de queue .
Avant de résumer les résultats de notre formation, le porcelet et moi avons décidé d'essayer une autre technique ancienne d'interprétation des programmes - le code cousu.
Exercice 4: code "cousu"
Tout cochon intéressé par l'histoire des interprètes a entendu un code fileté. Il existe de nombreuses options pour cette technique, mais elles se résument toutes à au lieu de suivre un tableau d'opcodes, en suivant un tableau, par exemple, des pointeurs vers des fonctions ou des étiquettes, en les suivant directement sans opcode intermédiaire.
Appeler des fonctions est une entreprise coûteuse et dénuée de sens de nos jours; la plupart des autres versions du code cousu sont irréalisables dans le cadre de la norme C. Même la technique, qui sera discutée ci-dessous, utilise l'extension C répandue, mais non standard, des pointeurs C vers les étiquettes.
Dans la version du code cousu (code fileté de jeton anglais) que j'ai choisi pour atteindre nos objectifs de cochon, nous enregistrons le bytecode, mais avant de commencer l'interprétation, nous créons un tableau qui affiche les opcodes d'instructions à l'adresse des étiquettes du gestionnaire d'instructions:
const void *labels[] = { [OP_PUSHI] = &&op_pushi, [OP_LOADI] = &&op_loadi, [OP_LOADADDI] = &&op_loadaddi, [OP_STORE] = &&op_store, [OP_STOREI] = &&op_storei, [OP_LOAD] = &&op_load, [OP_DUP] = &&op_dup, [OP_DISCARD] = &&op_discard, [OP_ADD] = &&op_add, [OP_ADDI] = &&op_addi, [OP_SUB] = &&op_sub, [OP_DIV] = &&op_div, [OP_MUL] = &&op_mul, [OP_JUMP] = &&op_jump, [OP_JUMP_IF_TRUE] = &&op_jump_if_true, [OP_JUMP_IF_FALSE] = &&op_jump_if_false, [OP_EQUAL] = &&op_equal, [OP_LESS] = &&op_less, [OP_LESS_OR_EQUAL] = &&op_less_or_equal, [OP_GREATER] = &&op_greater, [OP_GREATER_OR_EQUAL] = &&op_greater_or_equal, [OP_GREATER_OR_EQUALI] = &&op_greater_or_equali, [OP_POP_RES] = &&op_pop_res, [OP_DONE] = &&op_done, [OP_PRINT] = &&op_print, [OP_ABORT] = &&op_abort, };
Faites attention aux symboles && - ce sont des pointeurs vers des étiquettes avec le corps des instructions, l'extension la plus non standard de GCC.
Pour commencer à exécuter le code, cliquez simplement sur le pointeur correspondant au premier opcode du programme:
goto *labels[NEXT_OP()];
Il n'y a pas de cycle ici et il n'y en aura pas, chacune des instructions elle-même fait un saut au gestionnaire suivant:
op_pushi: { uint16_t arg = NEXT_ARG(); PUSH(arg); goto *labels[NEXT_OP()]; }
L'absence d'un commutateur «répartit» les points de branchement le long des corps d'instructions, ce qui devrait en théorie aider le prédicteur de branchement en cas d'exécution extraordinaire des instructions. C'est comme si nous avions intégré le commutateur directement dans les instructions et formé manuellement une table de transition.
C'est toute la technique. Elle aimait le porcelet pour sa simplicité. Voyons ce qui se passe dans la pratique:
> ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 443ms PROFILE: switch code (no range check) finished took 389ms PROFILE: threaded code finished took 477ms PROFILE: trace code finished took 364ms
Oups! C'est la plus lente de toutes nos techniques! Que s'est-il passé? Exécutons les mêmes tests, désactivant toutes les optimisations GCC:
> ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 969ms PROFILE: switch code (no range check) finished took 940ms PROFILE: threaded code finished took 824ms PROFILE: trace code finished took 1169ms
Ici, le code cousu fonctionne mieux.
Trois facteurs jouent ici un rôle:
- Le compilateur d'optimisation lui-même va construire une table de conversion pas pire que notre plaque d'étiquette manuelle.
- Les compilateurs modernes se débarrassent remarquablement des appels de fonctions supplémentaires.
- À partir de la génération Haswell de processeurs Intel, les prédicteurs de branche ont appris à prédire avec précision les transitions à travers un seul point de branche.
Selon l'ancienne mémoire, cette technique est encore utilisée dans le code de, par exemple, l'interpréteur Python VM, mais, franchement, de nos jours, c'est déjà de l'archaïsme.
Résumons et évaluons enfin les succès obtenus par notre porc.
Débriefing
Je ne sais pas trop comment cela peut être appelé un vol, mais avouons-le, notre cochon a parcouru un long chemin de 550 millisecondes pour une centaine de courses sur le "tamis" aux 370 millisecondes finales. Nous avons utilisé différentes techniques: super-instructions, se débarrasser de la vérification des intervalles de valeurs, mécanique compliquée des traces et, enfin, même code cousu. Dans le même temps, nous avons, en général, agi dans le cadre des choses implémentées dans tous les compilateurs C populaires. L'accélération d'une fois et demie, comme il me semble, est un bon résultat, et le porcelet mérite une portion supplémentaire de son dans l'auge.
L'une des conditions implicites que nous nous sommes fixées avec le cochon est de préserver l'architecture de pile de la machine VM Piglet. La transition vers une architecture de registre, en règle générale, réduit le nombre d'instructions nécessaires à la logique des programmes et, en conséquence, peut aider à éliminer les sorties inutiles du gestionnaire d'instructions. Je pense que 10 à 20% du temps pourrait être interrompu.
Notre principale condition - le manque de compilation dynamique - n'est pas non plus une loi de la nature. Pomper un cochon avec des stéroïdes sous forme de compilation JIT est très facile de nos jours: dans des bibliothèques comme GNU Lightning ou LibJIT, tout le sale boulot a déjà été fait. Mais le temps de développement et la quantité totale de code même en utilisant des bibliothèques augmentent énormément.
Il y a, bien sûr, d'autres astuces auxquelles notre petit cochon n'a pas atteint le sabot. , — - — - . , .
PS , , , , ( https://www.instagram.com/vovazomb/ ), .
PPS , . true-grue - — PigletC . !
PPPS iliazeus : . ; . .