"Não importa o quanto você tente, você não pode fazer um cavalo de corrida com um porco. Você pode, no entanto, fazer um porco mais rápido" (comentário no código fonte do Emax)
Todo mundo sabe que os porcos não voam. Não menos popular é a opinião de que os intérpretes de bytecode como uma técnica para executar linguagens de alto nível não podem ser acelerados sem o uso de compilação dinâmica demorada.
Na segunda parte de uma série de artigos sobre intérpretes de bytecode, tentarei mostrar pelo exemplo de uma pequena máquina virtual da FDA empilhada (Pig Virtual Machine) que nem tudo está perdido para leitões trabalhadores com ambições e que é bem possível acelerar dentro da estrutura (principalmente) do padrão C o trabalho de tais intérpretes é pelo menos uma vez e meia.
Parte I, Introdutória
Parte dois, otimizando (atual)
Parte Três, Aplicada
Leitão
Vamos nos familiarizar.
O Piglet VM é uma máquina empilhada comum, baseada em um exemplo da primeira parte de uma série de artigos. Nosso porco conhece apenas um tipo de dados - uma palavra de máquina de 64 bits, e todos os cálculos (inteiros) são realizados na pilha com uma profundidade máxima de 256 palavras de máquina. Além da pilha, este leitão tem uma memória de trabalho de 65.536 palavras de máquina. O resultado da execução do programa - uma palavra de máquina - pode ser colocado no registro de resultados ou simplesmente gerar a saída padrão (stdout).
Todo o estado na máquina Piglet VM é armazenado em uma única estrutura:
static struct { uint8_t *ip; uint64_t stack[STACK_MAX]; uint64_t *stack_top; uint64_t memory[MEMORY_SIZE]; uint64_t result; } vm;
O exposto acima nos permite atribuir essa máquina a máquinas virtuais de baixo nível, quase toda a sobrecarga na qual recai a manutenção do ciclo principal do programa:
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; }
O código mostra que, para cada código de operação, o piggy deve:
- Recupere o código de operação do fluxo de instruções.
- Verifique se o código de operação está no intervalo válido de valores de código de operação (essa lógica é adicionada pelo compilador C ao gerar o código do comutador).
- Vá para as instruções do corpo.
- Extraia argumentos de instrução da pilha ou decodifique um argumento de instrução localizado diretamente no bytecode.
- Realize uma operação.
- Se houver um resultado do cálculo, coloque-o na pilha.
- Mova o ponteiro da instrução atual para a próxima.
A carga útil aqui está apenas no quinto parágrafo, o restante está sobrecarregado: decodificando ou recuperando os argumentos de instrução da pilha (cláusula 4), verificando o valor do opcode (cláusula 2), retornando repetidamente para o início do loop principal e a subsequente transição condicional dificilmente prevista (cláusula 3).
Em suma, o porco excedeu claramente o índice de massa corporal recomendado e, se quisermos moldá-lo, teremos que lidar com todos esses excessos.
Linguagem de montagem de suínos e peneira de Eratóstenes
Primeiro, vamos decidir sobre as regras do jogo.
Escrever programas para uma máquina virtual diretamente em C é uma péssima idéia, mas criar uma linguagem de programação é um longo tempo, por isso decidimos nos limitar a uma linguagem assembly piggy.
Um programa que calcula a soma dos números de 1 a 65.536 neste montador se parece com isso:
# 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
Não é Python, é claro, mas há tudo o que você precisa para a felicidade dos porcos: comentários, tags, saltos condicionais e incondicionais, mnemônicos para instruções e a capacidade de especificar argumentos diretos para as instruções.
Completo com a máquina "Piglet VM", são montadores e desmontadores, que são corajosos em espírito e têm muito tempo livre, os leitores podem testar independentemente em batalha.
Os números se somam muito rapidamente, então, para testar o desempenho, escrevi outro programa - uma implementação ingênua da peneira de Eratóstenes .
De fato, o leitão corre muito rápido de qualquer maneira (suas instruções estão próximas das da máquina); portanto, para obter resultados claros, eu farei cada medição para cem partidas do programa.
A primeira versão do nosso porco não otimizado funciona assim:
> ./pigletvm runtimes test/sieve-unoptimized.bin 100 > /dev/null PROFILE: switch code finished took 545ms
Meio segundo! A comparação é certamente desonesta, mas o mesmo algoritmo Python torna centenas de execuções um pouco mais lentas:
> python test/sieve.py > /dev/null 4.66692185402
4,5 segundos ou nove vezes mais lento. Devemos prestar homenagem ao leitão - ele tem a capacidade! Bem, agora vamos ver se o nosso porco pode bombear a prensa.
Exercício Um: Superinstruções Estáticas
A primeira regra do código rápido é não fazer muito trabalho. A segunda regra do código rápido é nunca fazer muito trabalho. Então, que tipo de trabalho extra o Piglet VM faz?
Observação um: criar um perfil do nosso programa mostra que existem sequências de instruções mais comuns que outras. Não atormentaremos muito nosso porco e nos restringiremos apenas a algumas instruções:
- LOADI 0, ADICIONAR - coloque na pilha um número da memória no endereço 0 e adicione-o ao número no topo da pilha.
- PUSHI 65536, GREATER_OR_EQUAL - coloque um número na pilha e compare-o com o número que estava anteriormente no topo da pilha, colocando o resultado da comparação (0 ou 1) de volta na pilha.
- PUSHI 1, ADD - coloque um número na pilha, adicione-o ao número que estava anteriormente no topo da pilha e coloque o resultado da adição novamente na pilha.
Há pouco mais de 20 instruções na máquina Piglet VM e um byte inteiro é usado para codificação - 256 valores. A introdução de novas instruções não é um problema. O que faremos:
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; } }
Nada complicado. Vamos ver o que aconteceu:
> ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 410ms
Uau! O código é apenas para três novas instruções, e ganhamos um milhão e meio de milissegundos!
O ganho aqui é alcançado devido ao fato de nosso porquinho não fazer movimentos desnecessários ao executar essas instruções: o segmento de execução não cai no loop principal, nada é decodificado e os argumentos das instruções não voltam a ser empilhados novamente.
Isso é chamado de superinstruções estáticas, pois instruções adicionais são definidas estaticamente, ou seja, pelo programador da máquina virtual no estágio de desenvolvimento. Essa é uma técnica simples e eficaz que todas as máquinas virtuais de linguagens de programação usam de uma forma ou de outra.
O principal problema das superinstruções estáticas é que, sem um programa específico, é impossível determinar quais instruções devem ser combinadas. Programas diferentes usam sequências de instruções diferentes e você pode descobrir essas sequências apenas no estágio de lançamento de um código específico.
O próximo passo pode ser a compilação dinâmica de superinstruções no contexto de um programa específico, ou seja, superinstruções dinâmicas (nos anos 90 e início dos anos 2000, essa técnica desempenhou o papel de uma compilação JIT primitiva).
É impossível criar instruções em tempo real no âmbito do C comum, e nosso leitão com razão não considera isso uma competição honesta. Felizmente, tenho alguns exercícios melhores para ele.
Exercício dois: verificando o intervalo de valores do código de operação
Seguindo nossas regras rápidas de código, mais uma vez nos perguntamos a eterna pergunta: o que você não pode fazer?
Quando nos familiarizamos com o dispositivo da máquina VM Piglet, listei todas as ações que a máquina virtual executa para cada código de operação. E o ponto 2 (verificar o valor do código de operação para ajustar-se ao intervalo válido de valores do comutador) é o mais suspeito.
Vamos dar uma olhada em como o GCC compila a construção do switch:
- Uma tabela de transição é construída, ou seja, uma tabela que exibe o valor do código de operação para o endereço do código que executa o corpo da instrução.
- É inserido um código que verifica se o código de operação recebido está dentro do intervalo de todos os valores possíveis do comutador e o envia para o rótulo padrão se não houver manipulador para o código de operação.
- O código que vai para o manipulador é inserido.
Mas por que verificar o intervalo de valores para cada instrução? Acreditamos que o opcode está correto - terminando a execução pela instrução OP_DONE ou incorreto - indo além do bytecode. A cauda do fluxo de códigos de operação é marcada com zero e zero é o código de operação da instrução OP_ABORT, que completa a execução do bytecode com um erro.
Acontece que essa verificação não é necessária! E o leitão deve ser capaz de transmitir essa idéia ao compilador. Vamos tentar consertar um pouco o switch principal:
uint8_t instruction = NEXT_OP(); switch (instruction & 0x1f) { case 26 ... 0x1f: { return ERROR_UNKNOWN_OPCODE; } }
Sabendo que temos apenas 26 instruções, impomos uma máscara de bit (o valor octal 0x1f é um 0b11111 binário que cobre o intervalo de valores de 0 a 31) no código de operação e adicionamos manipuladores a valores não utilizados no intervalo de 26 a 31.
As instruções de bits são algumas das mais baratas da arquitetura x86 e certamente são mais baratas que as ramificações condicionais problemáticas, como a que usa a verificação de intervalo. Teoricamente, devemos ganhar vários ciclos em cada instrução executável se o compilador entender nossa dica.
A propósito, a maneira de especificar o intervalo de valores no caso não é C padrão, mas uma extensão do GCC. Mas, para nossos propósitos, esse código é adequado, principalmente porque não é difícil refazê-lo em vários manipuladores para cada um dos valores desnecessários.
Tentamos:
> ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 437ms PROFILE: switch code (no range check) finished took 383ms
Mais 50 milissegundos! Leitão, é como se você se ouvisse nos seus ombros!
Exercício Três: Trilhas
Que outros exercícios podem ajudar nosso leitão? A maior economia de tempo que obtivemos graças a super instruções. E eles reduzem o número de saídas para o ciclo principal e permitem que você se livre dos custos indiretos correspondentes.
O switch central é o principal problema para qualquer processador, com uma execução extraordinária de instruções. Os preditores modernos de ramificação aprenderam a prever bem até mesmo tais transições indiretas complexas, mas "borrar" pontos de ramificação ao longo do código pode ajudar o processador a mudar rapidamente de instrução para instrução.
Outro problema é a leitura byte a byte dos opcodes de instruções e argumentos diretos do bytecode. Máquinas físicas operam com uma palavra de máquina de 64 bits e realmente não gostam quando o código opera com valores mais baixos.
Os compiladores geralmente operam com blocos básicos , ou seja, sequências de instruções sem ramificações e rótulos dentro. O bloco base inicia no início do programa ou no rótulo e termina com o final do programa, ramificação condicional ou um salto direto para o rótulo que inicia o próximo bloco base.
Há muitas vantagens em trabalhar com unidades de base, mas nosso porco está interessado em sua característica principal: as instruções dentro da unidade de base são executadas sequencialmente. Seria ótimo isolar esses blocos de base e seguir as instruções neles sem perder tempo entrando no loop principal.
No nosso caso, você pode até estender a definição da unidade base para a pista. A faixa em termos da máquina Piglet VM incluirá todos os blocos de base conectados sequencialmente (ou seja, usando saltos incondicionais).
Além da execução seqüencial de instruções, seria bom decodificar os argumentos diretos das instruções com antecedência.
Tudo soa bem assustador e se assemelha a uma compilação dinâmica, que decidimos não usar. O porco até duvidou um pouco de sua força, mas na prática não ficou tão ruim.
Vamos primeiro pensar em como você pode imaginar as instruções incluídas na faixa:
struct scode { uint64_t arg; trace_op_handler *handler; };
Aqui arg é o argumento pré-decodificado da instrução e handler é um ponteiro para uma função que executa a lógica da instrução.
Agora, a visualização de cada rastreamento é assim:
typedef scode trace[MAX_TRACE_LEN];
Ou seja, um rastreio é uma sequência de códigos s de comprimento limitado. O próprio cache de rastreamento dentro da máquina virtual é semelhante a este:
trace trace_cache[MAX_CODE_LEN];
Isso é apenas uma matriz de rastreios com um comprimento que não excede o comprimento possível do bytecode. A solução é preguiçosa, para economizar memória, faz sentido usar uma tabela de hash.
No início do intérprete, o primeiro manipulador de cada rastreamento será compilado:
for (size_t trace_i = 0; trace_i < MAX_CODE_LEN; trace_i++ ) vm_trace.trace_cache[trace_i][0].handler = trace_compile_handler;
O loop principal do intérprete agora fica assim:
while(vm_trace.is_running) { scode *code = &vm_trace.trace_cache[vm_trace.pc][0]; code->handler(code); }
Um compilador de rastreio é um pouco mais complicado e, além de criar um rastreio a partir da instrução atual, ele faz o seguinte:
static void trace_compile_handler(scode *trace_head) { scode *trace_tail = trace_head; trace_head->handler(trace_head); }
Manipulador de instruções normal:
static void op_add_handler(scode *code) { uint64_t arg_right = POP(); *TOS_PTR() += arg_right; code++; code->handler(code); }
Um manipulador que não faz nenhuma chamada no final da função termina cada rastreamento:
static void op_done_handler(scode *code) { (void) code; vm_trace.is_running = false; vm_trace.error = SUCCESS; }
Tudo isso, é claro, é mais complicado do que adicionar superinstruções, mas vamos ver se isso nos deu alguma coisa:
> ./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
Viva, mais 30 milissegundos!
Como assim? Em vez de simplesmente navegar pelos rótulos, criamos cadeias de chamadas de manipuladores de instruções, gastamos tempo em chamadas e passando argumentos, mas nosso porquinho ainda segue as trilhas mais rapidamente do que um simples comutador com seus rótulos.
Esse ganho no desempenho da pista é alcançado devido a três fatores:
- É fácil prever ramificações espalhadas em diferentes lugares do código.
- Os argumentos dos manipuladores são sempre pré-codificados em uma palavra de máquina completa, e isso é feito apenas uma vez - durante a compilação do rastreamento.
- O compilador transforma as cadeias de funções em uma única chamada para a primeira função do manipulador, o que é possível devido à otimização da chamada final .
Antes de resumir os resultados de nosso treinamento, o leitão e eu decidimos tentar outra técnica antiga para interpretar programas - o código costurado.
Exercício Quatro: Código "Costurado"
Qualquer porco interessado na história dos intérpretes ouviu um código encadeado. Existem muitas opções para essa técnica, mas todas se resumem a, em vez de seguir uma matriz de códigos de operação, seguindo uma matriz de, por exemplo, ponteiros para funções ou etiquetas, seguindo-os diretamente sem um código de operação intermediário.
Chamar funções é um negócio caro e sem sentido atualmente; a maioria das outras versões do código costurado é irrealizável dentro da estrutura do padrão C. Mesmo a técnica, que será discutida abaixo, usa a extensão C difusa, mas não padronizada - indicadores para etiquetas.
Na versão do código costurado (código encadeado do token em inglês) que escolhi para atingir nossos objetivos de porco, salvamos o bytecode, mas antes de iniciar a interpretação, criamos uma tabela que exibe os códigos de instrução para o endereço dos rótulos do processador de instruções:
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, };
Preste atenção aos símbolos && - são indicadores de etiquetas com o corpo de instruções, a extensão mais não-padrão do GCC.
Para começar a executar o código, basta clicar no ponteiro correspondente ao primeiro código operacional do programa:
goto *labels[NEXT_OP()];
Não há ciclo aqui e não haverá, cada uma das instruções em si salta para o seguinte manipulador:
op_pushi: { uint16_t arg = NEXT_ARG(); PUSH(arg); goto *labels[NEXT_OP()]; }
A ausência de uma opção “espalha” os pontos de ramificação ao longo dos corpos de instruções, o que, em teoria, deve ajudar o preditor de ramificação em caso de execução extraordinária de instruções. É como se incorporássemos o switch diretamente nas instruções e formássemos manualmente uma tabela de transição.
Essa é toda a técnica. Ela gostou do leitão por sua simplicidade. Vamos ver o que acontece na prática:
> ./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
Opa! Esta é a mais lenta de todas as nossas técnicas! O que aconteceu? Vamos executar os mesmos testes, desativando todas as otimizações do 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
Aqui, o código costurado tem melhor desempenho.
Três fatores desempenham um papel aqui:
- O próprio compilador de otimização criará uma tabela de conversão não pior do que nossa placa de etiquetas manual.
- Os compiladores modernos se livram notavelmente de chamadas de função extras.
- Começando na geração Haswell de processadores Intel, os preditores de ramificação aprenderam a prever com precisão as transições em um único ponto de ramificação.
Segundo a memória antiga, essa técnica ainda é usada no código, por exemplo, do interpretador Python VM, mas, francamente, hoje em dia já é arcaísmo.
Vamos finalmente resumir e avaliar os sucessos alcançados por nosso porco.
Debriefing
Não tenho certeza do que pode ser chamado de voo, mas, convenhamos, nosso porquinho percorreu um longo caminho de 550 milissegundos para cem corridas na "peneira" até os 370 milissegundos finais. Usamos diferentes técnicas: super-instruções, eliminando intervalos de verificação de valores, mecânica complicada de traços e, finalmente, até código costurado. Ao mesmo tempo, em geral, agimos dentro da estrutura das coisas implementadas em todos os compiladores populares C. A aceleração uma vez e meia, como me parece, é um bom resultado, e o leitão merece uma porção extra de farelo na cavidade.
Uma das condições implícitas que estabelecemos para nós mesmos com o porco é preservar a arquitetura de pilha da máquina VM Piglet. A transição para registrar a arquitetura, via de regra, reduz o número de instruções necessárias para a lógica dos programas e, consequentemente, pode ajudar a eliminar saídas desnecessárias ao gerenciador de instruções. Eu acho que outros 10 a 20% do tempo podem ser cortados.
Nossa principal condição - a falta de compilação dinâmica - também não é uma lei da natureza. Bombear um porco com esteróides na forma de uma compilação JIT é muito fácil atualmente: em bibliotecas como GNU Lightning ou LibJIT, todo o trabalho sujo já foi feito. Mas o tempo de desenvolvimento e a quantidade total de código, mesmo usando bibliotecas, estão crescendo tremendamente.
É claro que existem outros truques para os quais nosso porquinho não alcançou o casco. , — - — - . , .
PS , , , , ( https://www.instagram.com/vovazomb/ ), .
PPS , . true-grue - — PigletC . !
PPPS iliazeus : . ; . .