近几十年来，编程语言的虚拟机已经非常普及。 自从90年代后半叶Java虚拟机问世以来，已经过去了很多时间，可以肯定地说字节码解释器不是未来，而是现在。
但是，我认为这种技术几乎是通用的，理解解释器开发的基本原理不仅对下一个挑战者的创建者（ TIOBE称其为“年度语言”） 很有用 ，而且对所有程序员都是有用的。
简而言之，如果您有兴趣了解我们最喜欢的编程语言如何累加数字，虚拟机开发人员仍在争论什么以及如何轻松地匹配字符串和正则表达式，我会请猫。
第一部分，简介（当前）
第二部分，优化
第三部分，应用
背景知识
我们公司商务智能部门的一种自写系统具有简单查询语言形式的界面。 在系统的第一个版本中，无需编译即可直接从带有请求的输入行中即时解释该语言。 解析器的第二个版本已经可以与中间字节码一起使用，这将使您可以将查询语言与其执行分开，从而大大简化了代码。
在使用第二版系统的过程中，我度过了一个假期，在此期间，我每天要花一两个小时来处理家庭事务，以研究有关字节码解释器的体系结构和性能的材料。 我决定与Habr的读者分享由此产生的注释和口译员示例，作为一系列文章。
他们中的第一个介绍了五个小型（最多数百行简单的C代码）虚拟机，每个虚拟机都揭示了此类解释器开发的某个方面。
字节码在哪里编程语言？
已经发明了许多虚拟机，这是过去几十年来最多样化的虚拟指令集。 维基百科声称，最早的编程语言可以追溯到上个世纪60年代，开始被编译为各种简化的中间表示形式。 这些第一个字节代码中的某些被转换为机器代码，并由真实处理器执行，而其他一些则由虚拟处理器即时解释。
虚拟指令集作为代码的中间表示形式的流行是由于三个原因：
- 字节码程序很容易移植到新平台。
- 字节码解释器比代码语法树的解释器快。
- 您可以在几个小时内开发一个简单的虚拟机。
让我们制作一些简单的C虚拟机，并使用这些示例来强调实现虚拟机的主要技术方面。
完整的示例代码可在GitHub上获得 。 可以使用任何相对较新的GCC编译示例：
gcc interpreter-basic-switch.c -o interpreter ./interpreter
所有示例都具有相同的结构：首先是虚拟机本身的代码，然后是带有断言的主要函数，这些断言检查代码的运行。 我试图对解释器的操作码和关键位置进行清晰评论。 我希望即使不是每天都用C写作的人也可以理解本文。
世界上最简单的字节码解释器
正如我所说，最简单的解释器很容易制作。 注释就在清单的后面，但让我们直接从代码开始：
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; }
少于一百行，但是代表了虚拟机的所有特征属性。 该机器具有单个寄存器（ vm.accumulator ），三个操作（寄存器递增，寄存器递减和程序执行完成）以及指向当前指令的指针（ vm.ip ）。
每个操作（eng。 操作码或opcode ）都用一个字节编码，并使用vm_interpret函数中的常规switch执行调度。 switch的分支包含操作逻辑，即，它们更改寄存器的状态或终止程序的执行。
这些操作以字节数组（字节码（英文字节码 ））的形式传送到vm_interpret函数，并顺序执行，直到OP_DONE虚拟机的操作（ OP_DONE ） OP_DONE 。
虚拟机的关键方面是语义，即在虚拟机上可能执行的一组操作。 在这种情况下，只有两个操作，它们会更改单个寄存器的值。
一些研究者（ 虚拟机抽象和优化技术 ，2009）建议根据虚拟机语义与将在其上执行字节码的物理机语义之间的接近程度，将虚拟机分为高级和低级 。
在极端情况下，低级虚拟机的字节码可以完全重复具有模拟RAM，全套寄存器，用于堆栈的指令等的物理机的机器码。 例如， Bochs虚拟机重复x86体系结构指令集。
反之亦然：高级虚拟机的操作紧密反映了编译为字节码的专用编程语言的语义。 这样就可以使用，例如SQLite，Gawk和众多Prolog版本。
中间位置由具有高级和低级元素的通用编程语言的解释器占据。 最受欢迎的Java虚拟机既具有用于堆栈的低级指令，又具有对具有自动内存分配功能的面向对象编程的内置支持。
上面的代码很可能是最底层的虚拟机：每个虚拟指令是一个或两个物理指令的包装，虚拟寄存器与“铁”处理器的一个寄存器完全一致。
字节码指令参数
可以说，在我们的虚拟机示例中，唯一的寄存器既是参数，也是所有已执行指令的返回值。 但是，我们可能会发现在指令中传递参数很有用。 一种方法是直接将它们放入字节码中。
我们将通过引入指令（OP_ADDI，OP_SUBI）来扩展该示例，这些指令采用紧随操作码之后的字节形式的参数：
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; }
新指令（请参阅vm_interpret函数）从字节码读取其参数，并将其添加到寄存器中/从寄存器中减去。
这样的参数称为直接参数 ，因为它直接位于操作码数组中。 在我们的实现中的主要限制是该参数是单个字节，并且只能采用256个值。
在我们的虚拟机中，可能的指令参数值的范围并不重要。 但是，如果将虚拟机用作真实语言的解释器，则可以通过添加一个与操作码和指令数组分开的常量表，并在该常量表中添加与常量表中此参数的地址相对应的直接参数来使字节码复杂化。
堆码机
我们简单的虚拟机中的指令始终使用一个寄存器，并且不能以任何方式相互传输数据。 另外，指令的参数只能是立即数，例如加法或乘法运算需要两个参数。
简而言之，我们无法评估复杂的表达式。 要解决此问题，需要一台堆叠计算机，即具有集成堆叠的虚拟机：
#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; }
在此示例中，已经有更多的操作，并且几乎所有操作仅适用于堆栈。 OP_PUSHI将其直接参数压入堆栈。 从值堆栈中弹出指令OP_ADD，OP_SUB，OP_DIV，OP_MUL，计算结果，然后将其推回堆栈中。 OP_POP_RES从堆栈中删除该值，并将其放置在结果寄存器中，以用于虚拟机的结果。
对于除法运算（OP_DIV），将捕获除以零的错误，这将停止虚拟机。
这种机器的功能比具有单个寄存器的前一台机器的功能要广泛得多，例如，可以计算复杂的算术表达式。 另一个（也是重要的！）优点是将编程语言编译到堆栈机的字节码中的简单性。
注册机
由于其简单性，堆叠虚拟机在编程语言的开发人员中得到最广泛的使用。 相同的JVM和Python VM完全使用它们。
但是，这样的机器有缺点：它们必须添加特殊的指令来处理堆栈，在计算表达式时，所有参数都反复通过单个数据结构传递，很多额外的指令将不可避免地出现在堆栈代码中。
同时，每条额外指令的执行都带来了调度的成本，即解码操作码并切换到指令主体。
堆叠计算机的替代方法是注册虚拟机。 它们具有更复杂的字节码：寄存器参数的数量和寄存器结果的数量在每条指令中都经过显式编码。 因此，代替堆栈，扩展的寄存器集被用作中间值的存储。
#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; }
该示例显示了具有16个寄存器的寄存器机。 指令每个占用16位，并以三种方式进行编码：
- 每个操作码4位+每个寄存器名称4位+每个参数8位。
- 每个操作码4位+每个寄存器名称4位的三倍。
- 每个操作码4位+每个单个寄存器名称4位+ 8个未使用位。
我们的小型虚拟机几乎没有操作，因此每个操作码只有4位（或16种可能的操作）就足够了。 该操作确定该指令的其余位确切代表什么。
需要第一类编码（4 + 4 + 8），才能通过OP_LOADI操作将数据加载到寄存器中。 第二种类型（4 + 4 + 4 + 4）用于算术运算，该算术运算应知道在哪里使用一对参数以及在哪里添加计算结果。 最后，最后一种形式（4 + 4 + 8个不必要的位）用于以单个寄存器作为参数的指令，在我们的情况下为OP_MOV_RES。
为了对指令进行编码和解码，我们现在需要特殊的逻辑（ decode功能）。 另一方面，由于对参数位置的明确指示，指令的逻辑变得更容易-堆栈操作消失了。
关键特征：在寄存器机的字节码中，指令较少，单个指令较宽，将此类字节码编译起来更加困难-编译器必须决定如何使用可用的寄存器。
应该注意的是，实际上在注册虚拟机时通常会有一个堆栈，在该堆栈中放置例如函数自变量。 寄存器用于计算单个表达式。 即使没有显式堆栈，也将使用数组来构建堆栈，其作用与物理机中的RAM相同。
堆叠和套准机，比较
有一项有趣的研究（ 虚拟机对决：堆栈与寄存器 ，2008年）对编程语言虚拟机领域中的所有后续开发都产生了重大影响。 它的作者提出了一种将标准JVM的堆栈代码直接转换为寄存器代码并比较性能的方法。
该方法并非易事：首先翻译代码，然后以相当复杂的方式对其进行优化。 但是随后对同一程序性能的比较表明，通过减少指令总数可以完全补偿在解码指令上花费的额外处理器周期。 简而言之，总的来说，套准机比堆栈的效率更高。
如上所述，这种效率具有明显的代价：编译器必须自己分配寄存器，并且还需要高级优化器。
关于哪种架构更好的争论仍然没有结束。 如果我们谈论Java编译器，那么Dalvik VM字节码（直到最近才可在每个Android设备上使用）都已注册。 但是标题JVM保留了一堆指令。 Lua虚拟机使用注册机，但Python VM仍可堆叠。 依此类推。
正则表达式解释器中的字节码
最后，为了分散低级虚拟机的注意力，让我们看一个专门的解释器，该解释器检查字符串以进行正则表达式匹配：
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); }
主要指令是OP_CHAR。 她接受直接参数，并将其与字符串（ char *sp ）中的当前字符进行比较。 如果该行中的预期字符与当前字符一致，则过渡到下一条指令和下一个字符。
机器还了解跳转操作（OP_JUMP），该操作只需一个立即参数。 该参数表示字节码中从此处继续计算的绝对偏移量。
最后一个重要操作是OP_OR。 她采用了两个偏移量，尝试首先在第一个偏移量上应用代码，然后在出现错误的情况下尝试第二个。 她通过递归调用来执行此操作，也就是说，该指令深入了正则表达式所有可能变体的树的深度。
令人惊讶的是，四个操作码和70行代码足以表示正则表达式，例如“ abc”，“ a？Bc”，“（ab | bc）d”，“ a * bc”。 该虚拟机甚至没有明确的状态，因为您需要的所有内容（指向指令流开头的指针，当前指令和当前字符）都作为参数传递给递归函数。
如果您对正则表达式引擎的工作细节感兴趣，可以先阅读Russ Cox的系列文章， Russ Cox是Google RE2的正则表达式引擎的作者。
总结
让我们总结一下。
通常，对于通用编程语言，使用两种体系结构：堆栈和寄存器。
在堆栈模型中，指令之间传递参数的主要数据结构和方法是堆栈。 在寄存器模型中，一组寄存器用于计算表达式，但是显式或隐式堆栈仍用于存储函数参数。
显式堆栈和一组寄存器的存在使此类机器更接近于底层机器甚至物理机器。 这种字节码中大量的低级指令意味着物理处理器资源的大量消耗落在了虚拟指令的解码和调度上。
另一方面，高级指令在流行的虚拟机中起着重要作用。 例如，在Java中，这些是用于多态函数调用，对象分配和垃圾回收的指令。
纯高级虚拟机（例如，具有发达且远非铁制语义的语言的字节码解释器）大部分时间不花在调度程序或解码器上，而是花在指令主体上，因此相对高效。
实用建议：
- 如果您需要执行任何字节码并在合理的时间内执行，请尝试使用最接近您的任务的指令进行操作； 语义级别越高，越好。 这将减少调度成本并简化代码生成。
- 如果您需要更多的灵活性和异构语义，则至少应尝试突出显示字节码中的公分母，以使结果指令处于有条件的平均水平。
- 如果将来可能需要计算任何表达式，请制造一台堆栈机，这将减少编译字节码时的麻烦。
- 如果不希望使用表达式，则使用普通的寄存器机器，这将避免堆栈的开销并简化指令本身。
在以下文章中，我将讨论流行的编程语言对虚拟机的实际实现，并解释为什么Business Intelligence Badoo部门需要字节码。