CS Fundamentals Trainer · Guias
Compiladores, interpretadores e runtimes de linguagens
Do texto-fonte ao código em execução: análise léxica, parsing, otimização, máquinas de bytecode e compilação just-in-time, com um tree walker, uma VM de bytecode e código compilado medidos lado a lado.
40 min de leitura
Todo programa que você escreve é texto, e um processador não executa nem Python, nem Java, nem TypeScript. Algo precisa transformar o texto em ações, e as escolhas feitas ali decidem a rapidez com que o programa inicia, a rapidez com que roda, que erros você vê e quando, e por que o mesmo código pode ser 30 vezes mais lento em uma linguagem do que em outra. Esse "algo" é um compilador, um interpretador ou, na maioria das linguagens modernas, uma mistura dos dois: um runtime de linguagem. Este guia acompanha um programa pelos estágios, constrói o mesmo laço de três maneiras para medir a diferença e mostra como um compilador just-in-time se aquece e o que o faz ficar lento de novo. Os scripts estão no apêndice.
Ele se apoia em sistemas operacionais (o que é um processo), na hierarquia de memória (por que o layout importa) e na coleta de lixo (outra coisa que um runtime faz).
1. Do texto à ação: os estágios
Diagram: The stages that turn source text into something that runs
- A análise léxica (lexing, scanning) divide os caracteres em tokens:
price,*,qty,+,5. Espaços em branco e comentários desaparecem. - O parsing aplica a gramática e constrói uma árvore de sintaxe abstrata (AST) que registra a estrutura e a precedência. O próprio módulo
astdo Python a mostra paratotal = price * qty + 5: umAssigncujo valor é umAddde umMult(price, qty) e da constante 5. A multiplicação fica mais abaixo na árvore porque tem precedência maior, então a árvore dispensa parênteses. - A análise resolve nomes para declarações, verifica tipos em uma linguagem de tipagem estática e relata os erros que interrompem o build: "variável indefinida", "não é possível somar string a int".
- A representação intermediária (IR) e a otimização reescrevem o programa em uma forma mais simples, onde é mais fácil melhorá-lo (veja abaixo).
- A geração de código emite código de máquina para uma CPU real ou bytecode para uma virtual.
Os três primeiros estágios, o front end, tratam da linguagem; os dois últimos, o back end, tratam do alvo. Separá-los, como faz o LLVM, significa que N linguagens e M processadores precisam de N front ends e M back ends, não de N × M compiladores.
2. Três maneiras de executar um programa
| Abordagem | O que acontece | Exemplos | Partida | Velocidade em execução |
|---|---|---|---|---|
| Compilador antecipado (ahead-of-time, AOT) | o programa inteiro é traduzido para código de máquina antes de rodar | C, C++, Rust, Go | instantânea | muitas vezes a mais rápida, mas veja 3.1 |
| Interpretador | o programa é executado diretamente a partir da árvore ou do bytecode, instrução por instrução | CPython, Ruby (MRI), shells | instantânea | em geral a mais lenta por instrução, mas veja 3.1 |
| Compilador just-in-time (JIT) | começa interpretando; encontra o código quente em tempo de execução e o compila para código de máquina | JavaScript (V8), Java (HotSpot), .NET, PyPy | aquecimento lento | próxima da AOT, às vezes melhor |
"Linguagem compilada" e "linguagem interpretada" são propriedades de uma implementação, não de uma linguagem: o JavaScript tem interpretadores e compiladores JIT, e o C tem interpretadores. A maioria dos sistemas reais combina estágios: o Java compila para bytecode uma vez (javac), depois a JVM interpreta esse bytecode e compila por JIT os métodos quentes; o Python compila o código-fonte para bytecode (os arquivos .pyc) e o interpreta; o TypeScript é compilado para JavaScript e o JavaScript é então compilado por JIT.
2.1 Três coisas diferentes: a linguagem, o seu bytecode e o seu runtime
As palavras "Python", "Java" ou "C" são usadas para três camadas que as pessoas misturam, e muitas crenças erradas sobre desempenho e comportamento vêm dessa mistura.
| Camada | O que é | Quem define | Exemplos |
|---|---|---|---|
| Semântica da linguagem | o que um programa significa: que resultados e efeitos são garantidos e o que fica indefinido ou não especificado | uma especificação ou padrão | o padrão C, a Java Language Specification, o ECMAScript, a referência da linguagem Python |
| Forma intermediária (bytecode) | as instruções que o front end de um compilador produz para uma máquina virtual | às vezes uma especificação, às vezes um detalhe privado | o bytecode da JVM e o WebAssembly são especificados; o bytecode do CPython e o bytecode Ignition do V8 são internos |
| Implementação do runtime | o programa que o executa: interpretador, JIT, coletor de lixo, biblioteca padrão, otimizador | cada fornecedor ou projeto | CPython, PyPy; HotSpot, OpenJ9, GraalVM; V8, SpiderMonkey; GCC, Clang |
Três medições tornam a diferença concreta.
1. A mesma fonte em C, respostas diferentes. Em C, o estouro de inteiro com sinal é comportamento indefinido: o padrão permite que o compilador suponha que ele nunca acontece. Escrevi uma verificação de estouro, a + b < a, e a executei com a = INT_MAX, b = 1:
| Implementação e flags | INT_MAX + 1 estoura? |
|---|---|
gcc 13, -O0, -O1 e -O2 | "não" (o compilador supôs que não há estouro, então a + b < a virou b < 0) |
gcc 13, -O2 -fwrapv (pede o comportamento de dar a volta) | "sim" |
clang 18, -O0 | "sim" |
clang 18, -O2 | "não" |
Java, no interpretador (-Xint), no compilador C1 e no JIT padrão | "sim", sempre (a linguagem define a volta) |
A linguagem não mudou; a implementação escolheu entre comportamentos que a linguagem permitia. Um programa que depende de comportamento indefinido só está correto por acaso e pode quebrar com uma atualização do compilador ou uma mudança de flag. O Java, cuja especificação não deixa essa liberdade aqui, deu uma única resposta em todos os modos: o JIT pode mudar a velocidade, nunca o significado. Ferramentas como -fsanitize=undefined existem para encontrar esses casos.
2. A mesma função Python, bytecode diferente. Compilei uma função com três versões instaladas do CPython e listei as suas instruções:
| CPython | Instruções | Diferenças |
|---|---|---|
| 3.11 | 28 | a list comprehension é uma função aninhada separada (MAKE_FUNCTION, PRECALL) |
| 3.12 | 46 | as comprehensions são embutidas no código (inlined) (LOAD_FAST_AND_CLEAR, LIST_APPEND, END_FOR) |
| 3.13 | 47 | novas instruções combinadas (LOAD_FAST_LOAD_FAST, STORE_FAST_LOAD_FAST) |
Os programas Python se comportam do mesmo jeito nas três, mas o bytecode não faz parte da linguagem e muda entre releases; um código que analisa arquivos .pyc ou a saída do dis quebra na atualização. O bytecode da JVM, por outro lado, é um formato publicado, com uma especificação, para o qual muitas linguagens compilam (Java, Kotlin, Scala), e é por isso que elas podem compartilhar um runtime.
3. O mesmo programa, um runtime, velocidades diferentes. O comportamento acima não depende da estratégia de execução; a velocidade depende, por fatores grandes (próximas seções): o interpretador do HotSpot, o seu primeiro nível de compilador e o seu compilador otimizador são três escolhas de implementação para a mesma linguagem e o mesmo bytecode.
Uma pergunta útil diante de qualquer comportamento surpreendente é: isso é garantido pela linguagem ou é esta implementação? A ordem de iteração do dict do Python é garantida (desde a 3.7); o momento em que um finalizador roda, a velocidade de uma chamada, o layout dos objetos e o resultado de uma operação indefinida não são. Teste em mais de um compilador ou versão quando puder, ligue os avisos e os sanitizers e escreva para a especificação, não para o que uma implementação específica faz por acaso.
3. Medindo os três: um tree walker, bytecode e código compilado
Para ver a diferença, escrevi uma pequena linguagem (inteiros, +, *, %, <, atribuição e while) e executei o mesmo programa de três maneiras em C: s = 0; i = 0; while (i < 50,000,000) { s = s + (i*i) % 7; i = i + 1 }.
- Um interpretador tree-walking avalia a AST diretamente: uma chamada recursiva e um
switchpara cada nó. - Uma máquina virtual de bytecode: a árvore é achatada uma vez em 22 instruções e um laço as executa em uma pilha.
- C compilado para o mesmo laço.
| Implementação | Tempo | Relativo |
|---|---|---|
| tree walker | 2,3 a 2,4 s | 1 |
| VM de bytecode | 1,55 a 1,6 s | 1,4 a 1,6 vez mais rápida |
| compilado para código de máquina | 0,08 s | cerca de 30 vezes mais rápido |
Os três produziram o mesmo resultado. O tree walker segue ponteiros por toda a memória e faz uma chamada de função por nó; o laço de bytecode lê instruções de um array compacto, o que é mais amigável ao cache da CPU e ao seu preditor de desvios. Mas até a máquina de bytecode ainda decodifica e despacha cada instrução, cerca de 17 por iteração, 850 milhões no total, enquanto o laço compilado é um punhado de instruções de máquina. Esse é o custo fundamental da interpretação: uma sobrecarga por operação, que você paga a cada passo. (Interpretadores escritos com cuidado reduzem o custo do despacho, e interpretadores reais como o CPython acrescentam truques, mas a ordem de grandeza permanece.)
Como funciona uma máquina de pilha
Uma máquina de pilha não tem registradores nomeados; cada instrução tira seus operandos de uma pilha e empilha seu resultado. É fácil gerar código para ela, e o bytecode é compacto. Percorra a compilação de 2 + 3 * 4 e depois de (2 + 3) * 4:
Interactive animation: bytecode vm
As duas expressões têm os mesmos números e operadores, mas árvores diferentes, bytecode diferente e resultados diferentes (14 e 20). A precedência não é algo que a máquina conhece; é decidida inteiramente pelo parser e compilada na ordem das instruções. Esse é também o modelo da JVM (o bytecode Java é uma máquina de pilha), enquanto a VM do Lua e o Dalvik do Android usam máquinas de registradores, que precisam de menos instruções, mas mais longas.
O que o CPython realmente executa
O Python imprime o seu próprio bytecode com o módulo dis. Para def f(price, qty): return price * qty + 5, ele é:
LOAD_FAST_LOAD_FAST price, qty → BINARY_OP * → LOAD_CONST 5 → BINARY_OP + → RETURN_VALUE
cinco instruções de trabalho (seis com o marcador RESUME no começo), com a mesma forma da máquina acima. O custo se esconde no BINARY_OP: o Python tem tipagem dinâmica, então o + precisa descobrir em tempo de execução se está somando inteiros, floats, strings ou listas (a mesma função devolveu 3, 3.5, 'ab' e [1, 2] para argumentos diferentes). Três milhões de chamadas de uma soma assim, por uma função, levaram cerca de 0,25 s, aproximadamente 80 ns cada, contra uma fração de nanossegundo para a mesma soma compilada. As versões recentes do CPython aceleram isso com um interpretador adaptativo especializante: depois de ver que uma instrução sempre recebe inteiros, ele a reescreve para uma forma mais rápida só para inteiros (com uma guarda para voltar atrás). É a mesma ideia que os JITs usam, um nível abaixo.
3.1 Qual é a mais rápida? Depende do trabalho
A tabela da seção 2 é uma regra prática, e as medições da seção 3 são de um único laço. Nenhuma categoria (compilada antecipadamente, compilada por JIT, interpretada) é a mais rápida em geral. Mais quatro medições, cada uma das quais inverte o ranking simples em alguma situação:
1. A duração do trabalho decide quem vence. O mesmo laço (s = (s*31 + i) % 1000003) em cinco implementações, medindo o processo inteiro, com a partida incluída:
| Implementação | 1.000 iterações | 1 milhão | 100 milhões | 1 bilhão |
|---|---|---|---|---|
C (gcc -O2) | 0,001 s | 0,006 s | 0,51 s | 5,0 s |
| Java (HotSpot, JIT) | 0,037 s | 0,045 s | 0,62 s | 5,1 s |
| Node.js (V8, JIT) | 0,031 s | 0,034 s | 0,60 s | 5,8 s |
Java só com o seu interpretador (-Xint) | 0,033 s | 0,055 s | 2,3 s | 22,6 s |
| Python 3.13 (interpretador) | 0,014 s | 0,116 s | 11,0 s | 104,8 s |
Para um trabalho minúsculo, as linguagens com JIT perdem para um interpretador simples (Python: 14 ms; Node e Java: 31 a 37 ms), porque o próprio runtime leva 30 ms para iniciar; o C precisa de 1 ms. Para um trabalho longo, o JIT alcança por completo (o Java a 2% do C com um bilhão de iterações, o Node a 17%), porque o laço quente é compilado para código de máquina. Duas outras coisas se destacam: a categoria interpretada não tem uma velocidade só, já que o interpretador do próprio HotSpot rodou este laço cerca de 4,5 vezes mais devagar que o C, enquanto o CPython foi cerca de 21 vezes mais lento; e o laço é dominado por uma divisão, um caso em que um JIT tem pouco a melhorar. Outros laços dariam outras razões.
2. O algoritmo normalmente importa mais que a categoria. Um insertion sort correto em C (-O2), O(n²), contra o sorted() embutido do Python, que é o Timsort rodando em C dentro do interpretador:
| Inteiros | Insertion sort em C | sorted() do Python |
|---|---|---|
| 20.000 | 0,039 s | 0,004 s |
| 100.000 | 1,19 s | 0,029 s |
| 400.000 | 16,7 s | 0,11 s |
A linguagem interpretada "lenta" é 150 vezes mais rápida com 400.000 elementos, porque gasta o seu tempo em uma rotina bem projetada escrita em uma linguagem compilada. A maioria dos programas Python que têm bom desempenho o têm por esse motivo: o interpretador faz a orquestração e as bibliotecas compiladas fazem o trabalho. O inverso também acontece: um laço Python que faz por elemento um trabalho que uma biblioteca poderia fazer para o array inteiro é onde aparece a diferença de 20 vezes vista acima.
3. Um JIT pode vencer o código compilado antecipadamente, porque sabe como o programa se comporta. Um laço chama uma de várias funções pequenas por meio de uma tabela construída em tempo de execução. Um compilador antecipado não consegue embutir (inline) uma chamada que não consegue prever; a JVM observa quais classes chegam ao ponto de chamada e as embute:
| Destinos distintos no ponto de chamada | C (chamada indireta, gcc -O2) | Java (HotSpot, depois do aquecimento) |
|---|---|---|
| 1 | 1,62 ns | 0,77 ns |
| 2 | 1,76 ns | 1,07 ns |
| 4 | 1,97 ns | 4,31 ns |
Com um ou dois destinos, a especulação do JIT venceu por até um fator de dois; com quatro, perdeu por mais de um fator de dois, porque o ponto de chamada se tornou "megamórfico" e já não podia ser embutido. Essa é a natureza da otimização especulativa: ela é rápida quando o programa se comporta como se comportou durante o perfilamento. Os compiladores antecipados podem usar a otimização guiada por perfil (compilar, executar uma carga de trabalho representativa, recompilar com o perfil registrado) para recuperar boa parte disso, ao preço de precisar de uma carga de trabalho representativa.
4. O que você paga pelo JIT. A partida (ponto 1), memória para o compilador e para os seus dados de perfil, trabalho de compilação nos mesmos núcleos da sua aplicação e desempenho variável ao longo do tempo, que a próxima seção mede. As plataformas em que isso importa preferem a compilação antecipada ou snapshots (Go, imagens nativas do GraalVM, modos de compilação antecipada do .NET, snapshot e restauração de uma JVM aquecida).
Portanto, o ranking honesto é um conjunto de condições, não uma ordem:
| Se o trabalho é... | então, em geral |
|---|---|
| de vida curta (um comando, uma invocação de função, um script) | um programa compilado antecipadamente ou um interpretador leve vence; a partida e o aquecimento do JIT dominam |
| de longa duração e limitado pela CPU em um laço quente | AOT e JIT ficam próximos; o JIT pode vencer quando o comportamento é previsível em tempo de execução e perder quando não é |
| composto sobretudo de chamadas a bibliotecas otimizadas (ordenação, expressões regulares, arrays, criptografia) | a linguagem da cola quase não importa; importam a biblioteca e o algoritmo |
| sensível à latência, com requisitos rígidos de cauda | prefira desempenho previsível: AOT, ou um JIT aquecido que não desotimize com o seu tráfego |
| um programa cujo gargalo é E/S, um banco de dados ou a rede | nada disso importa; meça primeiro |
4. O que um otimizador faz
Quando compilei printf("%d\n", SQUARE(n) * 8) com n = 12, o gcc -O0 gerou cerca de 43 linhas de assembly que realmente multiplicam em tempo de execução. Com -O2, o compilador já tinha calculado 12 × 12 × 8 e o programa continha a constante 1152. As transformações comuns:
- Constant folding e propagação: calcular em tempo de compilação tudo o que já é conhecido.
- Eliminação de código morto: descartar o que nunca pode rodar ou cujo resultado nunca é usado.
- Inlining: trocar uma chamada pelo corpo da função. Remove o custo da chamada e, mais importante, deixa as outras otimizações enxergarem através da fronteira. É a mais importante de todas.
- Otimizações de laços: mover para fora do laço cálculos que não mudam, desenrolar (unrolling) e vetorizar para usar instruções SIMD.
- Alocação de registradores e escalonamento de instruções: manter valores em registradores da CPU e ordenar as instruções para se ajustarem ao pipeline.
- Análise de escape (escape analysis) (como na JVM e no Go): um objeto que nunca sai de uma função pode ser colocado na pilha ou removido por completo, e é por isso que uma primeira versão do meu teste de coleta de lixo, um laço Java que alocava 4 GB de arrays descartáveis, terminou em 63 ms: o compilador removeu as alocações (coleta de lixo).
Os otimizadores precisam preservar o comportamento observável do programa, e a definição disso são as regras da linguagem, incluindo o comportamento indefinido em C e C++, que permite ao compilador supor que ele nunca acontece e pode transformar um bug latente em um resultado surpreendente. Para um benchmark, isso significa: confira se aquilo que você mede ainda existe depois da otimização. Meu laço compilado usa um contador volatile; sem ele, o compilador pode trocar o laço inteiro por uma fórmula e relatar um tempo absurdamente pequeno.
Os estágios da toolchain de C podem ser executados um a um: o pré-processador (gcc -E: cola os cabeçalhos com #include e expande macros: um programa de 3 linhas virou 816 linhas), o compilador propriamente dito (-S: assembly), o assembler (-c: um arquivo objeto em um formato ELF relocável) e o linker (resolve referências entre arquivos objeto e bibliotecas em um executável de cerca de 16 KB aqui). A ligação pode ser estática (o código da biblioteca é copiado para dentro) ou dinâmica (resolvida quando o programa inicia, de modo que uma cópia da biblioteca é compartilhada e a correção de uma vulnerabilidade não exige rebuild). O Go e o Rust preferem ligação estática, e é por isso que seus binários são fáceis de pôr em uma imagem de contêiner mínima.
5. Compilação just-in-time: aquecimento e desotimização
Um JIT começa executando o código em um nível lento e barato e o perfila. Quando uma função ou laço fica quente, ele compila essa parte com um compilador otimizador, usando o que viu. O V8 tem o interpretador Ignition, depois os compiladores Sparkplug e Maglev, depois o TurboFan; o HotSpot tem um interpretador, o compilador C1 e o compilador C2. O perfil permite a otimização especulativa: "este + só viu inteiros até agora", "este acesso a propriedade só viu objetos de uma forma", então ele compila uma versão rápida com uma guarda que verifica a suposição. Se uma guarda falha, o runtime desotimiza, joga fora o código compilado e volta ao nível lento.
Medi os dois efeitos com uma função JavaScript que soma o campo x de 200 000 objetos, no Node.js 22:
| Situação | Tempo por chamada |
|---|---|
| primeira chamada (a frio) | 3 a 4,5 ms |
| segunda chamada | cerca de 1 ms |
| depois do aquecimento | cerca de 0,4 ms |
| mesmo código, o array agora mistura cinco formas de objeto diferentes | 1,0 a 1,7 ms (2,5 a 4 vezes mais lento) |
| de volta a objetos de uma só forma | ainda cerca de 1,0 a 1,3 ms |
Três coisas a aprender com isso. Primeiro, o aquecimento é real: as primeiras chamadas foram aproximadamente 10 vezes mais lentas que o regime estável, o que importa para processos de vida curta, funções serverless e as primeiras requisições depois de um deploy (atualizações graduais (rolling updates) enviam tráfego a instâncias frias; um canário ou uma requisição de aquecimento ajuda). Segundo, a estabilidade de tipos importa: o V8 dá a cada objeto uma "forma" oculta (a ordem em que as propriedades foram adicionadas), e um acesso a propriedade que vê uma forma é uma leitura rápida por deslocamento, enquanto um que vê muitas (um acesso megamórfico) precisa fazer uma busca mais lenta. {x, y} e {y, x} são formas diferentes. Terceiro, a lentidão é pegajosa: depois que o código viu muitas formas, não voltou à versão rápida quando os dados voltaram a ser uniformes. O conselho prático é criar objetos do mesmo tipo do mesmo jeito (as mesmas propriedades na mesma ordem, inicializadas no construtor) e manter os tipos consistentes no código quente.
O código compilado por JIT às vezes pode vencer o código ahead-of-time porque otimiza para o comportamento que realmente vê (por exemplo, fazendo inlining da única implementação de uma interface que é realmente usada), mas paga em tempo de aquecimento, em memória para o compilador e os dados de perfil e em desempenho menos previsível. Algumas plataformas, por isso, preferem a compilação ahead-of-time (Go; imagens nativas do GraalVM; modos AOT do .NET), e o WebAssembly foi projetado como um alvo compacto e tipado que um navegador consegue compilar rapidamente.
Desotimização na JVM: velocidade que depende do que o programa fez até agora
A seção 5 mediu o V8 com formas de objeto mistas. A JVM faz o mesmo com classes. Em uma JVM e um laço quente, mudei quais classes chegavam ao ponto de chamada da seção 3.1 (300 milhões de chamadas por lote; tempo por chamada):
| Lotes | Classes vistas no ponto de chamada | Tempo por chamada |
|---|---|---|
| 1 a 6 | 1 | 0,76 a 1,03 ns (o primeiro lote inclui o aquecimento) |
| 7 a 10 | 2 | 0,87 a 1,01 ns |
| 11 a 16 | 4 | 3,7 a 5,5 ns (4 a 6 vezes mais lento) |
| 17 a 20 | 1 de novo | 4,1 a 5,7 ns: não se recuperou |
Quando uma quarta classe chegou, a suposição por trás do código embutido ("só estas classes aparecem aqui") se tornou falsa, e a JVM desotimizou: descartou o método compilado e voltou a um nível mais lento, depois recompilou com o novo perfil, mais amplo. Voltar a uma única classe não restaurou a versão rápida no tempo que medi; o perfil registrou que esse ponto é megamórfico. Serviços reais veem isso como desempenho que muda depois de uma certa mistura de requisições ou quando um caminho de código é usado pela primeira vez, e como os primeiros minutos depois de um deploy serem diferentes das horas seguintes. Dá para vê-lo acontecer: o -XX:+PrintCompilation do HotSpot imprime made not entrant quando o código compilado é descartado; o V8 tem --trace-opt e --trace-deopt.
Consequências práticas: aqueça uma instância antes que ela receba o tráfego completo (um canário e uma subida gradual, ou a repetição de requisições representativas); mantenha os caminhos quentes estáveis quanto ao tipo (as mesmas formas e classes) e tenha cuidado com código genérico que canaliza muitos tipos por uma chamada quente; faça o benchmark depois do aquecimento e também durante ele; e, quando a latência previsível importa mais que a velocidade de pico, considere a compilação antecipada, ou meça se um JIT aquecido continua aquecido sob o seu tráfego real.
6. Tipagem estática e dinâmica, do ponto de vista do compilador
Em uma linguagem de tipagem estática, o compilador conhece o tipo de cada expressão antes de o programa rodar, então pode emitir uma soma direta de inteiros, dispor objetos na memória com deslocamentos fixos de campos e relatar erros de tipo em tempo de build. Em uma linguagem de tipagem dinâmica, esse conhecimento não está disponível até a execução, e é por isso que um JIT precisa redescobri-lo com perfilamento e guardas. Isso é só uma parte do debate entre elas (flexibilidade, velocidade de desenvolvimento, ferramentas), mas explica por que os sistemas de tipagem gradual (TypeScript, type hints do Python) ajudam principalmente o programador e as ferramentas, enquanto o runtime ainda precisa verificar tipos, a menos que a linguagem seja compilada com os tipos fazendo parte da sua semântica.
7. Onde a ideia aparece no trabalho do dia a dia
- Expressões regulares, SQL e templates são pequenas linguagens que são compiladas para uma forma interna e depois executadas. Um prepared statement ou uma regex pré-compilada evita refazer o front end a cada uso (indexação e planos de consulta).
- Linguagens de configuração e de regras, motores de expressões, fórmulas de planilhas e filtros de consulta em uma API são interpretadores. Construir um com um parser escrito à mão e um tree walker é um projeto normal de fim de semana, e um passo de bytecode é uma otimização para depois.
- Ferramentas de build e bundlers (
tsc, esbuild, os compiladores do Go e do Rust) são compiladores com caches; sua velocidade depende dos estágios do pipeline e do trabalho incremental. - Segurança: os parsers são onde o texto não confiável encontra pela primeira vez o seu programa, e muitos bugs de injeção são duas linguagens misturadas em uma string (injeção de SQL). Os compiladores também produzem os binários cuja procedência importa em ataques à cadeia de suprimentos (veja CI/CD).
8. Erros comuns
- Dizer que uma linguagem "é interpretada" ou "é compilada" como se fosse uma propriedade fixa.
- Fazer benchmark de uma linguagem compilada por JIT em uma única execução a frio, ou de uma linguagem AOT em um laço cujo resultado não é usado, e tirar conclusões.
- Otimizar o código antes de medir para onde vai o tempo; a maior parte do tempo está em poucos lugares.
- Supor que uma linguagem mais rápida conserta um design lento: 30 vezes vindas da linguagem não recuperam um algoritmo quadrático (complexidade).
- Misturar formas de objeto e tipos em caminhos quentes de uma linguagem dinâmica.
- Ignorar custos de inicialização e de aquecimento em funções serverless, ferramentas de linha de comando e instâncias recém-implantadas.
- Depender de comportamento indefinido em C ou C++.
- Interpretar dados estruturados com expressões regulares ou divisão de strings quando existe um parser de verdade.
9. Coisas a mencionar em uma entrevista
- O pipeline: lexer, parser (AST), análise, IR e otimização, geração de código; front end e back end.
- Compilador contra interpretador contra JIT, e que "compilado" é uma propriedade da implementação.
- Por que uma VM de bytecode é mais rápida que um tree walker, e por que o código compilado é ainda mais rápido (sobrecarga de despacho por operação); no meu teste, cerca de 1,5 vez e 30 vezes.
- Máquinas de pilha contra máquinas de registradores, e o que
disoujavapmostram. - Otimizações comuns (constant folding, inlining, eliminação de código morto, análise de escape) e por que o inlining é a que mais importa.
- JIT: níveis, perfilamento, especulação com guardas, desotimização, aquecimento, classes ocultas e monomórfico contra megamórfico.
- Ligação estática contra dinâmica; o que acontece entre
gcc -Ee um executável. - Custos de inicialização e de aquecimento em implantações reais.
Resumo rápido
- Um programa passa por análise léxica, parsing, análise, otimização e geração de código; o front end trata da linguagem, o back end do alvo.
- Os interpretadores pagam um custo de despacho por operação. Para o mesmo laço, uma máquina de bytecode foi cerca de 1,5 vez mais rápida que um tree walker e o código compilado cerca de 30 vezes mais rápido.
- Os otimizadores fazem trabalho em tempo de compilação (o compilador transformou 12 × 12 × 8 na constante 1152); confira se o seu benchmark ainda mede alguma coisa.
- Um JIT perfila, compila o código quente de forma especulativa e desotimiza quando seus palpites falham. No V8, uma chamada a frio foi cerca de 10 vezes mais lenta que uma aquecida, e misturar formas de objeto deixou a função de 2,5 a 4 vezes mais lenta e ela continuou lenta.
- Planeje para o aquecimento e a inicialização nas implantações, mantenha tipos e formas consistentes no código quente e meça antes de otimizar.
Apêndice: o código dos experimentos
Quatro arquivos: um programa em C com três maneiras de executar um laço (interp.c, compile com gcc -O2), um script em Python que imprime uma árvore de sintaxe e bytecode (pyvm.py, Python 3.13), um script de shell que executa o compilador C estágio por estágio (stages.sh, GCC) e um arquivo JavaScript para o Node.js 22 (jit.js). Os tempos vêm de execuções únicas em uma pequena máquina virtual e variam entre execuções e máquinas; as razões (a máquina de bytecode é cerca de 1,5 vez mais rápida que o tree walker, o código compilado é 30 vezes mais rápido) foram estáveis nas execuções que fiz, e os números do JIT são dados como faixas. A versão compilada usa um contador volatile para que o compilador não possa trocar o laço por uma fórmula, o que não seria uma comparação justa. A animação compila e executa expressões reais com algumas linhas de TypeScript, mas é um modelo, não o CPython.
interp.c: um tree walker, uma máquina de bytecode e código compilado para o mesmo laço
// interp.c: the same loop run three ways: walking a syntax tree, running bytecode, and as compiled C.
// s = 0; i = 0; while (i < N) { s = s + (i * i) % 7; i = i + 1 }
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
enum { NUM, VAR, ADD, MUL, MOD, LT, ASSIGN, WHILE, SEQ };
typedef struct Node { int kind; long val; struct Node *a, *b; } Node;
static long vars[2]; // 0 = s, 1 = i
static Node *mk(int k, long v, Node *a, Node *b) { Node *n = malloc(sizeof *n); *n = (Node){k, v, a, b}; return n; }
// ---- 1. tree walker: one recursive call per node, a switch on the node kind
static long eval(Node *n) {
switch (n->kind) {
case NUM: return n->val;
case VAR: return vars[n->val];
case ADD: return eval(n->a) + eval(n->b);
case MUL: return eval(n->a) * eval(n->b);
case MOD: return eval(n->a) % eval(n->b);
case LT: return eval(n->a) < eval(n->b);
case ASSIGN: return vars[n->val] = eval(n->a);
case WHILE: while (eval(n->a)) eval(n->b); return 0;
case SEQ: eval(n->a); return eval(n->b);
}
return 0;
}
// ---- 2. bytecode: the tree is flattened once into a linear array, then run by a loop with a stack
enum { PUSH, LOAD, STORE, OP_ADD, OP_MUL, OP_MOD, OP_LT, JZ, JMP, HALT };
typedef struct { int op; long arg; } Ins;
static Ins code[64]; static int ncode;
static int emit(int op, long arg) { code[ncode] = (Ins){op, arg}; return ncode++; }
static void gen(Node *n) {
switch (n->kind) {
case NUM: emit(PUSH, n->val); break;
case VAR: emit(LOAD, n->val); break;
case ADD: gen(n->a); gen(n->b); emit(OP_ADD, 0); break;
case MUL: gen(n->a); gen(n->b); emit(OP_MUL, 0); break;
case MOD: gen(n->a); gen(n->b); emit(OP_MOD, 0); break;
case LT: gen(n->a); gen(n->b); emit(OP_LT, 0); break;
case ASSIGN: gen(n->a); emit(STORE, n->val); break;
case SEQ: gen(n->a); gen(n->b); break;
case WHILE: { int top = ncode; gen(n->a); int jz = emit(JZ, 0); gen(n->b); emit(JMP, top); code[jz].arg = ncode; break; }
}
}
static void run(void) {
long st[32]; int sp = 0, pc = 0;
for (;;) {
Ins in = code[pc++];
switch (in.op) {
case PUSH: st[sp++] = in.arg; break;
case LOAD: st[sp++] = vars[in.arg]; break;
case STORE: vars[in.arg] = st[--sp]; break;
case OP_ADD: sp--; st[sp-1] += st[sp]; break;
case OP_MUL: sp--; st[sp-1] *= st[sp]; break;
case OP_MOD: sp--; st[sp-1] %= st[sp]; break;
case OP_LT: sp--; st[sp-1] = st[sp-1] < st[sp]; break;
case JZ: if (!st[--sp]) pc = in.arg; break;
case JMP: pc = in.arg; break;
case HALT: return;
}
}
}
// ---- 3. native: what a compiler produces for the same program
static long native(long n) { long s = 0; for (volatile long i = 0; i < n; i++) s += (i * i) % 7; return s; }
static double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec / 1e9; }
int main(int argc, char **argv) {
long N = atol(argv[1]);
Node *prog = mk(SEQ, 0, mk(ASSIGN, 0, mk(NUM, 0, 0, 0), 0), mk(SEQ, 0, mk(ASSIGN, 1, mk(NUM, 0, 0, 0), 0),
mk(WHILE, 0, mk(LT, 0, mk(VAR, 1, 0, 0), mk(NUM, N, 0, 0)),
mk(SEQ, 0, mk(ASSIGN, 0, mk(ADD, 0, mk(VAR, 0, 0, 0), mk(MOD, 0, mk(MUL, 0, mk(VAR, 1, 0, 0), mk(VAR, 1, 0, 0)), mk(NUM, 7, 0, 0))), 0),
mk(ASSIGN, 1, mk(ADD, 0, mk(VAR, 1, 0, 0), mk(NUM, 1, 0, 0)), 0)))));
double t = now(); vars[0] = vars[1] = 0; eval(prog); double t1 = now() - t; long r1 = vars[0];
ncode = 0; gen(prog); emit(HALT, 0);
t = now(); vars[0] = vars[1] = 0; run(); double t2 = now() - t; long r2 = vars[0];
t = now(); long r3 = native(N); double t3 = now() - t;
printf("N=%ld results equal: %s (%ld bytecode instructions in the program)\n", N, (r1 == r2 && r2 == r3) ? "yes" : "NO", (long)ncode);
printf("tree walker: %.2f s bytecode VM: %.2f s compiled: %.2f s\n", t1, t2, t3);
printf("bytecode is %.1fx faster than the tree walker; compiled code is %.0fx faster than the tree walker\n", t1 / t2, t1 / t3);
return 0;
}
pyvm.py: a árvore de sintaxe e o bytecode de uma função Python
import ast, dis, time
src = "total = price * qty + 5"
print("1. source -> syntax tree")
print(ast.dump(ast.parse(src), indent=2)[:600])
def f(price, qty):
return price * qty + 5
print("\n2. the bytecode CPython runs for f(price, qty) = price * qty + 5")
dis.dis(f)
print(" instructions:", len(list(dis.get_instructions(f))))
print("\n3. a dynamically typed '+' must check the types every time")
def add(a, b): return a + b
for a, b in ((1, 2), (1.5, 2), ("a", "b"), ([1], [2])):
print(f" add({a!r}, {b!r}) = {add(a, b)!r}")
n = 3_000_000
t = time.perf_counter()
for i in range(n): add(i, 1)
print(f" {n:,} int additions through a function call: {time.perf_counter() - t:.2f} s")
stages.sh: os estágios de um compilador C, um de cada vez
# the stages of a C compiler, one at a time
cat > hello.c <<'C'
#include <stdio.h>
#define SQUARE(x) ((x) * (x))
int main(void) { int n = 12; printf("%d\n", SQUARE(n) * 8); return 0; }
C
gcc -E hello.c | wc -l | sed 's/^/preprocessed lines (the header is pasted in): /'
gcc -S -O0 hello.c -o hello_O0.s; grep -c '^\s' hello_O0.s | sed 's/^/assembly lines at -O0: /'
gcc -S -O2 hello.c -o hello_O2.s; grep -E 'imul|sal|shl|\$1152|\$144' hello_O2.s | head -3 | sed 's/^/at -O2 the multiplication is already done by the compiler: /'
gcc -c hello.c -o hello.o && file hello.o | cut -d, -f1-2
gcc hello.o -o hello && ls -l hello | awk '{print "linked program: " $5 " bytes"}' && ./hello
jit.js: aquecimento do JIT e mudança das formas de objeto no V8
// jit.js: V8 warms up, then slows down when the types change (run with: node jit.js)
function sumX(points) { let s = 0; for (let i = 0; i < points.length; i++) s += points[i].x; return s; }
const mk = (shape, n) => Array.from({ length: n }, (_, i) => shape(i));
const A = (i) => ({ x: i, y: 1 }); // one object shape
const B = (i) => ({ y: 1, x: i }); // same fields, different order: a different hidden class
const C = (i) => ({ x: i, y: 1, z: 2 });
const D = (i) => ({ a: 1, x: i });
const E = (i) => ({ b: 1, c: 2, x: i });
const N = 200000;
function time(label, arr, reps) {
const t = process.hrtime.bigint(); let r = 0;
for (let k = 0; k < reps; k++) r += sumX(arr);
const ms = Number(process.hrtime.bigint() - t) / 1e6;
console.log(`${label.padEnd(44)} ${(ms / reps).toFixed(3)} ms per call`);
return r;
}
const mono = mk(A, N);
console.log("1. warm-up: the same call repeated on the same shape");
for (const reps of [1, 1, 1, 1, 5, 50, 200]) time(`call batch of ${reps}`, mono, reps);
console.log("2. the same code with objects of several shapes mixed in one array");
const mixed = mono.map((p, i) => [A, B, C, D, E][i % 5](i));
time("five shapes (megamorphic)", mixed, 100);
console.log("3. back to a single shape");
time("one shape again", mono, 100);
Semântica contra implementação: comportamento indefinido em C, comportamento definido em Java e bytecode que muda entre versões do Python
ub.c (compile com gcc -O0, -O2, -O2 -fwrapv e com clang), Ub.java (JDK 21; execute com -Xint, -XX:TieredStopAtLevel=1 e com os padrões) e bc.py (execute com cada versão do Python que você tiver).
#include <limits.h>
#include <stdio.h>
/* Signed overflow is undefined behaviour in C: the compiler may assume it never happens, and then "a + b < a" means just "b < 0". */
int add_overflows(int a, int b) { return a + b < a; }
int main(int argc, char **argv) {
int a = INT_MAX, b = 1; /* decided at run time so that the compiler cannot fold the call away */
if (argc > 5) a = 0;
printf("does INT_MAX + 1 overflow? the check says: %s\n", add_overflows(a, b) ? "yes" : "no");
return 0;
}
public class Ub {
static boolean addOverflows(int a, int b) { return a + b < a; }
public static void main(String[] args) {
int a = Integer.MAX_VALUE, b = 1; if (args.length > 5) a = 0;
System.out.println("does Integer.MAX_VALUE + 1 overflow? the check says: " + (addOverflows(a, b) ? "yes" : "no") + " (Java defines the wrap-around, so every implementation agrees)");
}
}
import dis, sys
def f(prices, qty):
total = 0
for p in prices:
total += p * qty
return [round(total, 2)] + [x for x in prices if x > 1]
ops = [i.opname for i in dis.get_instructions(f)]
print(f"Python {sys.version.split()[0]}: {len(ops)} instructions; first ones: {' '.join(ops[:9])}")
print(f" opcodes used: {sorted(set(ops))}")
Tempo do processo inteiro do mesmo laço em cinco implementações
Coloque as quatro fontes e o driver em uma pasta e execute python3 cross.py; ele precisa de gcc, um JDK, Node.js e Python, e a execução em Python com um bilhão de iterações leva cerca de dois minutos.
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) { long n = atol(argv[1]); long s = 0; for (long i = 0; i < n; i++) s = (s * 31 + i) % 1000003; printf("%ld\n", s); return 0; }
public class Loop { public static void main(String[] a) { long n = Long.parseLong(a[0]), s = 0; for (long i = 0; i < n; i++) s = (s * 31 + i) % 1000003; System.out.println(s); } }
const n = Number(process.argv[2]); let s = 0; for (let i = 0; i < n; i++) s = (s * 31 + i) % 1000003; console.log(s);
import sys
n = int(sys.argv[1]); s = 0
for i in range(n): s = (s * 31 + i) % 1000003
print(s)
"""Total wall-clock time of whole processes (start-up included) for the same loop in an AOT-compiled language, a JIT, a bytecode interpreter and a JVM running only its interpreter."""
import statistics, subprocess, sys, time
subprocess.run(["gcc", "-O2", "-o", "loop_c", "loop.c"], check=True)
env = {"JAVA_TOOL_OPTIONS": "", "PATH": "/usr/bin:/bin:/usr/local/bin"}
subprocess.run(["javac", "Loop.java"], check=True, env=env, capture_output=True)
impls = {"C (gcc -O2)": ["./loop_c"], "Java (HotSpot JIT)": ["java", "Loop"], "Java -Xint (interpreter only)": ["java", "-Xint", "Loop"],
"Node.js (V8 JIT)": ["node", "loop.js"], "Python 3.13 (interpreter)": ["python3", "loop.py"]}
sizes = [1_000, 1_000_000, 100_000_000, 1_000_000_000]
LIMIT = 40 # do not run anything that is expected to take longer than this many seconds
print(f"{'':<32}" + "".join(f"{n:>16,}" for n in sizes) + " (iterations; seconds for the whole process)")
answers = {}
slow = set()
for name, cmd in impls.items():
row = []
for n in sizes:
if name in slow: row.append("not run"); continue
reps = 5 if n <= 1_000_000 else 1
ts = []
for _ in range(reps):
t = time.perf_counter(); out = subprocess.run(cmd + [str(n)], capture_output=True, text=True, env={**env}).stdout.strip(); ts.append(time.perf_counter() - t)
answers.setdefault(n, set()).add(out)
m = statistics.median(ts); row.append(f"{m:.3f}")
if m * (sizes[min(sizes.index(n) + 1, len(sizes) - 1)] / n) > LIMIT * 4 and n != sizes[-1]: slow.add(name)
print(f"{name:<32}" + "".join(f"{x:>16}" for x in row))
print("all implementations printed the same answer for each size:", all(len(v) == 1 for v in answers.values()))
Uma ordenação compilada antecipadamente com o algoritmo errado contra o sorted()
Compile com gcc -O2 -o insertion insertion.c e depois execute ./insertion 100000 e python3 sorted_py.py 100000.
/* A correct, ahead-of-time compiled sort with the wrong algorithm for the job: insertion sort, O(n^2). */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(int argc, char **argv) {
long n = atol(argv[1]); int *a = malloc(n * sizeof(int)); unsigned x = 12345;
for (long i = 0; i < n; i++) { x = x * 1103515245u + 12345u; a[i] = x >> 8; }
struct timespec t0, t1; clock_gettime(CLOCK_MONOTONIC, &t0);
for (long i = 1; i < n; i++) { int v = a[i]; long j = i - 1; while (j >= 0 && a[j] > v) { a[j + 1] = a[j]; j--; } a[j + 1] = v; }
clock_gettime(CLOCK_MONOTONIC, &t1);
printf("C insertion sort of %ld integers (gcc -O2): %.3f s (sorted: %d)\n", n, (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9, a[0] <= a[n / 2] && a[n / 2] <= a[n - 1]);
}
import random, sys, time
n = int(sys.argv[1]); r = random.Random(1); a = [r.randrange(1 << 24) for _ in range(n)]
t = time.perf_counter(); b = sorted(a); dt = time.perf_counter() - t
print(f"Python sorted() of {n} integers: {dt:.3f} s (sorted: {b == sorted(b)})")
Inlining e desotimização: ponteiros de função em C contra um ponto de chamada da JVM
Compile com gcc -O2 -o dispatch_c dispatch.c e execute ./dispatch_c 4 1000000000; java Dispatch 4 1000000000 executa a versão em Java e java Dispatch phases 300000000, o experimento de desotimização.
/* A loop that calls one of several small functions through a table that is only known at run time. An ahead-of-time compiler cannot inline them. */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static int inc(int x) { return x + 1; }
static int dbl(int x) { return x * 2 + 1; }
static int xr(int x) { return x ^ 0x5555; }
static int neg(int x) { return -x + 3; }
int main(int argc, char **argv) {
int variants = atoi(argv[1]); long n = atol(argv[2]);
int (*all[4])(int) = {inc, dbl, xr, neg}; int (*seq[1024])(int);
for (int i = 0; i < 1024; i++) seq[i] = all[i % variants];
struct timespec a, b; clock_gettime(CLOCK_MONOTONIC, &a);
int s = 1; for (long i = 0; i < n; i++) s = seq[i & 1023](s);
clock_gettime(CLOCK_MONOTONIC, &b);
printf("C, %d function(s) in the table: %.2f ns per call (%d)\n", variants, ((b.tv_sec - a.tv_sec) * 1e9 + (b.tv_nsec - a.tv_nsec)) / n, s & 1);
}
public class Dispatch {
interface Op { int apply(int x); }
static final class Inc implements Op { public int apply(int x) { return x + 1; } }
static final class Dbl implements Op { public int apply(int x) { return x * 2 + 1; } }
static final class Xr implements Op { public int apply(int x) { return x ^ 0x5555; } }
static final class Neg implements Op { public int apply(int x) { return -x + 3; } }
static final Op[] ALL = {new Inc(), new Dbl(), new Xr(), new Neg()};
static Op[] seq(int variants) { Op[] s = new Op[1024]; for (int i = 0; i < 1024; i++) s[i] = ALL[i % variants]; return s; }
static int run(Op[] seq, long n, int s) { for (long i = 0; i < n; i++) s = seq[(int) (i & 1023)].apply(s); return s; }
public static void main(String[] args) {
long n = Long.parseLong(args[1]);
if (args[0].equals("phases")) {
// one JVM, one hot loop; the set of classes the call site sees changes while the program runs
int s = 1; int[] schedule = {1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1};
System.out.println("batch classes seen at the call site ns per call");
for (int b = 0; b < schedule.length; b++) {
Op[] sq = seq(schedule[b]); long t = System.nanoTime(); s = run(sq, n, s); double ns = (System.nanoTime() - t) / (double) n;
System.out.printf("%5d %29d %12.2f%n", b + 1, schedule[b], ns);
}
System.out.println("(" + (s & 1) + ")");
} else {
int variants = Integer.parseInt(args[0]); Op[] sq = seq(variants); int s = 1;
for (int w = 0; w < 5; w++) s = run(sq, n / 5, s); // warm-up, discarded
long t = System.nanoTime(); s = run(sq, n, s);
System.out.printf("Java, %d class(es) at the call site: %.2f ns per call (%d)%n", variants, (System.nanoTime() - t) / (double) n, s & 1);
}
}
}
Fontes
- Alfred Aho, Monica Lam, Ravi Sethi e Jeffrey Ullman, Compilers: Principles, Techniques, and Tools ("o Dragon Book", 2ª ed., Pearson, 2006).
- Robert Nystrom, Crafting Interpreters (2021), que constrói tanto um interpretador de árvore quanto uma máquina virtual de bytecode.
- Keith Cooper e Linda Torczon, Engineering a Compiler (Morgan Kaufmann, 3ª ed., 2022).
- Documentação do Python:
astedis, e o guia de desenvolvimento do CPython, Design of CPython's compiler e o interpretador adaptativo especializante (PEP 659). - Blog da equipe do V8: Launching Ignition and TurboFan, Fast properties in V8 (classes ocultas) e Sparkplug.
- Oracle, The Java Virtual Machine Specification (Java SE 21), e as notas sobre a compilação em níveis do HotSpot.
- Documentação do GCC, Overall options (
-E,-S,-c) e Optimize options. - WebAssembly: especificação e introdução; e Chris Lattner e Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation (CGO 2004).
- Padrão ISO C (comportamento indefinido) e a documentação do GCC e do Clang sobre
-fwrapve-fsanitize=undefined; John Regehr, A Guide to Undefined Behavior in C and C++. - A Java Language Specification e a Java Virtual Machine Specification (bytecode da JVM); documentação do Python,
dis("detalhe de implementação do CPython": o bytecode pode mudar entre versões). - OpenJDK, documentação do compilador do HotSpot e
-XX:+PrintCompilation; V8,--trace-deopte o pipeline de otimização.
Pratique este tema: CS Fundamentals