benchmarking - 使用素数的Perl6 vs Perl5基准测试

Question

这是从此处的HN thread进行的讨论，内容是关于使用实现Sieve of Sundaram来查找素数的算法对Perl6与Perl5与其他语言进行基准测试。

这是原始线程中的原始代码:

perl5 0分0.156秒

perl6 0分6.615秒

问题在于，与Perl5实现相比，Perl6版本花费太多时间才能找到质数。部分原因是由于使用float作为输入，但是仍然太慢。

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

Answer 1

事实证明，即使素数是整数，在Perl 6版本中，每一次计算都是使用浮点数完成的。这是由子程序的调用引起的。如果您愿意:

sieve_sundaram(1000)

代替:

sieve_sundaram(1e3)

然后突然变成了原来的4倍。在Perl 5中，您永远不知道要处理的值(value)观。在Perl 6中，如果您告诉它使用浮点数，则它将感染所有随后在浮点数内的计算。 1e3是一个浮点值。 1000是Perl 6中的整数。

另外，您似乎有一个次优算法:第二个 foreach不需要来自 1..$n，而可以来自 $i..$n。这对我来说将代码的Perl 5版本的运行时间降低到89毫秒。

由于您的程序未在Perl 5版本中使用BigInt，因此它基本上是在使用 native 整数。在Perl 6中，所有整数计算始终都是BigInts，除非您将其标记为 native 。如果我为此调整了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上。