Máquinas virtuais de linguagens de programação se tornaram muito difundidas nas últimas décadas. Muito tempo se passou desde a apresentação da Java Virtual Machine na segunda metade dos anos 90, e é seguro dizer que os intérpretes de código de bytes não são o futuro, mas o presente.
Mas essa técnica, na minha opinião, é quase universal, e o entendimento dos princípios básicos do desenvolvimento de intérpretes é útil não apenas para o criador do próximo desafiante do título "Linguagem do Ano" de acordo com o TIOBE , mas para qualquer programador em geral.
Em uma palavra, se você estiver interessado em aprender como nossas linguagens de programação favoritas somam números, sobre o que os desenvolvedores de máquinas virtuais ainda estão discutindo e sobre como combinar strings e expressões regulares sem problemas, peço cat.
Parte um, introdutória (atual)
Parte Dois, Otimizando
Parte Três, Aplicada
Antecedentes
Um dos sistemas auto-escritos do departamento de Business Intelligence da nossa empresa possui uma interface na forma de uma linguagem de consulta simples. Na primeira versão do sistema, esse idioma foi interpretado em tempo real, sem compilação, diretamente da linha de entrada com a solicitação. A segunda versão do analisador já funcionará com bytecode intermediário, o que permitirá que você separe o idioma da consulta da execução deles e simplifique bastante o código.
No processo de trabalhar na segunda versão do sistema, tive férias durante as quais, durante uma ou duas horas todos os dias, me distraí dos assuntos da família para estudar materiais sobre a arquitetura e o desempenho dos intérpretes de bytecode. Decidi compartilhar as notas e exemplos de intérpretes resultantes com os leitores de Habr como uma série de artigos.
O primeiro deles apresenta cinco máquinas virtuais pequenas (até centenas de linhas de código C simples), cada uma das quais revela um certo aspecto do desenvolvimento de tais intérpretes.
Para onde foram os códigos de bytes nas linguagens de programação?
Muitas máquinas virtuais, os mais diversos conjuntos de instruções virtuais nas últimas décadas, foram inventados. A Wikipedia afirma que as primeiras linguagens de programação começaram a se compilar em várias representações intermediárias simplificadas nos anos 60 do século passado. Alguns desses códigos de primeiro byte foram convertidos em códigos de máquina e executados por processadores reais, enquanto outros foram interpretados em tempo real por processadores virtuais.
A popularidade dos conjuntos de instruções virtuais como uma representação intermediária do código se deve a três razões:
- Os programas de bytecode são facilmente portados para novas plataformas.
- Os intérpretes de bytecode são mais rápidos que os intérpretes da árvore de código da sintaxe.
- Você pode desenvolver uma máquina virtual simples em apenas algumas horas.
Vamos criar algumas máquinas virtuais C simples e usar esses exemplos para destacar os principais aspectos técnicos da implementação de máquinas virtuais.
Códigos de amostra completos estão disponíveis no GitHub . Exemplos podem ser compilados com qualquer GCC relativamente recente:
gcc interpreter-basic-switch.c -o interpreter ./interpreter
Todos os exemplos têm a mesma estrutura: primeiro vem o código da própria máquina virtual, depois a função principal com asserções que verificam a operação do código. Tentei comentar claramente os códigos de operação e os principais locais dos intérpretes. Espero que este artigo seja compreensível até para as pessoas que não escrevem em C diariamente.
O interpretador de bytecodes mais fácil do mundo
Como eu disse, o intérprete mais simples é muito fácil de fazer. Os comentários estão logo atrás da lista, mas vamos começar diretamente com o código:
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; }
Existem menos de cem linhas, mas todos os atributos característicos de uma máquina virtual são representados. A máquina possui um único registro ( vm.accumulator ), três operações (incremento do registro, decremento do registro e conclusão da execução do programa) e um ponteiro para a instrução atual ( vm.ip ).
Cada operação (por exemplo, código de operação ou opcode ) é codificada com um byte e o agendamento é realizado usando a switch usual na função vm_interpret . As ramificações no switch contêm a lógica das operações, ou seja, elas alteram o estado do registro ou encerram a execução do programa.
As operações são transferidas para a função vm_interpret na forma de uma matriz de bytes - um bytecode (Eng. Bytecode ) - e são executadas sequencialmente até que a operação de OP_DONE máquina virtual ( OP_DONE ) seja OP_DONE .
Um aspecto fundamental de uma máquina virtual é a semântica, ou seja, o conjunto de operações que são possíveis nela. Nesse caso, existem apenas duas operações e elas alteram o valor de um único registro.
Alguns pesquisadores ( Técnicas de Abstração e Otimização de Máquinas Virtuais , 2009) propõem a divisão de máquinas virtuais em máquinas de alto e baixo nível, de acordo com a proximidade da semântica da máquina virtual com a semântica da máquina física na qual o bytecode será executado.
No caso extremo, o bytecode de máquinas virtuais de baixo nível pode repetir completamente o código da máquina física com RAM simulada, um conjunto completo de registros, instruções para trabalhar com a pilha e assim por diante. A máquina virtual Bochs , por exemplo, repete o conjunto de instruções da arquitetura x86.
E vice-versa: as operações de máquinas virtuais de alto nível refletem de perto a semântica de uma linguagem de programação especializada compilada no bytecode. Então trabalhe, por exemplo, SQLite, Gawk e várias versões do Prolog.
As posições intermediárias são ocupadas por intérpretes de linguagens de programação de uso geral, com elementos de níveis alto e baixo. A Java Virtual Machine mais popular possui instruções de baixo nível para trabalhar com a pilha e suporte interno para programação orientada a objetos com alocação automática de memória.
É mais provável que o código acima seja a mais primitiva das máquinas virtuais de baixo nível: cada instrução virtual é um invólucro com uma ou duas instruções físicas, o registro virtual é totalmente consistente com um registro do processador "iron".
Argumentos de instrução de bytecode
Podemos dizer que o único registro em nosso exemplo de máquina virtual é um argumento e o valor de retorno de todas as instruções executadas. No entanto, podemos achar útil passar argumentos nas instruções. Uma maneira é colocá-los diretamente no bytecode.
Expandiremos o exemplo introduzindo instruções (OP_ADDI, OP_SUBI) que recebem um argumento na forma de um byte imediatamente após o código de operação:
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; }
Novas instruções (consulte a função vm_interpret ) leem seu argumento do bytecode e o adicionam ao registro / subtraem-no do registro.
Esse argumento é chamado de argumento imediato , porque está localizado diretamente na matriz opcode. A principal limitação em nossa implementação é que o argumento é um byte único e pode levar apenas 256 valores.
Em nossa máquina virtual, o intervalo de possíveis valores de argumentos de instruções não desempenha um grande papel. Mas se a máquina virtual for usada como intérprete da linguagem real, faz sentido complicar o bytecode adicionando uma tabela de constantes separada da matriz de opcodes e instruções com um argumento direto correspondente ao endereço desse argumento na tabela de constantes.
Máquina de empilhar
As instruções em nossa máquina virtual simples sempre funcionam com um registro e não podem transmitir dados entre si de forma alguma. Além disso, o argumento para a instrução só pode ser imediato e, digamos, a operação de adição ou multiplicação leva dois argumentos.
Simplificando, não temos como avaliar expressões complexas. Para resolver esse problema, é necessária uma máquina empilhada, ou seja, uma máquina virtual com uma pilha integrada:
#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; }
Neste exemplo, já existem mais operações e quase todas funcionam apenas com a pilha. OP_PUSHI coloca seu argumento imediato na pilha. As instruções OP_ADD, OP_SUB, OP_DIV, OP_MUL são exibidas de uma pilha de valores, calculam o resultado e empurram-no de volta para a pilha. OP_POP_RES remove o valor da pilha e o coloca no registro de resultados, destinado aos resultados da máquina virtual.
Para a operação de divisão (OP_DIV), um erro de divisão por zero é capturado, o que para a máquina virtual.
As capacidades dessa máquina são muito mais amplas do que a anterior com um único registro e permitem, por exemplo, calcular expressões aritméticas complexas. Outra vantagem (e importante!) É a simplicidade de compilar linguagens de programação no código de bytes da máquina de empilhamento.
Registrar máquina
Devido à sua simplicidade, as máquinas virtuais empilhadas são mais amplamente usadas entre os desenvolvedores de linguagens de programação; as mesmas VMs JVMs e Python as usam exatamente.
No entanto, essas máquinas têm desvantagens: elas precisam adicionar instruções especiais para trabalhar com a pilha; ao calcular expressões, todos os argumentos passam repetidamente por uma única estrutura de dados; muitas instruções extras aparecerão inevitavelmente no código da pilha.
Enquanto isso, a execução de cada instrução extra implica o custo da programação, isto é, decodificar o código de operação e mudar para o corpo das instruções.
Uma alternativa para máquinas empilhadas é registrar máquinas virtuais. Eles têm um bytecode mais complexo: o número de argumentos do registro e o número do resultado do registro são codificados explicitamente em cada instrução. Portanto, em vez de uma pilha, um conjunto estendido de registros é usado como armazenamento de valores intermediários.
#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; }
O exemplo mostra uma máquina de registro com 16 registros. As instruções ocupam 16 bits cada e são codificadas de três maneiras:
- 4 bits por código de operação + 4 bits por nome de registro + 8 bits por argumento.
- 4 bits por código de operação + três vezes 4 bits por nomes de registro.
- 4 bits por código de operação + 4 bits por nome de registro único + 8 bits não utilizados.
Nossa pequena máquina virtual possui muito poucas operações, portanto, quatro bits (ou 16 operações possíveis) por código de operação são suficientes. A operação determina o que exatamente os bits restantes da instrução representam.
O primeiro tipo de codificação (4 + 4 + 8) é necessário para carregar dados nos registradores com a operação OP_LOADI. O segundo tipo (4 + 4 + 4 + 4) é usado para operações aritméticas, que devem saber onde levar um par de argumentos e onde adicionar o resultado do cálculo. E finalmente, a última forma (4 + 4 + 8 bits desnecessários) é usada para instruções com um único registro como argumento, no nosso caso é OP_MOV_RES.
Para codificar e decodificar instruções, agora precisamos de lógica especial (função de decode ). Por outro lado, a lógica das instruções, graças à indicação explícita da localização dos argumentos, fica mais fácil - as operações com a pilha desaparecem.
Recursos principais: no bytecode das máquinas de registro, há menos instruções, instruções individuais são mais amplas, a compilação nesse bytecode é mais difícil - o compilador precisa decidir como usar os registros disponíveis.
Deve-se notar que, na prática, no registro de máquinas virtuais, geralmente há uma pilha em que, por exemplo, argumentos de função são colocados; registradores são usados para calcular expressões individuais. Mesmo se não houver pilha explícita, uma matriz é usada para construir a pilha, desempenhando o mesmo papel que a RAM em máquinas físicas.
Máquinas de empilhar e registrar, comparação
Há um estudo interessante ( confrontação de máquinas virtuais: Stack versus registradores , 2008) que teve uma grande influência em todos os desenvolvimentos subsequentes no campo de máquinas virtuais para linguagens de programação. Seus autores propuseram um método de tradução direta do código de pilha de uma JVM padrão para um código de registro e compararam o desempenho.
O método não é trivial: o código é primeiro traduzido e depois otimizado de uma maneira bastante complicada. Porém, uma comparação subsequente do desempenho do mesmo programa mostrou que os ciclos adicionais do processador gastos em instruções de decodificação são totalmente compensados por uma diminuição no número total de instruções. Em geral, em resumo, a máquina registradora era mais eficiente que a pilha.
Como já mencionado acima, essa eficiência tem um preço bastante tangível: o compilador deve alocar os próprios registros e um otimizador avançado é adicionalmente desejável.
O debate sobre qual arquitetura é melhor ainda não acabou. Se falamos de compiladores Java, o bytecode da Dalvik VM, que até recentemente funcionava em todos os dispositivos Android, era registrado; mas o título JVM manteve uma pilha de instruções. A máquina virtual Lua usa uma máquina de registro, mas a VM Python ainda é empilhável. E assim por diante
Bytecode em intérpretes de expressão regular
Por fim, para nos distrair das máquinas virtuais de baixo nível, vejamos um intérprete especializado que verifica as seqüências de caracteres quanto à correspondência de expressões regulares:
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); }
A instrução principal é OP_CHAR. Ela pega seu argumento imediato e o compara com o caractere atual na string ( char *sp ). Em caso de coincidência dos caracteres esperados e atuais na linha, faça a transição para a próxima instrução e o próximo caractere.
A máquina também entende a operação de salto (OP_JUMP), que usa um único argumento imediato. O argumento significa o deslocamento absoluto no bytecode, de onde continuar o cálculo.
A última operação importante é OP_OR. Ela pega duas compensações, tentando aplicar o código primeiro na primeira delas e, em caso de erro, na segunda. Ela faz isso com uma chamada recursiva, ou seja, a instrução faz uma caminhada na profundidade da árvore de todas as variantes possíveis da expressão regular.
Surpreendentemente, quatro opcodes e setenta linhas de código são suficientes para expressar expressões regulares como "abc", "a? Bc", "(ab | bc) d", "a * bc". Essa máquina virtual nem sequer tem um estado explícito, pois tudo o que você precisa - ponteiros para o início do fluxo de instruções, a instrução atual e o caractere atual - é passado como argumento para a função recursiva.
Se você estiver interessado nos detalhes do trabalho dos mecanismos de expressão regular, primeiro leia uma série de artigos de Russ Cox, autor do mecanismo de expressão regular do Google RE2 .
Sumário
Vamos resumir.
Para linguagens de programação de uso geral, como regra, duas arquiteturas são usadas: empilhar e registrar.
No modelo de pilha, a estrutura de dados principal e o método de transmissão de argumentos entre instruções é a pilha. No modelo de registro, um conjunto de registros é usado para calcular expressões, mas uma pilha explícita ou implícita ainda é usada para armazenar argumentos de função.
A presença de uma pilha explícita e de um conjunto de registros aproxima essas máquinas das de baixo nível e até físicas. A abundância de instruções de baixo nível nesse código de bytes significa que um gasto significativo de recursos do processador físico recai na decodificação e programação de instruções virtuais.
Por outro lado, as instruções de alto nível desempenham um papel importante nas máquinas virtuais populares. Em Java, por exemplo, estas são instruções para chamadas de funções polimórficas, alocação de objetos e coleta de lixo.
Máquinas virtuais puramente de alto nível - por exemplo, intérpretes de códigos de bytes de linguagens com semântica desenvolvida e distante do ferro - passam a maior parte do tempo não no expedidor ou decodificador, mas no corpo das instruções e, portanto, são relativamente eficientes.
Recomendações práticas:
- Se você precisar executar qualquer bytecode e fazê-lo em um período de tempo razoável, tente operar com as instruções mais próximas da sua tarefa; quanto maior o nível semântico, melhor. Isso reduzirá os custos de agendamento e simplificará a geração de código.
- Se você precisar de mais flexibilidade e semântica heterogênea, tente pelo menos destacar o denominador comum no código de bytes para que as instruções resultantes estejam em um nível médio condicional.
- Se, no futuro, for necessário calcular qualquer expressão, criar uma máquina empilhada, isso reduzirá a dor de cabeça ao compilar o código de bytes.
- Se expressões não forem esperadas, crie uma máquina de registro trivial, que evitará o custo da pilha e simplificará as instruções.
Nos artigos a seguir, discutirei implementações práticas de máquinas virtuais em linguagens de programação populares e explicarei por que o departamento de Business Intelligence Badoo precisava de um bytecode.