机器指令翻译成 JavaScript —— No.3 流程分割

上一篇 我们讨论了跳转指令,并实现「正跳转」的翻译,但最终困在「负跳转」上。而且,由于线程模型的差异,我们不能 1:1 的翻译,必须对流程进行一些改造。

当初之所以选择翻译,而不是模拟,就是出于性能考虑。但是,这并不意味绝对不能用模拟 —— 如果能用少量模拟,解决一些技术障碍,那也是值得的。

现在,我们尝试用模拟的方式,来控制流程。

流程模拟

JS 的流程控制,就好比排队:如果你不想排了,可以随时退出,大家都不介意;但是之后又想回来插队,这就不行了,你必须从头排起。所以,只能退出,不能插入。

插入就类似指令跳入,所以得尽量避开。我们以跳入点(下图带箭头的)为界线,将指令分割成多块:

                        -------------
XXX 1 | block 0 |
JXX L2 --. | |
XXX 2 | | |
L1: | <-. ~~~~~~~~~~~~~~~~~~~
XXX 3 | | | block 1 |
XXX 4 | | | |
L2: <-| | ~~~~~~~~~~~~~~~~~~~
XXX 5 | | block 2 |
XXX 6 | | |
JXX L1 --| | |
XXX 7 -------------

这样,每个块中就没有跳入点了,满足 JS 的需求。现在要做的,就是块与块之间的控制。

我们先把每个块,包裹成单独的 function:

function block_0() {
XXX 1
... // JXX L2
XXX 2
} function block_1() {
XXX 3
XXX 4
} function block_2() {
XXX 5
XXX 6
... // JXX L1
XXX 7
}

为什么要用函数?因为函数可以赋给变量。通过函数变量,可灵活操控流程:

var nextFn = block_0;   // 用这个变量,模拟流程控制

function block_0() {
XXX 1
if (...) { // JXX L2
nextFn = block_2;
return;
}
XXX 2
nextFn = block_1 // 默认下一块
} function block_1() {
XXX 3
XXX 4
nextFn = block_2 // 默认下一块
} function block_2() {
XXX 5
XXX 6
if (...) { // JXX L1
nextFn = block_1;
return;
}
XXX 7
nextFn = null // end
}

这样,就能通过 nextFn 控制流程了。我们用一个简单的状态机,就能驱动这些指令块:

while (nextFn) {
nextFn();
}

这样,就解决跳转问题了!

对于普通指令,仍然是 1:1 的翻译;只有跳转时,才会用这种方式。因此总体效率仍然很高。

事实上,这其中还可以再优化 —— 我们只切割负跳转,正跳转尽可能使用 do..while(0) 来实现,因此还可以再减少分割的块数。

时钟频率

使用现在这种方案,线程模型的问题自然也可以解决了。

我们不再用死循环,而是用定时器去驱动,每一桢执行若干个块,这样就不会卡死浏览器了:

setInterval(function() {
nextFn();
nextFn();
...
}, 20);

那么,每一桢究竟执行多少次 nextFn 呢?这就看模拟的 CPU 时钟频率了。

假设以 1MHz 的频率运行,也就是每秒 100 万个周期。脚本定时器每秒触发 50 桢,那么每一帧得跑 2 万个周期:

setInterval(function() {
cycle_remain = 20000; while (cycle_remain > 0) {
nextFn();
}
}, 20);

每个指令的周期,基本都是固定的,可以查考文档。所以翻译时,每个流程会消耗多少周期,也是确定的。例如:

function block_1() {
...
if (...) {
nextFn = ...
cycle_remain -= 8 // 在此跳出,本流程消耗 8 周期
return
}
...
cycle_remain -= 12 // 运行到此,本流程消耗 12 周期
}

当周期用尽时,就完成这一桢的工作,等待下一帧触发。这样就不至于 100% 占用的浏览器资源,有充足的时间处理输入和输出。

死循环的问题,就这样解决了。

降低误差

为了提高性能,这里只在流程切换时,才会判断周期;而不是传统模拟器那样,每执行一个指令判断一次。

当然,这么做会有些误差:最后一个流程执行完,cycle_remain 不一定正好等于 0。事实上大多时候都是负数(超标),于是导致速度偏快。

为了消除误差,我们可以把超标的数量,在下一帧里扣除。例如本次 cycle_remain 最终是 -100,那么下一桢的 cycle_remain 则初始化为 19900。

这样,虽然每一帧有些波动,但在宏观上,还是相对稳定的。


思考题

回到上一章。假设 跳转指令能 1:1 翻译成 JS,那么我们就用不着分割流程了。这时是否能用一些其他技术,解决时钟频率的问题?

其实在如今 ES6 版 JS 中,又新增了一个强大的流程控制武器 —— yield。

yield 允许在函数任意位置跳出,之后可以回到那个位置,继续运行。

因此,可在负跳转之前判断周期,如果超了,则 yield 出去,让浏览器有喘息的机会:

function* routine() {
L1: do {
...
if (...) { // JXX L1
if (cycle_remain < 0) yield
continue L1
}
...
} while (0)
}

等到休息完成,还可以回到上次的位置继续工作。

这看起来十分好用!但是我们没用它。并非兼容性问题,也不是性能问题,而是:这一节的前提纯属 假设

结尾

这一篇和前一篇,我们讨论的只是「静态跳转」的情况。但事实上 6502 指令集还支持「动态跳转」,这又该如何实现?

下一篇,我们讨论如何处理动态跳转。

上一篇:Opencv中KNN背景分割器


下一篇:13 KNN背景分割器