dimanche 3 mai 2015

Scala performance on primes algorithm

I'm quite new on Scala and so in order to start writing some code I've implemented this simple program:

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)
  }

}

It generates n primes starting from 2. Then I've implemented the same algorithm in C++11 using range-v3 library of Eric Nibler.This is the code:

#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]));
    }
}

As you can see the code looks very similar but the performance are very different:

For n = 5000, C++ completes in 0,265s instead Scala completes in 24,314s!!! So, from this test, Scala seems 100x slower than C++11.

Which is the problem on Scala code? Could you give me some hints for a better usage of scalac?

Note: I've compiled the C++ code using gcc 4.9.2 and -O3 opt.

Thanks

Aucun commentaire:

Enregistrer un commentaire