python - 为什么这个记忆化的 Euler14 实现在 Raku 中比 Python 慢得多？

Question

我最近在玩problem 14的Euler project : 1..1_000_000 范围内的哪个数字产生最长的Collatz sequence ?
我知道必须 memoize 的问题获得合理的时间，以及以下 Python代码使用该技术相对快速地返回答案(内存到字典):

#!/usr/bin/env python

L = 1_000_000
cllens={1:1}

cltz = lambda n: 3*n + 1 if n%2 else n//2

def cllen(n):
    if n not in cllens: cllens[n] = cllen(cltz(n)) + 1
    return cllens[n]

maxn=1
for i in range(1,L+1):
    ln=cllen(i)
    if (ln > cllens[maxn]): maxn=i

print(maxn)

(改编自 here ；我更喜欢这个不使用 max 的版本，因为我可能想摆弄它以返回最长的 10 个序列等)。
我试着把它翻译成 Raku尽可能在语义上接近:

#!/usr/bin/env perl6
use v6;

my $L=1_000_000;
my %cllens = (1 => 1);

sub cltz($n) { ($n %% 2) ?? ($n div 2) !! (3*$n+1) }

sub cllen($n) {
    (! %cllens{$n}) && (%cllens{$n} = 1+cllen($n.&cltz));
    %cllens{$n};
}

my $maxn=1;
for (1..$L) {
    my $ln = cllen($_);
    ($ln > %cllens{$maxn}) && ($maxn = $_)
}
say $maxn

以下是我一直在运行这些的时间:

$ time <python script>
837799

real    0m1.244s
user    0m1.179s
sys     0m0.064s

另一方面，在 Raku :

$ time <raku script>
837799

real    0m21.828s
user    0m21.677s
sys     0m0.228s

问题
我是在两者之间翻译错误，还是差异是启动 VM 等不可调和的问题？
有没有我可以应用到 Raku 的巧妙调整/习语？代码可以大大加快速度吗？
旁白
当然，这与这个特定的 Euler project 无关。问题;我对是否有适合 Raku 的魔法加速奥秘更感兴趣。我不知道。

Answer 1

我认为大部分额外时间是因为 Raku 具有类型检查，并且它们没有被运行时类型专门化程序删除。或者，如果它们被删除，则需要很长时间。
通常优化 Raku 代码的方法是首先使用分析器运行它:

$ raku --profile test.raku

当然，这段代码的 Segfault 会失败，所以我们不能使用它。
我的猜测是大部分时间都与使用哈希有关。
如果已实现，则使用 native 整数作为键和值可能会有所帮助:

 my int %cllens{int} = (1 => 1);

然后将函数声明为使用 native 大小的整数可能是一个更大的胜利。
(目前这充其量只是一个小的改进。)

sub cltz ( int $n --> int ) {…}
sub cllen( int $n --> int ) {…}
for (1..$L) -> int $_ {…}

当然，就像我说的本地哈希没有实现，所以这纯粹是猜测。

您可以尝试使用 Raku 的多进程功能，但共享 %cllens 可能存在问题多变的。

问题也可能是因为递归。 (结合上述类型检查。)
如果你重写 cllen以便它使用循环而不是可能有帮助的递归。

注:
最接近 n not in cllens大概是 %cllens{$n}:!exists .
尽管这可能比仅检查值不为零要慢。
还有 cellen有点可怕。我会写得更像这样:

sub cllen($n) {
    %cllens{$n} //= cllen(cltz($n)) + 1
}