rakulang, dartlang, nimlang, golang, rustlang, lang lang no see

争取在 MoarVM 中建立一个新的总调度机制

焉知非鱼

Towards a New General Dispatch Mechanism in Moarvm

我的天啊,看来我是两年多来第一次写 Raku 内部的博文了。当然,两年前还不叫 Raku。总之,话不多说,继续说说这个共同的脑洞吧。

什么是调度? #

我用 “dispatch” 来表示我们接受一组参数,最后根据这些参数采取一些行动的过程。一些熟悉的例子包括:

  • 进行一个方法调用,比如 $basket.add($product, $quantity)。传统上,我们可能只调用 $product$qauntity 作为参数,但就我的目的而言,所有的 $basket、方法名 “add”、$product$quantity 都是 dispatch 的参数:它们是我们需要的东西,以便决定我们要做什么。

  • 进行子程序调用,如 uc($youtube-comment)。由于 Raku sub 调用是词法解析的,所以在这种情况下,调度的参数是 &uc(查找子程序的结果)和 $youtube-comment

  • 调用多个调度子程序或方法,根据参数的数量和类型来决定调用一组候选程序中的哪一个。这个过程可以看作是发生在上述两个调度中的一个 “内部”,因为我们在 Raku 中既有多重调度子程序,也有方法。

乍一看,也许前两个看起来相当简单,第三个就有点手忙脚乱了 - 这也算是事实。然而,Raku 还有一些其他的特性,使得调度变得相当,嗯,有趣。例如:

  • wrap 允许我们包装任何 Routine (sub 或方法); 包装器可以选择用原来的参数或新的参数来服从原来的例程。

  • 当进行多重调度时,我们可以写一个原型例程,让它选择何时 - 甚至是否 - 调用合适的候选者。

  • 我们可以使用 callsame 这样的例程,以便在调度中推迟到下一个候选者。但这意味着什么呢?如果我们是在一个多重调度中,它意味着下一个最适用的候选者,如果有的话。如果我们是在一个方法调度中,那么它意味着一个基类的方法。(同样的事情也被用来实现去下一个封装者,或者,最终也是去最初封装的例程)。而且这些都可以结合起来:我们可以包装一个 multi 方法,这意味着我们可以有 3 个层次的东西,都有可能贡献下一个要调用的东西!

多亏了这一点,dispatch - 至少在 Raku 中 - 并不总是我们所做的事情并产生一个结果,而是一个可能会被要求继续多次进行的过程!

最后,虽然我上面所写的例子都可以很清楚地看成是调度的例子,但在 Raku 中,其他一些常见的构造也可以表达为一种调度。分配是一个例子:它的语义取决于分配的目标和被分配的值,因此我们需要选择正确的语义。强制类型转换(Coercion)是另一个例子,返回值类型检查又是一个例子。

为什么调度很重要? #

Dispatch 在我们的程序中无处不在,它悄悄地把想做事情的代码和做事情的代码联系在一起。它的无处不在意味着它在程序性能中扮演着重要的角色。在最好的情况下,我们可以将成本降为零。在最坏的情况下,调度的成本高到足以超过作为调度结果的工作的成本。

初步估计,当运行时"理解"调度时,性能至少会有些不错,但当运行时不理解时,很有可能会很糟糕。调度往往涉及到一个可以缓存的工作量,往往会有一些廉价的防护措施来验证缓存结果的有效性。例如,在方法调度中,天真地我们需要走一个线性化的继承图,并询问沿途遇到的每个类是否有指定名称的方法。显然,如果我们在每次方法调用时都这样做,速度不会非常快。然而,特定类型上的特定方法名(精确识别,不考虑子类)每次都会解析到同一个方法。因此,我们可以缓存查找的结果,只要调用者的类型与用于产生缓存结果的类型相匹配,就可以使用它。

语言运行时的专门化与通用化机制 #

当一个人开始构建一个针对特定语言的运行时,并且必须在相当紧张的预算下完成时,要想获得某种可容忍的性能,最明显的方法就是将各种热路径语言语义烘焙到运行时中。这正是 MoarVM 的起步方式。因此,如果我们看看 MoarVM 几年前的样子,我们会发现这样的事情。

  • 对方法缓存的一些支持
  • 一个与 Raku 的多重调度语义高度绑定的多重调度缓存,只有在调度都是名义类型的时候才真正能够起到帮助作用(所以使用 where 的代价非常高)。
  • 一种机制,用于指定如何在封装代码对象内部找到实际的代码句柄(例如,Sub 对象有一个私有属性,它持有识别要运行的字节码的低级代码句柄)。
  • 一些有限的尝试,让我们能够在知道一个调度不会继续的情况下正确地进行优化 - 这需要编译器和运行时之间的谨慎合作(或者不那么外交地讲,这都是一个大黑客)。

这些今天都还在,然而也都在淘汰的路上。这个榜单最能说明问题的是什么,不包括在内。比如:

  • 私有方法调用,需要不同的缓存 但最初的虚拟机设计限制了每一种类型的调用
  • 合格的方法调用($obj.SomeType::method-name())
  • 体面优化调度恢复的方法

几年前,我开始部分解决这个问题,引入了一种机制,我称之为 “specializer 插件”。但首先,什么是特化器(specializer)?

MoarVM 刚开始的时候,它是一个比较简单的字节码解释器。它只需要足够快的速度击败 Parrot VM 就可以获得相当的使用量,我认为在继续实现一些更有趣的优化之前,这一点非常重要(当时我们还没有今天这样的发布前自动测试基础设施,因此更多的是依赖于早期采用者的反馈)。总之,在能够像其他后端一样运行 Raku 语言后不久,我就开始了动态优化器的开发。它在程序被解释时收集类型统计,识别热代码,将其放入 SSA 形式,使用类型统计插入防护,将这些与字节码的静态属性一起使用来分析和优化,并为相关函数生成专门的字节码。这个字节码可以省略类型检查和各种查找,也可以使用一系列的内部操作,做出各种假设,由于优化器证明了程序的属性,这些假设是安全的。这被称为专门化的字节码,因为它的很多通用性 - 这将使它能够正确地工作在我们可能遇到的所有类型的值上 - 被删除了,转而工作在运行时实际发生的特殊情况下。(代码,尤其是动态语言中的代码,一般来说,理论上的通用性远远大于实践中的通用性。)

这个组件 - 内部称为 “spesh” 的 specializer - 为 Raku 程序的性能带来了显著的进一步提升,随着时间的推移,它的复杂程度也在不断提高,并采用了内联带有标量替换的转义分析等优化功能。这些并不是容易构建的东西 - 但一旦运行时拥有了它们,它们就会创造出以前不存在的设计可能性,并使在没有它们的情况下做出的决定看起来是次优的。

值得注意的是,那些特殊情况下的语言特定机制,在早期为了获得一些速度而被嵌入到运行时中,反而成为了一种负担和瓶颈。它们具有复杂的语义,这意味着它们对优化器来说要么是不透明的(所以优化器无法对它们进行推理,意味着优化受到抑制),要么就是需要在优化器中进行特殊的封装(一种负担)。

所以,回到 specializer 插件。我到了一个地步,我想承担像 $obj.?meth("call me maybe", dispatch)$obj.SomeType::meth()(用类开始寻找的调度限定),以及角色中的私有方法调用(不能静态解析)这样的性能。同时,我还准备实现一定量的转义分析,但意识到它的作用将非常有限,因为赋值在虚拟机中也被特例化了,有一大块不透明的 C 代码在做热路径的事情。

但为什么我们要让 C 代码来做那些热路径的事情呢?嗯,因为让每个赋值都调用一个虚拟机级别的函数,做一堆检查和逻辑,花费太大了。为什么这样做成本很高?因为函数调用的开销和解释的成本。这在以前都是正确的。但是,若干年后的发展。

  • 内联被实现了,并且可以消除做一个函数调用的开销。
  • 我们可以编译成机器代码,消除解释开销。
  • 我们当时的处境是,我们手头有 specializer 的类型信息,可以让我们消除 C 代码中的分支,但由于我们调用的只是一个不透明的函数,所以没有办法抓住这个机会

我解决了上面提到的分配问题和调度问题,引入了一个新的机制:specializer 插件。它们的工作原理如下。

  • 当我们第一次到达字节码中的一个给定的调用点时,我们就会运行这个插件。它产生了一个要调用的代码对象,以及一组守卫(为了使用该代码对象结果而必须满足的条件)。
  • 下一次到达时,我们检查是否满足守卫,如果满足,就用结果
  • 如果没有,我们再运行一次插件,并在 callsite 处堆积一个防护集。
  • 我们统计了一个给定的防护集成功的频率,然后将其用于 specializer

绝大多数情况下都是单态的,这意味着只产生一组守卫,而且之后总是成功的。因此,特殊化器可以将这些守卫编译到专门的字节码中,然后假设给定的目标调用者就是将被调用的守卫。(进一步,重复的守卫可以被消除,所以某个插件引入的守卫可能会减少到零)。

Specializer 插件感觉挺好的。一个新机制解决了多个优化头疼的问题。

新的 MoarVM 调度机制是对一个相当简单的问题的回答:如果我们把所有与调度相关的特例机制去掉,而采用有点像 specializer 插件的机制,会怎么样?由此产生的机制需要是一个比 specializer 插件更强大的机制。进一步说,我可以学习特殊器插件的一些缺点。因此,虽然它们会在比较短的寿命后消失,但我认为可以说,如果没有这些经验,我就不会有能力设计新的 MoarVM 调度机制。

调度操作和引导调度器 #

所有的方法缓存。所有的多重调度缓存。所有的 specializer 插件。所有用于在代码对象中解包字节码句柄的调用协议的东西。这一切都将被取消,取而代之的是一个新的调度指令。它的名字很无聊,叫 dispatch。它看起来像这样。

dispatch_o result, 'dispatcher-name', callsite, arg0, arg1, ..., argN

这意味着:

  • 使用名为 dispatcher-name 的调度器。
  • 给它指定的参数寄存器(所引用的调用点表示参数的数量)。
  • 将调度的对象结果放入寄存器结果中。

(旁白:这意味着一个新的调用约定,即我们不再将参数复制到参数缓冲区,而是将寄存器集的基数和一个指针传递到找到寄存器参数映射的字节码中,然后做一个查询 registers[map[argument_index]] 来获取一个参数的值。仅此一点,我们在解释时就很省事,因为我们不再需要每个参数绕着解释器循环了)。)

有些参数可能是我们传统上称之为参数的东西。有些则是针对调度过程本身。这其实并不重要 - 但如果我们安排将只针对调度的参数放在前面(例如,方法名),而将针对调度目标的参数放在后面(例如,方法参数),则会更加理想。

新的 bootstrap 机制提供了少量的内置调度器,它们的名字以 “boot-” 开头。它们是:

  • boot-value - 取第一个参数并将其作为结果(身份函数,除了丢弃任何其他参数)。
  • boot-constant - 取第一个参数并将其作为结果,但同时也将其视为一个将始终产生的常量值(因此意味着优化器可以将任何用于计算该值的纯代码视为死值)。
  • boot-code - 取第一个参数(必须是虚拟机字节码句柄),并运行该字节码,将其余参数作为参数传给它;评估为字节码的返回值。
  • boot-syscall - 将第一个参数视为虚拟机提供的内置操作的名称,然后调用它,并将其余参数作为其参数。
  • boot-resume - 恢复正在进行的最上层调度。

差不多就是这样。我们构建的每一个调度器,为了教给运行时一些其他的调度行为,最终都会终止于其中一个。

在引导程序的基础上 #

教 MoarVM 了解不同种类的调度,不外乎使用调度机制本身! 在大多数情况下,boot-syscall 被用来注册一个调度器,设置守卫,并提供与它们相匹配的结果。

这里是一个最小的例子,取自 dispatcher 测试套件,展示了一个提供同一性功能的 dispatcher 的样子。

nqp::dispatch('boot-syscall', 'dispatcher-register', 'identity', -> $capture {
    nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'boot-value', $capture);
});
sub identity($x) {
    nqp::dispatch('identity', $x)
}
ok(identity(42) == 42, 'Can define identity dispatch (1)');
ok(identity('foo') eq 'foo', 'Can define identity dispatch (2)');

在第一条语句中,我们调用 dispatcher-register MoarVM 系统调用,传递一个 dispatcher 的名称以及一个闭包,每次我们需要处理调度时,都会调用这个闭包(我倾向于将其称为"调度回调")。它接收一个单一的参数,这是一个参数的捕获(其实不是 Raku 级别的捕获,但想法 - 一个包含一组调用参数的对象 - 是一样的)。

每一个用户定义的调度器最终都应该使用 dispatcher-delegate,以便确定另一个调度器将控制权传递给它。在这种情况下,它立即委托给 boot-value - 这意味着它除了是 boot-value 内置调度器的包装器外,其实什么都不是。

sub identity 包含一个调度操作的静态出现。鉴于我们两次调用 sub,我们在运行时将两次遇到这个 op,但这两次是非常不同的。

第一次是 “记录” 阶段。参数形成一个捕获,回调运行,回调又将其传给引导值调度器,产生结果。这样就形成了一个极其简单的调度程序,它说结果应该是捕获中的第一个参数。由于没有守卫,所以这将永远是一个有效的结果。

第二次遇到调度操作时,它那里已经记录了一个调度程序,所以我们处于运行模式。在 MoarVM 源码中开启调试模式,我们可以看到结果的调度程序是这样的。

Dispatch program (1 temporaries)
  Ops:
    Load argument 0 into temporary 0
    Set result object value from temporary 0

也就是说,它将参数 0 读入一个临时位置,然后将其设置为调度的结果。请注意,没有提到我们经过了额外的一层调度,这些在结果调度程序中的成本为零。

捕获操作 #

参数捕获是不可改变的。各种虚拟机系统调用的存在,可以通过一些调整将它们转化为新的参数捕获,例如删除或插入参数。这里还有一个测试套件的例子。

nqp::dispatch('boot-syscall', 'dispatcher-register', 'drop-first', -> $capture {
    my $capture-derived := nqp::dispatch('boot-syscall', 'dispatcher-drop-arg', $capture, 0);
    nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'boot-value', $capture-derived);
});
ok(nqp::dispatch('drop-first', 'first', 'second') eq 'second',
    'dispatcher-drop-arg works');

这就在将捕获传递给引导值调度器之前丢弃了第一个参数 - 意味着它将返回第二个参数。回头看一下之前的身份函数的调度程序。你能猜到这个程序会是什么样子吗?

好吧,就是这样。

Dispatch program (1 temporaries)
  Ops:
    Load argument 1 into temporary 0
    Set result string value from temporary 0

同样,虽然在这样一个调度器的记录阶段,我们确实是创建了捕获对象,并做了一个调度器代理,但由此产生的调度程序要简单得多。

下面是一个稍微复杂一点的例子。

my $target := -> $x { $x + 1 }
nqp::dispatch('boot-syscall', 'dispatcher-register', 'call-on-target', -> $capture {
    my $capture-derived := nqp::dispatch('boot-syscall',
            'dispatcher-insert-arg-literal-obj', $capture, 0, $target);
    nqp::dispatch('boot-syscall', 'dispatcher-delegate',
            'boot-code-constant', $capture-derived);
});
sub cot() { nqp::dispatch('call-on-target', 49) }
ok(cot() == 50,
    'dispatcher-insert-arg-literal-obj works at start of capture');
ok(cot() == 50,
    'dispatcher-insert-arg-literal-obj works at start of capture after link too');

这里,我们有一个存储在变量 $target 中的闭包。我们把它作为捕获的第一个参数插入,然后委托给 boot-code-constant,它将调用那个代码对象,并把其他调度参数传递给它。再次,在记录阶段,我们真正要做的事情是这样的。

  • 创建一个新的捕获 在开始的时候插入一个代码对象。
  • 委托给引导代码常量分配器,它…。
  • …在没有原始参数的情况下创建一个新的捕获,并使用这些参数运行字节码。

由此产生的调度程序呢?就是这个

Dispatch program (1 temporaries)
  Ops:
    Load collectable constant at index 0 into temporary 0
    Skip first 0 args of incoming capture; callsite from 0
    Invoke MVMCode in temporary 0

也就是说,加载我们要调用的常量字节码句柄,设置 args(在本例中等于传入捕获的参数),然后用这些参数调用字节码。参数的洗牌,又一次消失了。一般来说,只要我们做最终的字节码调用的参数是初始调度参数的尾巴,参数转换就会变得不过是一个指针的添加。

守卫 #

目前看到的所有调度方案都是无条件的:一旦在某一通话地点记录下来,就应一直使用。要使这样的机制具有实用性,缺少的一大块就是守卫。守卫断言了一些属性,比如参数的类型或者参数是确定的(Int:D)还是不确定的(Int:U)。

下面是一个有点长的测试用例,并在其中放置了一些解释。

# A couple of classes for test purposes
my class C1 { }
my class C2 { }
 
# A counter used to make sure we're only invokving the dispatch callback as
# many times as we expect.
my $count := 0;
 
# A type-name dispatcher that maps a type into a constant string value that
# is its name. This isn't terribly useful, but it is a decent small example.
nqp::dispatch('boot-syscall', 'dispatcher-register', 'type-name', -> $capture {
    # Bump the counter, just for testing purposes.
    $count++;
 
    # Obtain the value of the argument from the capture (using an existing
    # MoarVM op, though in the future this may go away in place of a syscall)
    # and then obtain the string typename also.
    my $arg-val := nqp::captureposarg($capture, 0);
    my str $name := $arg-val.HOW.name($arg-val);
 
    # This outcome is only going to be valid for a particular type. We track
    # the argument (which gives us an object back that we can use to guard
    # it) and then add the type guard.
    my $arg := nqp::dispatch('boot-syscall', 'dispatcher-track-arg', $capture, 0);
    nqp::dispatch('boot-syscall', 'dispatcher-guard-type', $arg);
 
    # Finally, insert the type name at the start of the capture and then
    # delegate to the boot-constant dispatcher.
    nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'boot-constant',
        nqp::dispatch('boot-syscall', 'dispatcher-insert-arg-literal-str',
            $capture, 0, $name));
});
 
# A use of the dispatch for the tests. Put into a sub so there's a single
# static dispatch op, which all dispatch programs will hang off.
sub type-name($obj) {
    nqp::dispatch('type-name', $obj)
}
 
# Check with the first type, making sure the guard matches when it should
# (although this test would pass if the guard were ignored too).
ok(type-name(C1) eq 'C1', 'Dispatcher setting guard works');
ok($count == 1, 'Dispatch callback ran once');
ok(type-name(C1) eq 'C1', 'Can use it another time with the same type');
ok($count == 1, 'Dispatch callback was not run again');
 
# Test it with a second type, both record and run modes. This ensures the
# guard really is being checked.
ok(type-name(C2) eq 'C2', 'Can handle polymorphic sites when guard fails');
ok($count == 2, 'Dispatch callback ran a second time for new type');
ok(type-name(C2) eq 'C2', 'Second call with new type works');
 
# Check that we can use it with the original type too, and it has stacked
# the dispatch programs up at the same callsite.
ok(type-name(C1) eq 'C1', 'Call with original type still works');
ok($count == 2, 'Dispatch callback only ran a total of 2 times');

这个时候就会产生两个调度程序,一个是 C1。

Dispatch program (1 temporaries)
  Ops:
    Guard arg 0 (type=C1)
    Load collectable constant at index 1 into temporary 0
    Set result string value from temporary 0

另一个是 C2:

Dispatch program (1 temporaries)
  Ops:
    Guard arg 0 (type=C2)
    Load collectable constant at index 1 into temporary 0
    Set result string value from temporary 0

再一次,没有捕获操作、跟踪或调度器委托的遗留问题;调度程序对一个参数进行类型防护,然后产生结果字符串。整个对 $arg-val.HOW.name($arg-val) 的调用都被省略了,我们写的调度程序将知识进行了编码 - 以虚拟机能够理解的方式 - 一个类型的名称可以被认为是不可改变的。

这个例子有点造作,但现在考虑一下,我们反而要查找一个方法,并在调用者类型上进行守卫:这就是一个方法缓存! 守护更多参数的类型,我们就有了一个多缓存。两者都做,我们就有了一个多方法缓存。

后者很有意思,因为方法调度和多调度都想对调用者进行守护。事实上,在 MoarVM 中,今天会有两个这样的类型测试,直到我们到了特殊化器做工作并消除这些重复的守卫。然而,新的调度器并没有将调度器 - guard-类型当作一种命令式操作,将守卫写入结果调度程序中。相反,它声明相关的参数必须被防护。如果其他的调度器已经这样做了,那它就是幂等的。一旦我们委派通过的所有调度程序,在通往最终结果的路径上,都有了自己的发言权,就会发出守卫。

有趣的是:特别细心的人会注意到,调度机制也被用作实现新的调度程序的一部分,事实上,这最终也将意味着特殊化者可以将调度程序特殊化,让它们也被 JIT 编译成更高效的东西。毕竟,从 MoarVM 的角度来看,这一切都只是要运行的字节码,只是有些字节码是告诉 VM 如何更高效地执行 Raku 程序的!

恢复调度 #

可恢复调度器需要做两件事。

  • 在注册调度器的时候,提供一个恢复回调和一个调度回调。
  • 在 dispatch 回调中,指定一个捕获,这将形成恢复初始化状态。

当发生恢复时,将调用恢复回调,并提供恢复的任何参数。它还可以获得在 dispatch 回调中设置的 resume 初始化状态。resume 初始化状态包含了第一次恢复调度时继续进行调度所需要的东西。我们先来看看方法调度的工作原理,看一个具体的例子。我也会在此时,切换到看真正的 Rakudo 调度器,而不是简化的测试用例。

Rakudo 调度器利用授权、重复守卫和捕获操作都没有运行时成本的优势,在结果调度程序中,至少在我看来,很好地因素了一个有些复杂的调度过程。方法调度有多个切入点:普通无聊的 $obj.meth(),限定的 $obj.Type::meth(),以及调用我也许 $obj.?meth()。这些都有共同的 resume 语义 - 或者至少,只要我们在 resume 初始化状态中始终携带一个起始类型,也就是我们做方法调度的对象的类型,就可以使它们成为。

这里是普通方法调度的切入点,去掉了报告缺失方法错误的无聊细节。

# A standard method call of the form $obj.meth($arg); also used for the
# indirect form $obj."$name"($arg). It receives the decontainerized invocant,
# the method name, and the the args (starting with the invocant including any
# container).
nqp::dispatch('boot-syscall', 'dispatcher-register', 'raku-meth-call', -> $capture {
    # Try to resolve the method call using the MOP.
    my $obj := nqp::captureposarg($capture, 0);
    my str $name := nqp::captureposarg_s($capture, 1);
    my $meth := $obj.HOW.find_method($obj, $name);
 
    # Report an error if there is no such method.
    unless nqp::isconcrete($meth) {
        !!! 'Error reporting logic elided for brevity';
    }
 
    # Establish a guard on the invocant type and method name (however the name
    # may well be a literal, in which case this is free).
    nqp::dispatch('boot-syscall', 'dispatcher-guard-type',
        nqp::dispatch('boot-syscall', 'dispatcher-track-arg', $capture, 0));
    nqp::dispatch('boot-syscall', 'dispatcher-guard-literal',
        nqp::dispatch('boot-syscall', 'dispatcher-track-arg', $capture, 1));
 
    # Add the resolved method and delegate to the resolved method dispatcher.
    my $capture-delegate := nqp::dispatch('boot-syscall',
        'dispatcher-insert-arg-literal-obj', $capture, 0, $meth);
    nqp::dispatch('boot-syscall', 'dispatcher-delegate',
        'raku-meth-call-resolved', $capture-delegate);
});

现在是解析方法 dispatcher,也就是处理恢复的地方。首先,让我们看看正常的 dispatch 回调(恢复回调是包含的,但是是空的,我稍后会展示它)。

# Resolved method call dispatcher. This is used to call a method, once we have
# already resolved it to a callee. Its first arg is the callee, the second and
# third are the type and name (used in deferral), and the rest are the args to
# the method.
nqp::dispatch('boot-syscall', 'dispatcher-register', 'raku-meth-call-resolved',
    # Initial dispatch
    -> $capture {
        # Save dispatch state for resumption. We don't need the method that will
        # be called now, so drop it.
        my $resume-capture := nqp::dispatch('boot-syscall', 'dispatcher-drop-arg',
            $capture, 0);
        nqp::dispatch('boot-syscall', 'dispatcher-set-resume-init-args', $resume-capture);
 
        # Drop the dispatch start type and name, and delegate to multi-dispatch or
        # just invoke if it's single dispatch.
        my $delegate_capture := nqp::dispatch('boot-syscall', 'dispatcher-drop-arg',
            nqp::dispatch('boot-syscall', 'dispatcher-drop-arg', $capture, 1), 1);
        my $method := nqp::captureposarg($delegate_capture, 0);
        if nqp::istype($method, Routine) && $method.is_dispatcher {
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-multi', $delegate_capture);
        }
        else {
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-invoke', $delegate_capture);
        }
    },
    # Resumption
    -> $capture {
        ... 'Will be shown later';
    });

raku-meth-call 中有一个可以论证的欺骗:它实际上并没有插入调用者的类型对象来代替调用者。事实证明,这并不重要。否则,我认为注释(在真正的实现中也可以找到)很好地说明了这个问题。

有一个重要的点可能并不清楚 - 但遵循了一个重复的主题 - 那就是恢复初始化状态的设置也更多的是一种声明式而不是命令式的东西:在调度的时候并没有运行时成本,而是我们在周围保留了足够的信息,以便能够在我们需要的时候重建恢复初始化状态。事实上,当我们处于恢复的运行阶段时,我们甚至不需要在创建捕获对象的意义上重建它)。

现在说说复盘。我将介绍一个严重简化的版本,它只处理 callsame 语义(完整的东西也要处理 lastcall 和 nextcallee 这样的乐趣)。resume 初始化状态的存在是为了给 resumption 过程播种。一旦我们知道我们实际上确实要处理恢复,我们就可以做一些事情,比如计算我们想要走过的继承图中的全部方法列表。每个可恢复的调度器在调用栈上得到一个单一的存储槽,它可以用于它的状态。它可以在恢复的第一步中初始化这个,然后在我们走的时候更新它。或者更准确的说,它可以设置一个调度程序,在运行时就会这样做。

对于我们将要走过的候选链来说,链接列表原来是一个非常方便的数据结构。我们可以通过跟踪当前节点来完成链接列表的工作,也就是说只需要有一个东西发生突变,也就是当前调度的状态。调度程序机制还提供了一种从对象中读取属性的方法,这就足以将遍历链接列表表达到调度程序中。这也意味着零分配。

所以,不多说了,下面是链接列表(在 NQP 这个受限的 Raku 子集中,相当不如在完整的 Raku 中漂亮)。

# A linked list is used to model the state of a dispatch that is deferring
# through a set of methods, multi candidates, or wrappers. The Exhausted class
# is used as a sentinel for the end of the chain. The current state of the
# dispatch points into the linked list at the appropriate point; the chain
# itself is immutable, and shared over (runtime) dispatches.
my class DeferralChain {
    has $!code;
    has $!next;
    method new($code, $next) {
        my $obj := nqp::create(self);
        nqp::bindattr($obj, DeferralChain, '$!code', $code);
        nqp::bindattr($obj, DeferralChain, '$!next', $next);
        $obj
    }
    method code() { $!code }
    method next() { $!next }
};
my class Exhausted {};

最后是恢复处理。

nqp::dispatch('boot-syscall', 'dispatcher-register', 'raku-meth-call-resolved',
    # Initial dispatch
    -> $capture {
        ... 'Presented earlier;
    },
    # Resumption. The resume init capture's first two arguments are the type
    # that we initially did a method dispatch against and the method name
    # respectively.
    -> $capture {
        # Work out the next method to call, if any. This depends on if we have
        # an existing dispatch state (that is, a method deferral is already in
        # progress).
        my $init := nqp::dispatch('boot-syscall', 'dispatcher-get-resume-init-args');
        my $state := nqp::dispatch('boot-syscall', 'dispatcher-get-resume-state');
        my $next_method;
        if nqp::isnull($state) {
            # No state, so just starting the resumption. Guard on the
            # invocant type and name.
            my $track_start_type := nqp::dispatch('boot-syscall', 'dispatcher-track-arg', $init, 0);
            nqp::dispatch('boot-syscall', 'dispatcher-guard-type', $track_start_type);
            my $track_name := nqp::dispatch('boot-syscall', 'dispatcher-track-arg', $init, 1);
            nqp::dispatch('boot-syscall', 'dispatcher-guard-literal', $track_name);
 
            # Also guard on there being no dispatch state.
            my $track_state := nqp::dispatch('boot-syscall', 'dispatcher-track-resume-state');
            nqp::dispatch('boot-syscall', 'dispatcher-guard-literal', $track_state);
 
            # Build up the list of methods to defer through.
            my $start_type := nqp::captureposarg($init, 0);
            my str $name := nqp::captureposarg_s($init, 1);
            my @mro := nqp::can($start_type.HOW, 'mro_unhidden')
                ?? $start_type.HOW.mro_unhidden($start_type)
                !! $start_type.HOW.mro($start_type);
            my @methods;
            for @mro {
                my %mt := nqp::hllize($_.HOW.method_table($_));
                if nqp::existskey(%mt, $name) {
                    @methods.push(%mt{$name});
                }
            }
 
            # If there's nothing to defer to, we'll evaluate to Nil (just don't set
            # the next method, and it happens below).
            if nqp::elems(@methods) >= 2 {
                # We can defer. Populate next method.
                @methods.shift; # Discard the first one, which we initially called
                $next_method := @methods.shift; # The immediate next one
 
                # Build chain of further methods and set it as the state.
                my $chain := Exhausted;
                while @methods {
                    $chain := DeferralChain.new(@methods.pop, $chain);
                }
                nqp::dispatch('boot-syscall', 'dispatcher-set-resume-state-literal', $chain);
            }
        }
        elsif !nqp::istype($state, Exhausted) {
            # Already working through a chain of method deferrals. Obtain
            # the tracking object for the dispatch state, and guard against
            # the next code object to run.
            my $track_state := nqp::dispatch('boot-syscall', 'dispatcher-track-resume-state');
            my $track_method := nqp::dispatch('boot-syscall', 'dispatcher-track-attr',
                $track_state, DeferralChain, '$!code');
            nqp::dispatch('boot-syscall', 'dispatcher-guard-literal', $track_method);
 
            # Update dispatch state to point to next method.
            my $track_next := nqp::dispatch('boot-syscall', 'dispatcher-track-attr',
                $track_state, DeferralChain, '$!next');
            nqp::dispatch('boot-syscall', 'dispatcher-set-resume-state', $track_next);
 
            # Set next method, which we shall defer to.
            $next_method := $state.code;
        }
        else {
            # Dispatch already exhausted; guard on that and fall through to returning
            # Nil.
            my $track_state := nqp::dispatch('boot-syscall', 'dispatcher-track-resume-state');
            nqp::dispatch('boot-syscall', 'dispatcher-guard-literal', $track_state);
        }
 
        # If we found a next method...
        if nqp::isconcrete($next_method) {
            # Call with same (that is, original) arguments. Invoke with those.
            # We drop the first two arguments (which are only there for the
            # resumption), add the code object to invoke, and then leave it
            # to the invoke or multi dispatcher.
            my $just_args := nqp::dispatch('boot-syscall', 'dispatcher-drop-arg',
                nqp::dispatch('boot-syscall', 'dispatcher-drop-arg', $init, 0),
                0);
            my $delegate_capture := nqp::dispatch('boot-syscall',
                'dispatcher-insert-arg-literal-obj', $just_args, 0, $next_method);
            if nqp::istype($next_method, Routine) && $next_method.is_dispatcher {
                nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-multi',
                        $delegate_capture);
            }
            else {
                nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-invoke',
                        $delegate_capture);
            }
        }
        else {
            # No method, so evaluate to Nil (boot-constant disregards all but
            # the first argument).
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'boot-constant',
                nqp::dispatch('boot-syscall', 'dispatcher-insert-arg-literal-obj',
                    $capture, 0, Nil));
        }
    });

这是相当多的内容,也是相当多的代码。但请记住,这只是运行在调度恢复的记录阶段。它还会在 callsame 的 callsite 产生一个调度程序,并带有通常的守卫和结果。隐式守卫是为我们在该点恢复的调度程序创建的。在最常见的情况下,这最终将是单形或双形的,尽管涉及多个调度或方法调度的嵌套的情况可能会产生一个更有形态的 callsite。

我选取的设计迫使 resume 回调处理两种情况:第一次复用和后一次复用。这在几个方面都不理想。

这对那些编写调度简历回调的人来说有点不方便。然而,这又不是特别常见的活动!

这种差异导致两个调度程序堆积在一个调用点,而在其他情况下,这个调用点可能只得到一个 只有其中第二项真正重要。之所以不统一,是为了确保绝大多数从未恢复调度的电话,不会因其最终从未使用的功能而产生每次调度的费用。如果结果是使用该功能的人多花了一点成本,那就这样吧。事实上,早期的基准测试显示,使用新调度器的 callsame 与 wrap 和方法调用似乎比当前 Rakudo 中的速度快了 10 倍,这还没等专门人员对它有足够的了解,就已经进一步改进了!

目前所做的事情 #

我上面讨论的所有内容都已经实现了,只是我可能在某个地方给人的印象是,使用新的 dispatcher 已经完全实现了多重调度,而现在还不是这样(没有处理 where 子句,也不支持调度恢复)。

今后的步骤 #

下一步显然是要完全实现多调度的缺失部分。另一个缺失的语义是对 callwith 和 nextwith 的支持,当我们希望改变移动到下一个候选人时使用的参数。抛开其他一些小问题不谈,理论上来说,这至少可以让所有的 Raku 调度语义得到支持。

目前,所有的标准方法调用($obj.meth())和其他调用(foo()和$foo())都会通过现有的调度机制,而不是新的调度器。这些也需要迁移到新的调度器上,而且任何发现的错误都需要修复。这将使事情达到新调度器在语义上已经准备好的程度。

之后是性能工作:确保专用器能够处理调度程序的防护和结果。最初的目标是,让常见调用形式的稳态性能至少与当前乐道主分支中的性能相同。已经很清楚了,对于一些到目前为止还很冰冷的东西来说,会有一些大的胜利,但它不应该以最常见的调度种类的退步为代价,因为这些调度种类之前已经得到了大量的优化努力。

此外,NQP - 乐道编译器和运行时内脏的其他位写的乐的限制形式 - 也需要迁移到使用新的调度器。只有做到这一点,才有可能从 MoarVM 中扯出当前的方法缓存、多调度缓存等。

一个悬而未决的问题是,如何处理 MoarVM 以外的后端。理想情况下,新的调度机制将被移植到这些地方。相当多的内容应该可以用 JVM 的 invokedynamic 来表达(而这一切可能会在基于 Truffle 的 Raku 实现中发挥得相当好,尽管我不确定目前是否有这方面的积极努力)。

未来的机会 #

虽然我目前的重点是发布一个使用新调度机制的 Rakudo 和 MoarVM 版本,但这不会是旅程的终点。一些眼前的想法。

  • 对角色的方法调用需要把角色打入一个类中, 所以方法查找会返回一个闭包来完成这个任务并替换调用者。这是一个很大的间接性;新的调度者可以获得 pun,并产生一个调度程序,用 punn 化的类类型对象替换角色类型对象,这将使每次调用的成本大大降低。
  • 我期望使用新的 dispatcher 可以使句柄(dlegated)和 fallback(处理缺失的方法调用)机制都能有更好的表现
  • 当前的 assuming - 用于为例程讨价还价或其他首要参数 - 的实现并不理想,利用新调度器的参数重写能力的实现可能会有更好的表现。 在新的调度机制的帮助下,一些新的语言功能也可能以高效的方式提供。例如,目前没有一种可靠的方式来尝试调用一段代码,如果签名绑定了就运行它,如果没有绑定就做其他事情。相反,像 Cro 路由器这样的东西,必须先做签名的试绑定,然后再做调用,这使得路由的成本相当高。还有一个建议已久的想法,就是通过签名与 when 构造提供模式匹配 (例如,when * -> ($x) {}; when * -> ($x, *@tail) { }),这和需求差不多,只是在一个不太动态的环境下。

最后… #

在新的调度机制上的工作比我最初预期的历程要长。设计的恢复部分特别具有挑战性,而且还有一些重要的细节需要处理。一路走来,大概有四种潜在的方法被抛弃了(虽然其中的元素都影响了我在这篇文章中描述的内容)。能坚持下来的抽象真的非常非常难。

我最终也不得不从根本上离开几个月做 Raku 工作,在其他一些工作中感觉有点被压垮了,并且一直在与同样重要的 RakuAST 项目(它将因为能够承担新的调度器的存在而被简化,并且还为我提供了一系列更柔和的 Raku 黑客任务,而调度器的工作提供了很少的轻松选择)。

鉴于这些,我很高兴终于看到了隧道尽头的光亮。剩下的工作是数不胜数的,而我们使用新的调度器发布 Rakudo 和 MoarVM 的那一天,感觉还需要几个月的时间(我希望写下这句话不是在诱惑命运!)。

新的调度器可能是 MoarVM 自我创建以来最重要的变化,因为它看到我们删除了一堆从一开始就存在的东西。RakuAST 也将为 Rakudo 编译器带来十年来最大的架构变化。两者都是一个机会,将多年来学习的东西硬生生地折合到运行时和编译器中。我希望再过十年,当我回顾这一切的时候,至少会觉得自己这次犯了更多有趣的错误。

原文链接: https://6guts.wordpress.com/2021/03/15/towards-a-new-general-dispatch-mechanism-in-moarvm/