Geekly articles weekly

猪逃跑，或字节码解释器的优化


“无论您多么努力，都不能用猪制造赛马。但是，您可以制造更快的猪”（Emax源代码中的注释）

每个人都知道，猪不会飞。 同样流行的观点是，如果不使用费时的动态编译，字节码解释器作为一种执行高级语言的技术就无法得到加速。


在有关字节码解释器的系列文章的第二部分中，我将尝试以小型堆叠式FDA虚拟机（Pig Virtual Machine）为例，说明有抱负的勤奋仔猪并不会失去一切，并且有可能在（主要是）标准C框架内加速这类口译员的工作至少是其一半。


第一部分，简介
第二部分，优化（当前）
第三部分，应用


仔猪


让我们结识。


Piglet VM是基于一系列文章第一部分中的示例的普通堆叠式计算机。 我们的猪只知道一种数据类型-64位机器字，并且所有（整数）计算都是在堆栈中执行的，最大深度为256个机器字。 除了堆栈之外，此小猪还具有65,536个机器字的工作内存。 程序执行的结果（一个机器字）可以放在结果寄存器中，也可以简单地输出到标准输出（stdout）。


Piglet VM计算机中的整个状态存储在一个结构中：


static struct { /* Current instruction pointer */ uint8_t *ip; /* Fixed-size stack */ uint64_t stack[STACK_MAX]; uint64_t *stack_top; /* Operational memory */ uint64_t memory[MEMORY_SIZE]; /* A single register containing the result */ uint64_t result; } vm;

上面的内容使我们可以将此计算机归因于低层虚拟机，几乎所有开销都取决于维护主程序周期：


 interpret_result vm_interpret(uint8_t *bytecode) { vm_reset(bytecode); for (;;) { uint8_t instruction = NEXT_OP(); switch (instruction) { case OP_PUSHI: { /* get the argument, push it onto stack */ uint16_t arg = NEXT_ARG(); PUSH(arg); break; } case OP_ADD: { /* Pop 2 values, add 'em, push the result back to the stack */ uint64_t arg_right = POP(); *TOS_PTR() += arg_right; break; } /* * ... * Lots of other instruction handlers here * ... */ case OP_DONE: { return SUCCESS; } default: return ERROR_UNKNOWN_OPCODE; } } return ERROR_END_OF_STREAM; }

该代码显示，对于每个操作码，小猪必须：


  1. 从指令流中检索操作码。
  2. 确保操作码在操作码值的有效范围内（此逻辑由C编译器在生成切换代码时添加）。
  3. 转到身体说明。
  4. 从堆栈中提取指令参数或解码直接位于字节码中的指令参数。
  5. 执行操作。
  6. 如果有计算结果，请将其放在堆栈上。
  7. 将指针从当前指令移至下一条指令。

这里的有效负载仅在第五段中，剩下的是开销：从堆栈中解码或检索指令自变量（第4章），检查操作码值（第2章），重复返回到主循环的开头以及随后难以预测的条件转移（第3章）。


简而言之，这头猪显然已经超过了建议的体重指数，如果我们想使它成型，那么我们将不得不应对所有这些过剩问题。


猪汇编语言和Eratosthenes筛


首先，让我们决定游戏规则。


直接用C语言为虚拟机编写程序不是一个好主意，但是创建一种编程语言很长一段时间，因此我们决定将自己限制在一种小巧的汇编语言中。


在此汇编器中，用于计算1到65,536的数字总和的程序如下所示：


 # 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

当然，不是Python，而是您需要猪幸福的一切：注释，标签，对其的有条件和无条件跳转，指令的助记符以及指定指令直接参数的能力。


带有“ Piglet VM”机器的组装机和反汇编机，本着勇气和大量的空闲时间，读者可以在战斗中独立进行测试。


这些数字加起来非常快，因此为了测试性能，我编写了另一个程序-天生的Eratosthenes筛子的实现。


实际上，无论如何，小猪都运行得非常快（其指令与机器指令非常接近），因此，为了获得清晰的结果，我将在程序的一百次启动中进行每次测量。


我们未优化的猪的第一个版本运行如下：


 > ./pigletvm runtimes test/sieve-unoptimized.bin 100 > /dev/null PROFILE: switch code finished took 545ms

半秒钟！ 比较当然是不诚实的，但是相同的Python算法会使运行速度降低一百倍：


 > python test/sieve.py > /dev/null 4.66692185402

4.5秒，或慢9倍。 我们必须向小猪致敬-他有能力！ 好吧，现在让我们看看我们的猪是否可以使压力机升高。


练习一：静态超级指令


快速代码的第一条规则是不要做太多的工作。 快速代码的第二个规则是永远不要做太多的工作。 那么Piglet VM做什么样的额外工作？


观察一：对我们的程序进行概要分析表明，存在比其他指令更常见的指令序列。 我们不会对猪有太多的折磨，而只将其限制在以下几点：


  1. LOADI 0，添加-将堆栈中位于地址0的一个数字放入堆栈中，并将其添加到堆栈顶部的编号中。
  2. PUSHI 65536，GREATER_OR_EQUAL-在堆栈上放置一个数字，并将其与之前在堆栈顶部的数字进行比较，将比较结果（0或1）放回到堆栈上。
  3. PUSHI 1，ADD-在堆栈上放置一个数字，将其添加到先前在堆栈顶部的数字，然后将相加结果放回堆栈。

Piglet VM机器中的指令多于20条，整个字节用于编码-256个值。 引入新指令不是问题。 我们将做什么：


 for (;;) { uint8_t instruction = NEXT_OP(); switch (instruction) { /* * Other instructions here * */ case OP_LOADADDI: { /* get immediate argument as an memory address , add it to value from the address to the top * of the stack */ uint16_t addr = NEXT_ARG(); uint64_t val = vm.memory[addr]; *TOS_PTR() += val; break; } case OP_GREATER_OR_EQUALI:{ /* get the immediate argument, compare it with the value from the address to the top of the stack */ uint64_t arg_right = NEXT_ARG(); *TOS_PTR() = PEEK() >= arg_right; break; } case OP_ADDI: { /* Add immediate value to the top of the stack */ uint16_t arg_right = NEXT_ARG(); *TOS_PTR() += arg_right; break; } /* * Other instructions here * */ }

没什么复杂的。 让我们看看结果如何：


 > ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 410ms

哇！ 该代码仅适用于三个新指令，我们赢得了一百五十毫秒！


之所以能够实现这一目标，是因为我们的小猪在执行此类指令时不会进行不必要的移动：执行线程不会掉入主循环，不会解码任何内容，并且指令的参数不会再次遍历堆栈。


这称为静态超级指令，因为附加指令是静态定义的，也就是说，是由虚拟机程序员在开发阶段定义的。 这是一种简单有效的技术，所有编程语言的虚拟机都以一种或另一种形式使用。


静态超级指令的主要问题在于，如果没有特定的程序，就不可能确定应该合并哪些指令。 不同的程序使用不同的指令序列，您只能在启动特定代码的阶段才能找到这些序列。


下一步可能是在特定程序的上下文中动态编译超级指令，即动态超级指令（在90年代和2000年代初期，该技术扮演了原始JIT编译的角色）。


不可能在普通C框架中即时创建指令，而我们的仔猪完全不认为这是一场诚实的竞争。 幸运的是，我为他做了一些更好的练习。


练习二：检查操作码值的范围


按照我们的快速代码规则，我们再次问自己一个永恒的问题：您不能做什么？


当我们熟悉Piglet VM机器的设备时，我列出了虚拟机为每个操作码执行的所有操作。 第二点（检查操作码的值以适合开关值的有效范围）是最可疑的。


让我们看一下GCC如何编译switch构造：


  1. 构造一个过渡表，即一个表，该表将操作码的值显示为执行指令主体的代码的地址。
  2. 插入一个代码，检查接收到的操作码是否在所有可能的开关值的范围内，如果没有该操作码的处理程序，则将其发送到默认标签。
  3. 插入处理程序的代码。

但是，为什么要检查每条指令的值间隔呢？ 我们认为操作码是正确的-由OP_DONE指令终止执行，或者是不正确的-超出字节码。 操作码流的尾部标有零，而零是OP_ABORT指令的操作码，该操作以错误结束字节码的执行。


原来根本不需要此检查！ 并且小猪应该能够将这个想法传达给编译器。 让我们尝试修复主开关：


 uint8_t instruction = NEXT_OP(); /* Let the compiler know that opcodes are always between 0 and 31 */ switch (instruction & 0x1f) { /* All the instructions here */ case 26 ... 0x1f: { /*Handle the remaining 5 non-existing opcodes*/ return ERROR_UNKNOWN_OPCODE; } }

知道我们只有26条指令，我们在操作码上强加了一个位掩码（八进制值0x1f是二进制0b11111，覆盖从0到31的值的范围），并将处理程序添加到26到31范围内的未使用的值。


位指令是x86体系结构中最便宜的一些，并且它们肯定比有问题的条件分支（如使用间隔检查的条件分支）便宜。 从理论上讲，如果编译器理解了我们的提示，我们应该在每个可执行指令上赢得多个周期。


顺便说一句，指定大小写范围的方法不是标准C，而是GCC扩展名。 但是出于我们的目的，此代码是合适的，尤其是因为对于每个不必要的值将它重新制成多个处理程序并不困难。


我们尝试：


 > ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 437ms PROFILE: switch code (no range check) finished took 383ms

再过50毫秒！ 小猪，好像你在肩上听到自己的声音！


练习三：足迹


还有哪些其他运动可以帮助我们的仔猪？ 有了超级指令，我们节省了最大的时间。 并且它们减少了进入主循环的次数，并使您摆脱了相应的间接费用。


对于指令执行异常的任何处理器，中央开关都是主要问题点。 现代的分支预测器已经学会了很好地预测这种复杂的间接转换，但是沿代码的“涂抹”分支点可以帮助处理器快速地从指令切换到指令。


另一个问题是指令操作码和字节码中直接参数的逐字节读取。 物理机器使用64位机器字运行，并且当代码以较低值运行时，它们并不真正喜欢它。


编译器通常使用基本块 （即，内部没有分支和标签的指令序列）进行操作。 基础块从程序的开头或标签开始，并以程序的结尾，条件分支或直接跳转到开始下一个基础块的标签结束。


使用基本单元有很多优点，但是我们的猪对它的主要功能感兴趣：基本单元内的指令是顺序执行的。 最好以某种方式隔离这些基本块并按照其中的说明进行操作，而又不会浪费时间进入主循环。


在我们的情况下，您甚至可以将基本单位的定义扩展到轨道。 就Piglet VM机而言，该轨道将包括所有顺序连接（即使用无条件跳转）的基本块。


除了顺序执行指令外，最好预先解码指令的直接参数。


听起来很吓人，类似于动态编译，我们决定不使用它。 猪甚至对他的力量有些怀疑，但实际上却还不错。


首先，让我们考虑一下如何想象轨道中包含的指令：


 struct scode { uint64_t arg; trace_op_handler *handler; };

这里arg是指令的预解码参数，并且handler是指向执行指令逻辑的函数的指针。


现在，每个跟踪的视图如下所示：


 typedef scode trace[MAX_TRACE_LEN];

即，迹线是有限长度的s码序列。 虚拟机内部的跟踪缓存本身如下所示：


 trace trace_cache[MAX_CODE_LEN];

这只是一个跟踪数组，其长度不超过可能的字节码长度。 解决方案是懒惰的，为了节省内存，使用哈希表是有意义的。


在解释器的开头，每个跟踪的第一个处理程序将自行编译：


 for (size_t trace_i = 0; trace_i < MAX_CODE_LEN; trace_i++ ) vm_trace.trace_cache[trace_i][0].handler = trace_compile_handler;

现在，主解释器循环如下所示：


 while(vm_trace.is_running) { scode *code = &vm_trace.trace_cache[vm_trace.pc][0]; code->handler(code); }

跟踪编译器稍微复杂一些，除了从当前指令开始构建跟踪之外，它还执行以下操作：


 static void trace_compile_handler(scode *trace_head) { scode *trace_tail = trace_head; /* * Trace building here */ /* now, run the chain that has a trace_compile_handler replaced with proper instruction handler * function pointer */ trace_head->handler(trace_head); }

普通指令处理程序：


 static void op_add_handler(scode *code) { uint64_t arg_right = POP(); *TOS_PTR() += arg_right; /* * Call the next trace handler * */ /* scodes are located in an array so we can use pointer arithmetic to get the next handler */ code++; code->handler(code); }

在函数尾部不进行任何调用的处理程序将终止每个跟踪：


 static void op_done_handler(scode *code) { (void) code; vm_trace.is_running = false; vm_trace.error = SUCCESS; }

当然，所有这些都比添加超级指令更为复杂，但是让我们看看它是否给我们带来了什么：


 > ./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

欢呼，还有30毫秒！


怎么会这样 我们不只是简单地导航标签，我们制作指令处理程序的调用链，花时间在调用和传递参数上，但是我们的小猪仍然比使用带有标签的简单开关在步道上运行得更快。


跟踪性能的提高归因于以下三个因素：


  1. 在代码中预测分散在不同位置的分支很容易。
  2. 处理程序的参数总是预先编码为一个完整的机器字，在跟踪的编译过程中，只能执行一次。
  3. 编译器将函数链转换为对第一个处理函数的单个调用，这可能是由于tail调用的优化所致。

在总结培训结果之前，我和小猪决定尝试另一种古老的解释程序的技术-缝制代码。


练习四：“缝制”代码


任何对解释器历史感兴趣的猪都会听到一个线程化的代码。 这项技术有很多选择，但是它们全都归结为，而不是遵循操作码数组，例如跟随着指向函数或标签的指针的数组，直接跟随它们而没有中间操作码。


如今，调用函数是一项昂贵且毫无意义的业务。 在标准C的框架内，大多数其他版本的缝制代码都是无法实现的。即使是将在下面讨论的技术，也使用了广泛但非标准的扩展C-指向标签的指针。


在我选择实现的猪目标的缝制代码（英语令牌线程代码）版本中，我们保存了字节码，但是在开始解释之前，我们创建了一个表，该表将指令操作码显示到指令处理程序标签的地址：


 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, };

请注意符号&&-这些是指向带有说明主体（GCC的最不标准扩展名）的标签的指针。


要开始执行代码，只需单击与程序的第一个操作码相对应的指针：


 goto *labels[NEXT_OP()];

这里没有周期，也没有周期，每个指令本身都会跳转到以下处理程序：


 op_pushi: { /* get the argument, push it onto stack */ uint16_t arg = NEXT_ARG(); PUSH(arg); /* jump to the next instruction*/ goto *labels[NEXT_OP()]; }

没有开关的情况下，分支点会沿指令主体“扩展”，理论上，在异常执行指令的情况下，这应该有助于分支预测器。 就像我们直接将开关内置于说明中并手动形成了一个过渡表一样。


这就是整个技术。 她喜欢小猪的简单。 让我们看看实际发生的情况：


 > ./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

糟糕！ 这是我们所有技术中最慢的！ 怎么了 让我们运行相同的测试，关闭所有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

在这里，缝制代码的性能更好。


这里有三个因素起作用：


  1. 优化的编译器本身将构建一个转换表，该转换表不会比我们的手动标签板差。
  2. 现代编译器显着摆脱了多余的函数调用。
  3. 从Haswell一代Intel处理器开始，分支预测器已经学会了准确预测单个分支点之间的转换。

根据旧的记忆，这种技术仍在例如Python VM解释器的代码中使用，但是坦率地说，如今，它已经成为一种过时的技术。


让我们最后总结并评估我们的猪所取得的成功。


汇报



我不确定这可以称为一次飞行，但让我们面对现实吧，我们的小猪已经经历了很长的路要走，从550毫秒（“筛子”运行一百次）到最后的370毫秒。 我们使用了不同的技术：超级指令，摆脱对数值间隔的检查，复杂的走线机制以及最后的缝合代码。 同时，我们一般都在所有流行的C编译器中实现的事情的框架内行动。在我看来，加速是一个半倍的好结果，并且仔猪在谷底里应该多留一点麸皮。


我们为Pig设置的隐式条件之一是保留Piglet VM机器的堆栈体系结构。 通常，向寄存器体系结构的过渡减少了程序逻辑所需的指令数量，因此可以帮助消除不必要的指令管理器出口。 我认为可以再减少10-20％的时间。


我们的主要条件-缺乏动态编译-也不是自然法则。 如今，以JIT汇编的形式为动物泵送类固醇非常容易：在GNU Lightning或LibJIT之类的库中，所有肮脏的工作已经完成。 但是即使使用库，开发时间和总代码量也在急剧增长。


当然，还有其他一些我们的小猪还没有达到的技巧。 , — - — - . , .


PS , , , , ( https://www.instagram.com/vovazomb/ ), .


PPS , . true-grue - — PigletC . !


PPPS iliazeus : . ; . .

Source: https://habr.com/ru/post/zh-CN428878/

More articles:


All Articles