实现一个脚本引擎

Part VI:优化

你发现BUG了吗?

注意到了前两次的代码的好笑的东西了吗?可能有一个内存漏洞(memory leak)?Emmanuel Astier发现了;他找出了符号表中的一个BUG:当删除符号表时,我只是删除了链表中的第一个实体,而没有删除其他...OK,虽然程序没有崩溃,但是这不是很漂亮.这将在下一个教程中修改.多谢Emmanuel!

序言

我的考试结束了,我现在可能继续了.

在这部分我将涉及优化我们的中间代码的方法.记得吗,我们使用了一个非常简单的代码生成算法,所以那些代码也许相当的需要优化.

因为我们将在一个虚拟机上执行,所以优化变得格外的重要:我们的每一条指令将花费20条CPU指令去执行(很难更少),所以指令越少越好.

注意,我将只讨论与机器无关(machine-independent)的优化;面向机器的优化是一个完全不同的话题,在那里我们必须考虑象流水线效率,寄存器的使用等等这些.并且,当然的,面向机器的优化只有当你的代码在硬件上运行时才需要,这我们不需要.当然,可能有很多的方法来加速执行虚拟机本身,但是我们将在后面讨论.

对不起,这部分没有例子代码.一些优化的想法实现起来都是相当的简单,你将不会在这些问题上碰到麻烦.另外一些更复杂并且需要花大力气来实现.我没有时间来作,所以我只是给出一般的概念.

有两个重要的加速我们的代码的途径.一个是把代码翻译成更少的指令.另一个是制作更多强大的指令.

额外的操作码(Extra Opcodes)

高级的指令(Higher-level instructions)可以在VM上执行的更快,因为堆栈操作和更新指令指针的总开销是(粗略)的相同的.所以我们将忽略RISC并且为外来的代码(exotic instructions)而疯狂!;)

让我们观察一些代码.这是example.vasm的一部分,example.str的编译后的版本:

1: OP_NOP
2: OP_PUSH strconst1
3: OP_GETTOP a
4: OP_DISCARD
5: OP_PUSH strconst2
6: OP_GETTOP b
7: OP_DISCARD
8: OP_PUSH a
9: OP_PUSH b
10: OP_CONCAT
11: OP_GETTOP s
12: OP_DISCARD
13: OP_PUSH s
14: OP_PRINT

我应该注意它的一些事情.第一,在这个代码中的三个地方有一个OP_DISCARD跟随在一条OP_GETTOP的情况.我们将它它转换成一条OP_POP来提高速度,这条指令取得栈顶的值并且把它从堆栈中移走.我可以在开始时这么做,但是我想现在这样更简单.

第二,我看到了OP_PUSH; OP_GETTOP; OP_DISCARD两次.. 这是一个向"a = b"这样的简单赋值语句的代码.我们可以为它提供一个特殊的操作码OP_COPY,它把一个变量的值拷贝到另一个中.

第三,在这个程序的完整的代码中有相当多的"double pushes",两个进栈操作在一起.我们一个制作一个单独的OP_PUSH2操作码来加速它.

你或许能想出另外的高级指令.例如,一条连接一个现有字符串OP_CONCATTO操作码(s += "foo";).如果仔细的挑选他们将能够加速执行,所以花写时间来研究你的汇编代码,然后发现优化的可能.

代码变形(Code Transformations)

优化输出代码的另一个途径是吧一部分代码变形成更快的执行同样任务的某些东西.下面是一个例子.

下面是一些变形代码的算法,节约指令..(saving instructions and thus time)

绝大多数优化集中在优化一些被认为是"基本模块(basic blocks)"的一小段代码.一个基本模块有下面这些性质:你能够在开始时跳转到它里面,并且你只能在它的结尾跳出.所以在这些块的中间没有跳转或者跳转目标(jump targets).这意味着在块之内我们能够确定一件关于我们的变量的值的必然的事情,我们可以利用这个信息来优化代码.举个例子,如果你可以跳转到块内的某处,我们不能确定,t仍然保留着值(a * b - c).

指针带给基本模块优化很多困难,因为你必须确定变量没有通过一个指针被修改,而不是了基本模块的某处通过它的名字被修改.往往你不能确定这点(指向指针的指针就几乎不可能知道什么变量被改变了).

代数上等同(Algebraic identities)

一个优化代码的简单方法是使用产生相同结果的更快版本来替代原来的"天真的"计算.这些"天真的"计算的计算经常采用一个简单的代码产生方案而不是象程序员指定的那样.观察下表,十分明显.

消除通用子表达式(Common subexpression elimination)

这种优化利用某一表达式可能多次使用一小段代码的事实:

a = a + (b - 1);
c = c + (b - 1);

这里(b-1)是一个通用子表达式并且可被再次使用(第二个(b-1)表达式可以被"消除").

t = b - 1; // 把子表达式存储到一个临时变量中
a = a + t;
c = c + t;

为了检测通用子表达式,你需要构造一个出现在你表达式中基本模块的有向无环图(DAG,directed acyclic graph).每次你遇到一个新的表达式(例如,语法树中一个更高的结点),你检查在这个基本模块的它是否已经出现在表达式DAG中.当这个图完成时你能很容易的看出那个子表达式使用了多次,这样你就可以把它们的值存入一个链式变量,并且再次使用它.上图是一个例子.

循环的优化(Loop optimizations)

一个众所周知的程序员的格言"程序90%的时间花费在执行10%的代码上",尽管这个百分比每个程序都不同,但是每个人都会同意绝大多数运行时间花费在一个内层循环上.

所以如果我们能使用某种方法优化这些循环,我们就能节省很多的时间...好吧,有很多中优化循环的方法;我将简单的讨论他们中的两个,代码移动和变量归纳(code motion and induction variables).

代码移动类似与子表达式消除,但是不是在一个基本模块中,它在循环开始前计算表达式并且在循环的整个过程中使用这个值.

while ( i <= limit-2 )

变为

t = limit - 2;
while ( i <= t )

可是,循环也许没有很多的不变的表达式.它们经常使用的是一个循环技术器,并且这个技术器被频繁的使用在计算中,例如数组下标,等等.那就是变量归纳能帮我们的了.

如果j是我们的循环技术器,并且每次循环中都计算j*4,我们可以使用一个变量归纳,然后把这个乘法替代为加法:

for (j = 0; j < n; j++) {
.... (j * 4) ....
}

变为:

t = 0;
for (j = 0; j < n; j++) {
.... t ....
t += 4;
}

跳转的消除(Jump elimination)

有时你能够通过观察跳转的目的块来消去一个跳转.例如,你可能有:

1: jmp 7
...
7: str_equal
8: jmpf 10
9: ...

你可以从目的块拷贝代码,然后节省一个跳转(如果条件为假):

1a: str_equal // | 目的块的拷贝
1b: jmpf 10 // |
1c: jmp 9 // 如果条件为真,跳转到9
...
7: str_equal
8: jmpf 10
9: ...

你要决定为了消除一个跳转你将要复制多大一部分代码,但是在内层循环中它能省很多时间.

下次的东西...

这些信息使你的程序变得更有效率了.可是编译器优化是一个非常复杂的领域,我们只涉及到了非常少的一点.龙之书讨论了更多,所以如果你感兴趣,就去看它吧 .

下次我们将建立我们虚拟机,然后也许产生我们的虚拟机代码吧.那时我们就终于可以执行一个程序了.

Quote!

Somewhere on the wall a small white light flashed.

"Come," said Slartibartfast, "you are to meet the mice. Your arrival on the planet has caused considerable excitement. It has already been hailed, so I gather, as the third most improbable event in the history of the Universe."

"What were the first two?"

"Oh, probably just coincidences," said Slartibartfast carelessly.

HHG 1:30