对于实现功能语言的虚拟机,有哪些明显的优化？

Question

我正在研究一种中间语言和一个虚拟机来运行具有一些"有问题"属性的函数式语言:

• 词法命名空间(闭包)
• 动态增长的调用堆栈
• 慢整数类型(bignums)

中间语言是基于堆栈的,具有当前命名空间的简单哈希表.只是让你了解它的外观,这是McCarthy91的功能:

# McCarthy 91: M(n) = n - 10 if n > 100 else M(M(n + 11))
.sub M
    args
    sto n

    rcl n
    float 100
    gt
    .if
        .sub
            rcl n
            float 10
            sub
        .end
        .sub
            rcl n
            float 11
            add
            list 1
            rcl M
            call-fast
            list 1
            rcl M
            tail
        .end
    call-fast
.end

"大循环"很简单:

• 获取指令
• 递增指令指针(或程序计数器)
• 评估指令

随着sto,rcl和一大堆更多,有三种指令函数调用:

• call 复制命名空间(深层复制)并将指令指针推送到调用堆栈
• call-fast 是相同的,但只创建一个浅的副本
• tail 基本上是'转到''

实施非常简单.为了给你一个更好的主意,这里只是一个来自"大循环"中间的随机片段(更新,见下文)

    } else if inst == 2 /* STO */ {
        local[data] = stack[len(stack) - 1]
        if code[ip + 1][0] != 3 {
            stack = stack[:len(stack) - 1]
        } else {
            ip++
        }
    } else if inst == 3 /* RCL */ {
        stack = append(stack, local[data])
    } else if inst == 12 /* .END */ {
        outer = outer[:len(outer) - 1]
        ip = calls[len(calls) - 1]
        calls = calls[:len(calls) - 1]
    } else if inst == 20 /* CALL */ {
        calls = append(calls, ip)
        cp := make(Local, len(local))
        copy(cp, local)
        outer = append(outer, &cp)
        x := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        ip = x.(int)
    } else if inst == 21 /* TAIL */ {
        x := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        ip = x.(int)

问题是这样的:调用McCarthy91 16次,值为-10000,接近没有差别,3秒(优化掉深拷贝后,增加了近一秒).

我的问题是:优化这种语言的解释有哪些常用技巧？有没有悬挂水果？

我使用切片作为我的列表(参数,各种堆栈,命名空间的地图切片,......),所以我在这个地方做了这样的事情:call_stack[:len(call_stack) - 1].现在,我真的不知道哪些代码会使这个程序变慢.任何提示将不胜感激,但我主要是寻找一般的优化策略.

在旁边:

通过规避我的调用约定,我可以减少执行时间.该list <n>指令获取堆栈的n个参数并将它们的列表推回到堆栈中,该args指令弹出该列表并将每个项目推回堆栈.这首先要检查函数是否使用正确数量的参数调用,其次是能够使用可变参数列表调用函数(即(defun f x:xs)).删除它,并添加一个sto* <x>替换的指令sto <x>; rcl <x>,我可以将它降低到2秒.仍然没有辉煌,无论如何我必须有这个list/ args商业.:)

另一个(这是一个很长的问题,我知道,对不起):

用pprof对程序进行分析很少告诉我(我是Go的新手,以防不明显):-).这些是pprof报告的前3项:

  16   6.1%   6.1%       16   6.1% sweep               pkg/runtime/mgc0.c:745
   9   3.4%   9.5%        9   3.4% fmt.(*fmt).fmt_qc   pkg/fmt/format.go:323
   4   1.5%  13.0%        4   1.5% fmt.(*fmt).integer  pkg/fmt/format.go:248

这些是我到目前为止所做的改变:

• 我删除了哈希表.相反,我现在只传递指向数组的指针,而且只在必要时才有效地复制本地范围.
• 我用整数操作码替换了指令名.以前,我浪费了相当多的时间来比较字符串.
• 该call-fast指令消失(增速是无法衡量的其他变动后了)
• 我没有"int","float"和"str"指令,而是只有一个eval,我在编译时评估常量(编译字节码).然后eval只是推送它们的引用.
• 在改变语义之后.if,我可以摆脱这些伪函数.现在.if,.else并且.endif,隐含的getos和块语义类似于.sub.(一些示例代码)

在实现词法分析器,解析器和字节码编译器之后,速度有点下降,但并非如此.计算MC(-10000)16次使其在1.2秒内评估420万字节码指令.下面是它生成的代码的一个样品(从这个).

整件事都在github上

Answer 1

有几十年的研究可以优化:

• 实现函数式语言:教程,Simon Peyton Jones和David Lester.由Prentice Hall出版,1992年.
• 编程语言的实用基础,Robert Harper

Answer 2

您应该对解释器的各种概念进行有效的算法表示。在哈希表上进行深度复制看起来是一个糟糕的主意，但我看到您已经删除了它。

（是的，您使用数组切片的堆栈弹出操作看起来很可疑。您应该确保它们确实具有预期的算法复杂性，否则使用专用数据结构（...堆栈）。我通常对使用所有 -用于此用途的数据结构（例如 Python 列表或 PHP 哈希表），因为它们不一定旨在很好地处理此特定用例，但切片可能确实保证在所有情况下的推送和弹出成本为 O(1)。）

处理环境的最佳方法，只要它们不需要被具体化，就是使用数字索引而不是变量（de Bruijn 索引（0 表示最后一个变量绑定）或 de Bruijn 级别（0 表示变量绑定）首先）。这样你只能为环境保留一个动态调整大小的数组，并且访问它非常快。如果你有一流的闭包，你还需要捕获环境，这将更加昂贵：您必须将其中的一部分复制到专用结构中，或者对整个环境使用非可变结构。只有实验才能证明，但我的经验是，选择一个快速的可变环境结构并为闭包构建支付更高的成本比拥有一个始终保持更多簿记的不可变结构更好；当然，您应该进行使用分析以仅捕获闭包中的必要变量。

最后，一旦你根除与你的算法选择相关的低效率来源，热点区域将是：

• 垃圾收集（绝对是一个很难的话题；如果你不想成为 GC 专家，你应该认真考虑重用现有的运行时）；您可能正在使用宿主语言的 GC（解释语言中的堆分配被翻译成实现语言中的堆分配，具有相同的生命周期），在您显示的代码片段中不清楚；这种策略非常适合以简单的方式获得合理有效的东西

• 数字实现；当您操作的整数实际上很小时，有各种技巧可以提高效率。最好的办法是重用在这方面投入大量精力的人的工作，所以我强烈建议你重用例如GMP 库。再说一次，你也可以重用你的宿主语言对 bignum 的支持，如果它有一些的话，在你的情况下是 Go 的math/big包。

• 解释器循环的低级设计。在像你这样具有“简单字节码”的语言中（每个字节码指令都被翻译成少量的本机指令，而不是具有高级语义的复杂字节码，例如 Parrot 字节码），实际的“循环和分派字节码” “代码可能是一个瓶颈。关于编写此类字节码调度循环的最佳方法、避免 if/then/else（跳转表）的级联、受益于主机处理器分支预测、简化控制流等，已经有很多研究。这称为线程代码，有很多（相当简单）不同的技术：直接线程、间接线程……如果您想查看一些研究，例如 Anton Ertl 的工作，2003 年的高效解释器的结构和性能，以及后来的上下文线程：一种灵活高效的虚拟机解释器调度技术。这些技术的好处往往对处理器相当敏感，因此您应该自己测试各种可能性。

虽然 STG 的工作很有趣（Peyton-Jones 关于编程语言实现的书很棒），但它在某种程度上是面向惰性求值的。关于为严格的函数式语言设计高效字节码，我参考的是 Xavier Leroy 1990 年在 ZINC 机器上的工作：The ZINC 实验：ML Language 的经济实现，这是ML 语言实现的开创性工作，是仍在 OCaml 语言的实现中使用：既有字节码，也有本机编译器，但字节码仍然使用美化的 ZINC 机器。