快速算术字节码虚拟机：虚拟机的实现与性能优化

在本系列文章中，我们使用Haskell编写一个快速的字节码编译器和算术虚拟机。我们探讨以下主题：

将算术表达式解析为抽象语法树（AST）
解析器的单元测试
解释AST
将AST编译为字节码
反汇编和反编译字节码
编译器的单元测试
编译器的基于属性的测试
在虚拟机（VM）中高效执行字节码
虚拟机的单元测试和基于属性的测试
对代码进行基准测试以查看不同阶段的性能表现

在本文中，我们编写执行字节码的虚拟机，并对其进行基准测试。

引言

字节码虚拟机（VM）已知比AST遍历解释器更快。这就是为什么许多现代编程语言都使用字节码VM实现，例如Java、Python、PHP和Raku。部分原因是字节码本身平坦且紧凑的特性。但VM还有一些其他技巧使其具有高性能。在本文中，我们为算术表达式语言编写一个VM，并探索其中一些性能技巧。

测试编译器

我们在上一篇文章中为编译器编写了一些单元测试，但单元测试仅覆盖我们能想到的情况。编译器必须处理任何输入，仅凭单元测试我们无法确定其正确性。

为了测试编译器和其他组件的正确性，我们使用QuickCheck库。QuickCheck是一个基于属性的测试框架。基于属性测试的关键思想是编写代码的属性，这些属性对于任何输入都成立，然后自动生成大量任意输入并确保属性确实成立。

虚拟机

现在是主要事件：虚拟机。我们的VM是一个基于堆栈的机器，操作一个值堆栈并执行编译后的字节码。我们的目标是尽可能快。快速回顾一下，这是我们的操作码：

1
2
3
4
5
6
7
8
9


data Opcode
  = OPush !Int16        -- 0
  | OGet !Word8         -- 1
  | OSwapPop            -- 2
  | OAdd                -- 3
  | OSub                -- 4
  | OMul                -- 5
  | ODiv                -- 6
  deriving (Show, Read, Eq, Generic)

现在，VM的核心：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


interpretBytecode :: Bytecode -> Result Int16
interpretBytecode = interpretBytecode' defaultStackSize

interpretBytecode' :: Int -> Bytecode -> Result Int16
interpretBytecode' stackSize bytecode = runST $ runExceptT $ do
  stack <- PA.newPinnedPrimArray stackSize
  sp <- go 0 0 stack
  checkStack InterpretBytecode stackSize sp
  PA.readPrimArray stack 0
  where
    !size = BS.length bytecode

    go sp ip _ | ip == size = pure sp
    go !sp !ip stack = do
      let opcode = readInstr bytecode ip
      if
        | sp >= stackSize -> throwInterpretError "Stack overflow"
        | sp < 0 -> throwInterpretError "Stack underflow"
        | sp < 2 && opcode >= 2 -> throwInsufficientElementsError
        | opcode == 0 && ip + 2 >= size -> throwIPOOBError $ ip + 2
        | opcode == 1 && ip + 1 >= size -> throwIPOOBError $ ip + 1
        | otherwise -> case opcode of
            0 -> do                 -- OPush
              PA.writePrimArray stack sp $ readInstrArgInt16 bytecode ip
              go (sp + 1) (ip + 3) stack
            1 -> do                 -- OGet
              let i = fromIntegral $ readInstrArgWord8 bytecode ip
              if i < sp
                then do
                  PA.copyMutablePrimArray stack sp stack i 1
                  go (sp + 1) (ip + 2) stack
                else throwInterpretError $
                  "Stack index " <> show i <> " out of bound " <> show (sp - 1)
            2 -> do                 -- OSwapPop
              PA.copyMutablePrimArray stack (sp - 2) stack (sp - 1) 1
              go (sp - 1) (ip + 1) stack
            3 -> interpretBinOp (+) -- OAdd
            4 -> interpretBinOp (-) -- OSub
            5 -> interpretBinOp (*) -- OMul
            6 -> do                 -- ODiv
              b <- PA.readPrimArray stack $ sp - 1
              a <- PA.readPrimArray stack $ sp - 2
              when (b == 0) $ throwInterpretError "Division by zero"
              when (b == (-1) && a == minBound) $
                throwInterpretError "Arithmetic overflow"
              PA.writePrimArray stack (sp - 2) $ a `div` b
              go (sp - 1) (ip + 1) stack
            n -> throwInterpretError $
              "Invalid bytecode: " <> show n <> " at: " <> show ip
      where
        interpretBinOp op = do
          b <- PA.readPrimArray stack $ sp - 1
          a <- PA.readPrimArray stack $ sp - 2
          PA.writePrimArray stack (sp - 2) $ a `op` b
          go (sp - 1) (ip + 1) stack
        {-# INLINE interpretBinOp #-}

        throwIPOOBError ip = throwInterpretError $
          "Instruction index " <> show ip <> " out of bound " <> show (size - 1)

        throwInsufficientElementsError =
          throwInterpretError "Not enough elements to execute operation"

        throwInterpretError = throwError . Error InterpretBytecode

interpretBytecode'函数是动作发生的地方。它比interpretAST复杂得多，但复杂性是有原因的，即性能。

interpretBytecode'在ST monad中运行，包装在ExceptT monad变换器中。ST monad允许我们在本地使用可变数据结构，同时确保函数在外部保持纯净。ExceptT monad变换器增加了以纯方式抛出和传播错误的支持。

我们使用PrimArray作为堆栈，这是一个未装箱原始类型的可变数组，在我们的情况下是一个Int16值数组。使用可变未装箱数组比使用不可变和/或装箱数组（如Seq或Vector）快得多，因为减少了分配和/或指针追逐。

VM的核心是go函数，一个紧密的尾递归循环，GHC将其编译成高效的机器循环。它以堆栈指针（sp）、指令指针（ip）和堆栈作为参数。

在每个循环的顶部，一组保护子句在当前操作码之前检查堆栈溢出、下溢和其他错误条件。将这些检查放在顶部而不是操作码情况内部是一个深思熟虑的选择。这可能会使代码稍微难以理解，但通过将所有分支移到循环开头，显著提高了循环的性能，使代码对CPU的分支预测器更友好。

窥探内部：GHC Core

我们稍后会看到VM相当快，但GHC是如何实现这种性能的？为了看到魔法，我们可以查看GHC的中间语言：Core。Core是比Haskell更简单的函数式语言，GHC将Haskell编译到Core。Core的简单性使GHC更容易优化它并进一步编译。

测试VM

我们必须测试VM以确保其正确工作。我们重用AST解释器的成功和失败测试，因为字节码解释器应该产生相同的结果。

基准测试VM

现在是有趣的部分：基准测试。我们使用criterion库对代码进行基准测试。

以下是结果摘要：

基准测试	平均时间（ms）
pass/parse	573.5
pass/compile	50.8
pass/disassemble	155.8
pass/decompile	506.5
interpret/ast	49.8
interpret/bytecode	15.8
run/ast	617.2
run/bytecode	638.3

让我们分析这些数字：

解析和反编译很慢：分别为~~573ms和~~506ms，是迄今为止最慢的阶段。
编译很快：~51ms，比解析快一个数量级。
字节码解释非常快：仅~16ms，我们的VM解释器比AST解释器（~50ms）快3倍以上。
端到端运行：通过字节码运行的总时间（~638ms）略慢于通过AST运行（~617ms）。

与C语言对比基准测试

为了更好了解VM的性能，我用C重写了它。C实现采用经典的手动方法：手写分词器和递归下降解析器、带指针的结构体用于AST、手动内存管理和错误传播。VM是一个简单的while循环，带有用于分发操作码的switch语句。

以下是结果的总结：

阶段	C时间（ms）	Haskell时间（ms）	减速
Read	14.2	30.4	2.14x
Parse	203.2	537.2	2.64x
Compile	37.1	62.4	1.68x
Interpret	13.4	20.2	1.51x
Run	13.9	29.3	2.11x

正如预期的那样，C实现在所有方面都更快，介于1.5倍到2.6倍之间。最大的差异在解析方面，手写的C解析器比基于组合器的解析器快两倍以上。另一方面，Haskell VM仅比C VM慢50%。

未来方向

虽然我们的Haskell程序很快，但我们可以改进某些方面：

解析器优化：如基准测试所示，解析是我们最慢的阶段。
超级指令：我们可以分析字节码中常见的指令序列（如OPush后跟OAdd）并将它们组合成单个超级指令。
基于寄存器的VM：使用虚拟寄存器的小数组而不是基于内存的堆栈的基于寄存器的VM可以显著减少内存流量并提高性能。
即时（JIT）编译：最终的性能提升可能来自JIT编译器。

结论

我们成功地在Haskell中构建了一个字节码编译器和虚拟机。我们涵盖了解析、AST解释、编译和字节码执行，以及调试和测试功能。

从简单的AST解释器到字节码VM的旅程是富有成效的。我们看到了显著的性能改进，了解了编译器和VM的工作原理，以及如何在Haskell中编写高性能代码。虽然我们的Haskell实现不如手写C版本快，但它更简洁，并且更容易推理。这很好地展示了Haskell编写高性能——然而安全且优雅——代码的能力。