Perl6 vs Perl5使用素数进行基准测试

Question

这是一个讨论从这个HN线程移到这里,关于Perl6与Perl5与其他语言的基准测试,使用一种算法来实现Sundaram的Sieve用于查找素数.

这是原始主题中的原始代码:

perl5 0m0.156s

perl6 0m6.615s

问题是与Perl5实现相比,Perl6版本需要很长时间才能找到素数.部分原因是使用float作为输入,但仍然太慢了.

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

Answer 1

事实证明,即使素数是整数,在你的Perl 6版本中,每个计算都是通过使用浮点来完成的.这是由对子程序的调用引起的.如果你愿意:

sieve_sundaram(1000)

代替:

sieve_sundaram(1e3)

那么它突然变得快4倍.在Perl 5中,你永远不知道你在处理价值方面的问题.在Perl 6中,如果你告诉它使用一个浮点,那么它将在之后感染所有计算.1e3是一个浮点值.1000是Perl 6中的整数.

此外,您似乎有一个次优算法:第二个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上.

Answer 2

我不认为我可以为Liz所说的更多.以外:

"但为了对多种语言进行基准测试,我需要在任何地方运行相同的东西"

...其中"相同"被定义为英语中相似的语法,对于完全不同的编程语言之间的等价是一个非常差的标准.Perl 6与Perl 5具有非常相似甚至相同的语法,同时在下面执行非常不同的语义.整个语言已被调整为正确性,默认容易达到语法,而不是最佳行为.另一个很好的例子是Perl 6字符串,它们非常慢,它们总是完全规范化的unicode而不是一串普通的字节.对它们的所有操作都考虑了字形的unicode概念,而不是字节和字节偏移.哪个好极了!但是,对于C/Perl 5字符串来说,更等效的类型可能是一个Buf遗憾的是没有任何接近尽可能多的类似字符串的运算符/方法,但只是一个字节块.