Raku与Perl的质数基准测试

Question

Raku与Perl的质数基准测试

benchmarkingprimesrakuperl

8

这是从HN thread移动过来的讨论，涉及使用实现Sieve of Sundaram算法查找质数的Perl6与Perl5以及其他语言的基准测试。

以下是原始线程中的原始代码：

perl5 0m0.156s

perl6 0m6.615s

问题在于，与Perl5实现相比，Perl6版本花费的时间太长了。部分原因是使用浮点数作为输入，但仍然太慢了。

目标不一定是优化算法，而是确定为什么Perl6与其他语言相比如此缓慢。

- petre

请参见2017年SO如何在Raku中高效地生成素数列表？。摘自问题作者自己的答案总结的两句关键引用：“只要你稍微优化一下，使用 Raku 代码实现的筛子并不会像我担心的那么慢”，“我还添加了 Curt Tilmes 的Primesieve模块，哇，它真的很快！” - raiph

2个回答

6

我认为我无法再补充Liz所说的内容了。除此之外：

"但是为了在多种语言之间进行基准测试，我需要在所有地方运行相同的东西"

......其中，“相同”被定义为英语中类似的语法，这是评估根本不同的编程语言等价性非常糟糕的标准。Perl 6 的语法与 Perl 5 非常相似甚至相同，但在底层执行的语义却有很大不同。整个语言都经过调整以实现正确性，默认情况下容易达到语法，而不是最优行为。另一个很好的例子就是 Perl 6 字符串，它们相当慢，它们始终是完全规范化的 Unicode 而不是一系列纯字节的字符串。对它们的所有操作都考虑到了 Unicode 概念中的图形和字节偏移量。这很好！但是与 C/Perl 5 字符串最相似的类型可能是 Buf，但可惜的是没有像字符串一样的操作符/方法，只是一块字节。

- Matt Oates

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Elizabeth Mattijsen · Accepted Answer

结果发现即使质数是整数，在您的Perl 6版本中，每个计算都是通过浮点数进行的。这是由于调用子例程引起的。如果您这样做：

sieve_sundaram(1000)

改成：

sieve_sundaram(1e3)

突然间速度快了四倍。在 Perl 5 中，关于值你从不知道你正在处理什么。在 Perl 6 中，如果你告诉它使用浮点数，那么所有的计算都将被感染为浮点数。 1e3 是一个浮点数值。在 Perl 6 中，1000 是一个整数。

另外，您似乎有一个次优算法：第二个 foreach 不需要从 1..$n 开始，而是可以从 $i..$n 开始。这将使 Perl 5 版本代码的运行时间降至89毫秒。

由于您的程序在 Perl 5 版本中没有使用 BigInt，因此基本上是使用本机整数。在 Perl 6 中，除非将它们标记为本机的，否则所有的整数计算都是 BigInts。如果我为您的 Perl 6 版本进行调整，将其标记为本机的，那么该版本的运行时间将从 4671 毫秒降至 414 毫秒。

sub sieve_sundaram(int $n) {
    my %a;
    my int @s = 2;
    my int $m = $n div 2 - 1;
    for 1..$n -> int $i {
        for $i..$n -> int $j {
            my int $p = $i + $j + 2 * $i * $j;
            if $p < $m {
                %a{$p} = True;
            }
        }
    }
    for 1..$m -> int $k {
        if ! %a{$k} {
            my int $q = 2 * $k + 1;
            @s.push($q);
        }
    }

    return @s;
}

sieve_sundaram(1000);

因此，比以前快了大约11倍。速度比Perl 5版本慢近5倍。

在Perl 6中，获取质数的最典型版本是：

(1..1000).grep( *.is-prime )

对于我来说，这个方法的执行时间与你原本的 Perl 5 算法相当。对于多CPU机器上的较大值，我会使用以下代码：

(1..2500).hyper.grep( *.is-prime )

大约在2500时，使用hyper可以更快地完成工作，这样工作就会自动分配到多个CPU上。