利用 JS 函数柯里化，实现高性能虚拟机（2）

[EtherDream]

前言

上一篇，我们讲解了如何将指令转换成函数，从而减少运行时开销。

然而光有转换还是不够的，如何将转换后的函数高效运行起来，才是真正的挑战。

下面开始我们的探索。。。

流程控制

计数器

传统虚拟机的流程控制，大多依靠程序计数器（program counter）实现，用以指向当前指令的位置。

计数器的方案，同样适用于我们的函数列表：

fn_list = [fn, fn, ......]
pc = 0

do {
  f = fn_list[pc++]
  f()
} while (......)

正常情况下，我们顺序执行列表中的函数；如果需要跳转，则可提供一些「能修改计数器」的指令，以实现分支、循环等效果。

计数器的原理很简单，但其效率并不高。因为每执行一条指令，都得访问数组、更新计数器、终止判断，从而产生数倍的性能开销。

那么，是否有更快的流程控制方案呢？

指令分离

既然我们要追求极致的性能，那只能牺牲一些灵活性。

冯诺伊曼结构的虚拟机，指令和数据是合为一体的，这显然非常灵活。例如，程序可以跳到指令区外，将动态数据当做指令运行；可以跳到指令中间，将半个指令当做新指令执行；甚至还可以自修改，运行时改变指令数据。

然而这并不常用。我们不妨抛弃这些小众特性，尝试将指令和数据分离，这样是否能玩出新花样？

柯里化

现在，指令始终是固定的。因此不妨将多个指令事先绑在一起，这样就能一次调用多个指令。

例如，我们捆绑这两个指令：

mod r3, r5, r7
xor r0, r0, r1

根据上一篇文章，它们先被转换成两个闭包函数：

fn_list[0] = OP2(mod, set_r3, get_r5, get_r7)
fn_list[1] = OP2(xor, set_r0, get_r0, get_r1)

现在我们需要另一个函数，用于两者的绑定。这时，柯里化又派上用场了：

function wrap2(f1, f2) {
  return function() {
    f1(); f2()
  }
}

我们将 fn_list 作为参数列表传给 wrap2，即可得到合二为一的结果：

f = wrap2.apply(null, fn_list)

之后，只需 f() 即可触发 f1()、f2()，从而实现一次调用两个指令！

模板

如果想绑定 3 个、5 个指令，又该如何实现？很简单，接着实现 wrap3、wrap5 即可。

function wrap5(f1, f2, f3, f4, f5) {
  return function() {
    f1(); f2(); f3(); f4(); f5()
  }
}

我们可提供多个版本，例如从 wrap2 直到 wrap16。这样 16 个指令以内的，即可直接绑定；超过 16 个，则可通过组合实现。

例如绑定 18 个指令，可以这样实现：

f = wrap16(x1, x2, ......, x15, wrap3(x16, x17, x18) )

因为绑定后的结果也是一个函数，所以能多层嵌套。

这样，我们就能使用链式结构，将任意多的指令绑在一起，从而实现一次调用、批量执行！

动态 vs 静态

也许你在想，为什么绑定的个数非得固定，而不动态获取呢。例如这样岂不更简单：

function wrapN() {
  const arr = arguments
  return function() {
    for (let i = 0; i < arr.length; i++)
      arr[i]()
  }
}

从做逻辑上说，这确实没问题。然而，动态对于优化是不利的，可能会导致性能降低。

我们写个简单的案例，观察动态的性能开销：

let a = 0
function inc() { a++ }

// 硬编码
console.time('t0')
for (let i = 0; i < 100000000; i++) {
  inc(); inc();
  inc(); inc();
}
console.timeEnd('t0')


// 固定个数
const f = wrap4(inc, inc, inc, inc)
console.time('t1')

for (let i = 0; i < 100000000; i++) {
  f()
}
console.timeEnd('t1')


// 动态个数
const f = wrapN(inc, inc, inc, inc)
console.time('t2')

for (let i = 0; i < 100000000; i++) {
  f()
}
console.timeEnd('t2')

在线运行：https://jsfiddle.net/jcktof8b/

由此可见，固定个数的 wrap4 耗时和硬编码相差无几，而动态个数的 wrapN 则要慢上 3 倍！

分支流程

固定分支

我们实现了顺序流程，现在来考虑分支流程。

由于没有计数器，因此像 goto 这样的跳转，显然不易实现了。不过一般情况下，我们很少会用 goto，尤其像 JS 本来就不支持，只能用 break、continue 等控制流程，跳到块头或块尾。

既然我们的目标是高性能，那不妨再牺牲一些灵活性，只提供固定的流程控制！

例如条件判断，我们通过预制的模板来实现：

function br_if(src, exp1, exp2) {
  return function() {
    src() ? exp1() : exp2()
  }
}

这样，提供条件源、分支 1、分支 2，即可生成一个「带判断功能」的闭包函数。

类似的，循环也可以这样实现。例如，一个固定次数的循环模板：

function loop(N, exp1) {
  return function() {
    for (let i = 0; i < N; i++) {
      exp1()
    }
  }
}

不过，怎样才能将现有的指令块，作为参数传给分支模板呢？

看来，我们得设计一种特殊的指令结构。

指令结构

既然程序没有 goto 这样的任意跳转，那平坦型的指令结构不再有意义，不如使用树结构：

01  add ...
02  loop 1000
03    sub ...
04    br_if r1
05      add ...
06      sub ...
07    else
08      mul ...
09      div ...

虚拟机预处理时，将 同级 的指令合在一起，作为 上级 流程模板的参数。

例如，上述 5~6 行的指令合成 f56 函数，8~9 行合成 f89：

f56 = wrap2(f5, f6)
f89 = wrap2(f8, f9)

然后通过分支模板，生成 4~9 行的分支闭包：

f49 = br_if(get_r1, f56, f89)

由于该分支与第 3 行指令位于同一级，于是合成 f39：

f39 = wrap2(f3, f49)

然后通过循环模板，生成 2~9 行的循环闭包：

f29 = loop(1000, f39)

由于该循环与第 1 行指令位于同一级，于是合成 f19：

f19 = wrap2(f1, f29)

这就是最终的根节点。调用它，即可驱动整个程序！

小结

到此，顺序流程和分支流程已实现，这个「柯里化虚拟机」总算是图灵完备了。

既然我们的目标是高性能，那么其中显然还有不少值得推敲优化的地方。下一篇，我们继续探索。

简单演示：https://www.etherdream.com/FunnyScript/CurryVM/www/

这个 Demo 很不完善，现在已有很大变化~ 当然主要分享的是思路