rakulang

Raku

Raku Multiple Dispatch With the New MoarVM Dispatcher

Thu Apr 15, 2021

Raku Multiple Dispatch With the New Moarvm Dispatcher

我最近写了一篇关于新的 MoarVM 调度机制的文章，并在那篇文章中指出，我在 Raku 的多重分派语义方面还有不少需要实现的地方。从那以后，我在这个方向上取得了不小的进展。这篇文章包含了对所采取的方法的概述，以及一些非常粗略的性能测量。

我的天啊，语义太多了 #

在 Raku 的所有分派中，多重分派是最复杂的。多重分派允许我们写一组候选者，然后根据参数的数量进行选择。

multi ok($condition, $desc) {
    say ($condition ?? 'ok' !! 'not ok') ~ " - $desc";
}
multi ok($condition) {
    ok($condition, '');
}

或根据参数的类型:

multi to-json(Int $i) { ~$i }
multi to-json(Bool $b) { $b ?? 'true' !! 'false' }

而且不只是一个参数，而是可能有很多参数:

multi truncate(Str $str, Int $chars) {
    $str.chars < $chars ?? $str !! $str.substr(0, $chars) ~ '...'
}

multi truncate(Str $str, Str $after) {
    with $str.index($after) -> $pos {
        $str.substr(0, $pos) ~ '...'
    }
    else {
        $str
    }
}

我们可以添加 where 子句来区分普通类型无法捕捉的属性上的候选者。

multi fac($n where $n <= 1) { 1 }
multi fac($n) { $n * fac($n - 1) }

每当我们写出一组这样的 multi 候选列表时，编译器就会自动生成一个 proto 例程。这就是安装在符号表中的，存放候选列表的东西。然而，我们也可以写自己的 proto，并使用特殊的术语 {*} 来决定在哪一点上进行调度，如果有的话。

proto mean($collection) {
    $collection.elems == 0 ?? Nil !! {*}
}

multi mean(@arr) {
    @arr.sum / @arr.elems
}

multi mean(%hash) {
    %hash.values.sum / %hash.elems
}

候选者按窄度排序（使用拓扑排序）。如果多个候选者匹配，但它们窄度相同，那么这就是一个歧义错误。否则，我们调用最窄的一个。然后，我们选择的候选者可能会使用 callsame 和它的朋友们来推迟到下一个最窄的候选者，后者可能也会这样做，直到我们达到最一般的匹配的候选者。

多重分派无处不在 #

Raku 在很大程度上依赖于多重分派。Raku 中的大多数操作符都被编译成对多重分派子程序的调用。即使是 $a+$b 也会是一个多重分派。这意味着高效地进行多重分派对性能真的很重要。考虑到其语义的丰富性，这有可能有点令人担忧。不过，也有好消息。

大多数多重调度都很无聊 #

我们遇到的绝大多数情况是:

一个仅由参数和名义类型的数量所做的决定。
无 where 子句
无自定义 proto
无 callsame

这并不是说其他情况不重要，它们确实相当有用，而且它们的表现也是可取的。不过，在普通情况下，我们能省则省，也是可取的。例如，我们不希望急于计算每一个单次多重调度的全部可能的候选者，因为大多数时候只有第一个才是重要的。这不仅仅是时间上的问题：回想一下，新的调度机制会在每个调用点存储调度程序，如果我们在每个调用点存储所有匹配的候选程序列表，我们也会浪费很多内存。

我们今天怎么做？ #

如今 Rakuo 的情况如下:

如果调度只由元数和名义类型决定，并且你不使用扁平化的参数来调用它，它可能会表现得很好，甚至可能会享受到候选者的内联和消除在慢速路径上发生的重复类型检查。这要归功于 proto 持有一个 “dispatch cache”，这是一个在 VM 中实现的特例机制，它使用搜索树，每个参数有一个级别。
如果是这种情况，但它有一个自定义的 proto，也不会太差，虽然不会发生内联，它仍然可以使用搜索树。
如果它使用 where 子句，速度会很慢，因为搜索树只处理在每一个名义类型集合中找到一个候选者，所以我们不能使用它。
同样的道理也适用于 callsame，它的速度也会很慢。

实际上，今天的情况是，如果在热路径附近的任何地方，你根本不会在多重调度中使用 where子句（好吧，如果你知道热路径在哪里，并且知道这种调度很慢）。同理，callsame 也是如此，虽然那不太常触达。问题是，我们能不能用新的调度器做得更好？

守卫类型 #

我们先看看最简单的情况是如何处理的，然后再从那里开始建立。(这其实是我在实现上的做法，但同时我也有一个大概的想法，我希望最终的结果是什么)。

回忆一下这对候选者。

multi truncate(Str $str, Int $chars) {
    $str.chars < $chars ?? $str !! $str.substr(0, $chars) ~ '...'
}

multi truncate(Str $str, Str $after) {
    with $str.index($after) -> $pos {
        $str.substr(0, $pos) ~ '...'
    }
    else {
        $str
    }
}

然后我们有一个调用 truncate($message, "\n")，其中 $message 是 Str 类型的。在新的调度机制下，调用是使用 raku-call dispatcher 进行的，它识别出这是一个 multi 方法调度，因此委托给 raku-multi。(multi 方法调度也会在那里结束)。

调度的记录阶段 - 在我们第一次到达这个调用点时 - 将进行如下操作。

迭代候选者
如果某个候选者在参数数上不匹配，就直接丢弃它。由于 callsite 的形状是一个常数，而且我们在每个 callsite 都会计算 dispatch 程序，所以我们不需要为此建立任何防护措施。
如果在类型匹配并且成功了，注意涉及哪些参数，需要什么样的守卫。
如果没有匹配或者模棱两可，就报错，不产生调度程序。
否则，在确定了类型守卫后，将选定的候选程序委托给 raku-invoke 调度程序。

当我们再次到达同一个调用点时，我们可以运行调度程序，它可以快速检查参数类型是否与上次看到的参数类型相匹配，如果相匹配，我们就知道要调用哪个候选程序。这些检查非常便宜 - 比遍历所有候选者并检查每个候选者是否匹配要便宜得多。优化器以后可能会证明这些检查总是会成为事实，并消除它们。

因此，整个调度过程 - 至少对于这个我们只有类型和元数的简单案例 - 可以向虚拟机 “解释” 为 “如果参数具有这些确切的类型，就调用这个例程”。这和我们对方法分派所做的差不多，除了我们只关心第一个参数的类型 - 调用者 - 和方法名的值。(还记得上一篇文章中说过，如果是 multi 方法调度，那么方法调度和 multi 方法调度都会守护第一个参数的类型，但是消除了重复，所以只做一次检查)。

这就进入了恢复之洞 #

想出好的抽象是很难的，新的调度机制的很多挑战就在于此。Raku 有不少不同的类似调度的东西。然而，将它们全部直接编码在虚拟机中会导致很高的复杂度，这使得构建可靠的优化（甚至是可靠的未优化的实现！）具有挑战性。因此，我们的目标是研究出一套相对较小的原语，允许以这样一种方式向虚拟机 “解释” 调度，使其能够提供不错的性能。

很明显，callsame 是一种调度恢复，但自定义 proto 这种情况和 where 子句这种情况呢？事实证明，这些也都可以用调度恢复的方式整齐地表达出来（where 子句情况需要在虚拟机层面增加一个小的内容，到时候可能对其他事情也有用）。不仅如此，用调度恢复来编码这些特性也是相当直接的，因此应该是高效的。我们教给专门人员的关于如何更好地使用调度恢复的每一个技巧，都可以让所有使用它们实现的语言特性也受益。

自定义 proto #

回顾这个例子。

proto mean($collection) {
    $collection.elems == 0 ?? Nil !! {*}
}

在这里，我们希望运行 proto 的主体，然后在 {*} 这里进行候选者的选择。相比之下，当我们没有自定义的 proto 时，我们希望简单地继续调用正确的多。

为了达到这个目的，我首先将 multi 候选者的选择逻辑从 raku-multi 调度器移到了 raku-multi-core 调度器中。然后，raku-multi dispatcher 会检查我们是否有一个 “onlystar” proto（一个不需要我们运行的 proto）。如果有，它就会立即委托给 raku-multi-core。如果没有，它就将调度的参数保存为恢复初始化状态，然后调用 proto。proto 的 {*} 被编译成一个 dispatch resumption。然后，这个 resumption 委托给 raku-multi-core。或者，在代码中。

nqp::dispatch('boot-syscall', 'dispatcher-register', 'raku-multi',
    # Initial dispatch, only setting up resumption if we need to invoke the
    # proto.
    -> $capture {
        my $callee := nqp::captureposarg($capture, 0);
        my int $onlystar := nqp::getattr_i($callee, Routine, '$!onlystar');
        if $onlystar {
            # Don't need to invoke the proto itself, so just get on with the
            # candidate dispatch.
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-multi-core', $capture);
        }
        else {
            # Set resume init args and run the proto.
            nqp::dispatch('boot-syscall', 'dispatcher-set-resume-init-args', $capture);
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-invoke', $capture);
        }
    },
    # Resumption means that we have reached the {*} in the proto and so now
    # should go ahead and do the dispatch. Make sure we only do this if we
    # are signalled to that it's a resume for an onlystar (resumption kind 5).
    -> $capture {
        my $track_kind := nqp::dispatch('boot-syscall', 'dispatcher-track-arg', $capture, 0);
        nqp::dispatch('boot-syscall', 'dispatcher-guard-literal', $track_kind);
        my int $kind := nqp::captureposarg_i($capture, 0);
        if $kind == 5 {
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-multi-core',
                nqp::dispatch('boot-syscall', 'dispatcher-get-resume-init-args'));
        }
        elsif !nqp::dispatch('boot-syscall', 'dispatcher-next-resumption') {
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'boot-constant',
                nqp::dispatch('boot-syscall', 'dispatcher-insert-arg-literal-obj',
                    $capture, 0, Nil));
        }
    });

合二为一 #

推迟到下一个候选者（例如用 callsame）和因为 where 子句失败而尝试下一个候选者看起来非常相似：两者都涉及遍历一个可能的候选者列表。有一些细节，但它们有很多共同点，如果能在使用新的 dispatcher 实现多重分派的过程中体现出来就更好了。

在这之前，先说一个略显可怕的细节，当我们有 where 子句的时候，今天在 Rakuo 中是如何工作的。首先，调度器会做一个 “试用绑定”，它问一个问题：这个签名会不会绑定？要做到这一点，它必须评估所有的 where 子句。更糟糕的是，它还必须使用慢路径签名绑定器，它对签名进行解释，尽管我们在很多情况下可以编译它。如果候选者匹配，很好，我们选择它，然后调用它……这将第二次运行 where 子句，作为编译后的签名绑定代码的一部分。这样做一点也不高效，除了在开发人员的时间上要高效得多，这也是为什么要这样做的原因。

总之，毋庸置疑，在我使用新的调度器重新实现时，我相当希望尽可能避免这种重复的工作和慢路径绑定。而且，令人高兴的是，一个小小的补充提供了一个解决方案。有一个 op assertparamcheck，任何类型的参数检查都会被编译成（无论是类型检查、where 子句检查等），这将触发对一个函数的调用，该函数获取参数，也就是我们试图调用的东西，然后可以通过它们来产生错误信息。诀窍是提供一种调用例程的方法，使绑定失败后，不是调用报错函数，而是离开例程，然后做一个调度恢复! 这意味着我们可以将传递 where 子句检查失败变成一个调度恢复，然后会走到下一个候选者，并代替它进行尝试。

琐碎VS非琐碎 #

这让我们得到了大部分的解决方法，但在常见的情况下，仍然存在内存和时间效率的问题，即没有恢复和没有 where 子句。我为这种情况创造了一个术语 “trivial multiple dispatch”，这使得其他情况变得 “non-trivial”。事实上，我甚至做了一个调度器，叫做 raku-multi-non-trivial! 我们有两种方式可以结束。

最初尝试寻找匹配的候选者，决定了我们必须考虑 where 子句。一旦我们看到是这种情况，我们就会继续制作一个可能匹配的候选者的完整列表。这是一个链表（原因见我之前的文章）。
最初尝试寻找匹配的候选者时，发现了一个可以纯粹根据参数数和名词类型来挑选的候选者。我们就此停止，而不是试图建立一个完整的候选列表，并运行匹配的候选。在 callsame 的情况下，我们最终进入琐碎的调度恢复处理程序，它 - 因为这种情况现在是非琐碎的 - 建立完整的候选者列表，从它上面剪下第一项（因为我们已经运行了那项），然后委托给 raku-multi-non-trivial。

在这个描述中失去了另一个重要的改进：今天，当有 where 子句时，我们完全失去了使用 MoarVM 多重调度缓存的能力，但在新的调度器下，我们在 callsite 存储了一个类型过滤的候选列表，然后使用廉价的类型守卫来检查它是否有效使用。

初步结果 #

我做了一些基准测试，看看新的调度机制在今天 Raku 已知的几种次优情况下的表现。这些数字并不能反映出什么是可能的，因为目前专门人员对新的调度器还没有太多的了解。相反，它们反映了我们可以期望的最小改进。

考虑这个基准，使用一个带有 where 子句的 multi 来递归实现 factorial。

multi fac($n where $n <= 1) { 1 }
multi fac($n) { $n * fac($n - 1) }

for ^100_000 {
    fac(10)
}
say now - INIT now;

这需要进行一些调整（并在环境变量下运行）以使用新的调度器；这些都是暂时的，直到我将 Rakudo 转换为默认使用新的调度器。

use nqp;

multi fac($n where $n <= 1) { 1 }
multi fac($n) { $n * nqp::dispatch('raku-call', &fac, $n - 1) }

for ^100_000 {
    nqp::dispatch('raku-call', &fac, 10);
}
say now - INIT now;

在我的机器上，第一个运行时间为4.86秒，第二个运行时间为1.34秒。因此，在新的调度器下，运行时间只需过去的四分之一多一点 - 这已经是一个相当大的改进了。

一个涉及 callsame 的案例也很有意思。这里是没有使用新调度器的情况。

multi fallback(Any $x) { "a$x" }
multi fallback(Numeric $x) { "n" ~ callsame }
multi fallback(Real $x) { "r" ~ callsame }
multi fallback(Int $x) { "i" ~ callsame }

for ^1_000_000 {
    fallback(4+2i);
    fallback(4.2);
    fallback(42);
}   
say now - INIT now;

而配合临时调整使用新的调度器:

use nqp;

multi fallback(Any $x) { "a$x" }
multi fallback(Numeric $x) { "n" ~ new-disp-callsame }
multi fallback(Real $x) { "r" ~ new-disp-callsame }
multi fallback(Int $x) { "i" ~ new-disp-callsame }

for ^1_000_000 {
    nqp::dispatch('raku-call', &fallback, 4+2i);
    nqp::dispatch('raku-call', &fallback, 4.2);
    nqp::dispatch('raku-call', &fallback, 42);
}
say now - INIT now;

在我的机器上，第一个运行时间为31.3s，第二个运行时间为11.5s，这意味着使用新的调度器，我们最终需要的时间只有当前 Rakudo 的三分之一多一点。

这些都是相当鼓舞人心的，但正如前面提到的，大部分的多重调度都是琐碎的那种，没有使用这些功能。如果我在让其他事情变得更好的路上把最常见的情况变得更糟，那就不好了。现在还不能对此进行公平的比较：琐碎的多重分派在特化器中已经受到了很多关注，而且它还不能很好地优化使用新调度器的代码。值得注意的是，在这样的例子中。

multi m(Int) { }
multi m(Str) { }

for ^1_000_000 {
    m(1);
    m("x");
}
say now - INIT now;

内嵌和其他优化会将其变成一个空循环，这是很难做到的。不过有一件事我们已经可以做了：在禁用 specializer 的情况下运行它。新的调度器版本看起来是这样的。

use nqp;

multi m(Int) { }
multi m(Str) { }

for ^1_000_000 {
    nqp::dispatch('raku-call', &m, 1);
    nqp::dispatch('raku-call', &m, "x");
}
say now - INIT now;

结果分别是0.463s和0.332s。因此，基线执行时间 - 在特化器发挥其魔力之前 - 使用新的通用调度机制比使用我们目前使用的特化多重调度缓存要少。在做测量之前，我不知道这里会有什么预期。鉴于我们要从一个已经被剖析和调整过的特化机制转到一个没有受到如此关注的新的通用机制，我已经做好了最初做得差一点的准备，如果能做到平价就好了。在70%的时间里，跑进了70%的时间，这比我预期的进步更大。

我期望，一旦特化器更好地理解新的调度机制，它也能把上面的内容变成一个空循环 - 不过，由于每次优化可以进行更多的迭代，这应该还是表现为新调度器的胜利。

最后的想法 #

只要增加一个相对较小的功能，新的调度机制已经可以处理大部分的 Raku 多重调度语义。此外，即使在 specializer 和 JIT 没有真正能够做好的情况下，一些微基准已经显示出3倍-4倍的提升。这是一个很好的起点。

在我们使用新的调度器出货 Rakudo 版本之前，还有很多工作要做。然而，多重调度是设计中剩下的最大威胁：它比其他种类的调度相当多的参与，而且很有可能一个意想不到的缺点会引发新一轮的设计工作，或者揭示出一般机制与基线未优化的情况下, 与更专业的机制相比，性能会很吃力。到目前为止，没有任何迹象表明这两种情况，我谨慎乐观地认为整体设计是差不多的。