质量算法上的Scala性能

Question

我对Scala很新,所以为了开始编写一些代码,我已经实现了这个简单的程序:

package org.primes.sim

object Primes {

  def is_prime(a: Int): Boolean = {
    val l = Stream.range(3, a, 2) filter { e => a % e == 0}
    l.size == 0
  }

  def gen_primes(m: Int) = 
    2 #:: Stream.from(3, 2) filter { e => is_prime(e) } take m

  def primes(m : Int) = {
      gen_primes(m) foreach println      
  }

  def main(args: Array[String]) {
    if (args.size == 0)
      primes(10)
    else
      primes(args(0).toInt)
  }

}

它从2开始生成n个素数.然后我使用Eric Nibler的range-v3库在C++ 11中实现了相同的算法.这是代码:

#include <iostream>
#include <vector>
#include <string>
#include <range/v3/all.hpp>

using namespace std;
using namespace ranges;

inline bool is_even(unsigned int n) { return n % 2 == 0; }

inline bool is_prime(unsigned int n)
{
    if (n == 2)
        return true;
    else if (n == 1 || is_even(n))
        return false;
    else
        return ranges::any_of(
                view::iota(3, n) | view::remove_if(is_even),
                [n](unsigned int e) { return n % e == 0; }
            ) == false;
}

void primes(unsigned int n)
{
    auto rng = view::ints(2) | view::filter(is_prime);
    ranges::for_each(view::take(rng, n), [](unsigned int e){ cout << e << '\n'; });
}

int main(int argc, char* argv[])
{
    if (argc == 1)
        primes(100);
    else if (argc > 1)
    {
        primes(std::stoi(argv[1]));
    }
}

正如您所看到的,代码看起来非常相似,但性能却截然不同:

对于n = 5000,C++在0,265s完成,而Scala在24,314s完成!因此,从这个测试来看,Scala似乎比C++ 11慢100倍.

Scala代码有哪些问题？你能给我一些提示,以便更好地使用scalac吗？

注意:我使用gcc 4.9.2和-O3 opt编译了C++代码.

谢谢

Answer 1

主要的速度问题在于您的is_prime实施.

首先,您过滤一个Stream来查找所有除数,然后检查是否有无(l.size == 0).但是false一旦找到第一个除数,它就会更快返回:

def is_prime(a: Int): Boolean =
  Stream.range(3, a, 2).find(a % _ == 0).isEmpty

这使我的机器上的运行时间从22秒减少到5秒primes(5000).

第二个问题Stream本身.Scala Streams很慢,使用它们进行简单的数字计算是一个巨大的过度杀伤力.更换Stream与Range运行时减少进一步对于1,2秒:

def is_prime(a: Int): Boolean =
  3.until(a, 2).find(a % _ == 0).isEmpty

这很不错:比C++慢5倍.通常,我会停在这里,但如果我们删除高阶函数,可以减少更多的运行时间find.

虽然美观和功能,但find也会产生一些开销.循环实现(基本上替换find为foreach)进一步将运行时间减少到0.45秒,这比C++慢了不到2倍(已经是JVM开销的顺序):

def is_prime(a: Int): Boolean = {
  for (e <- 3.until(a, 2)) if (a % e == 0) return false
  true
}

还有另一个Stream gen_primes,所以用它做一些事情可能会更多地改善运行时间,但在我看来,没有必要.在性能改进的那一点上,我认为最好切换到其他一些生成素数的算法:例如,仅使用素数而不是所有奇数,来寻找除数,或者使用Eratosthenes的Sieve.

总而言之,Scala中的函数抽象是使用堆上的实际对象实现的,这些对象有一些开销,而JIT编译器无法修复所有内容.但C++的卖点是零成本抽象:在编译过程中template,所有可能的东西都会被扩展,constexpr并由编译器进一步优化.