prestazioni Scala l'algoritmo di numeri primi

Question

Sono abbastanza nuovo su Scala e quindi al fine di iniziare a scrivere un po 'di codice che ho implementato questo semplice programma:

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

} 

genera n primi a partire da 2. Poi ho implementato lo stesso algoritmo in C++ 11 utilizzando la libreria gamma-v3 di Eric Nibler.This è il codice:

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

Come si può vedere il codice è molto simile, ma le prestazioni sono molto diverse:

Per n = 5000, il C++ termina in 0,265s Scala invece completa in 24,314s !!! Quindi, da questo test, Scala sembra 100 volte più lento del C++ 11.

Qual è il problema sul codice Scala? Potresti darmi qualche suggerimento per un migliore utilizzo di scalac?

Nota: ho compilato il codice C++ utilizzando gcc 4.9.2 e -O3 opt.

Grazie

Answer 1

Il problema principale risiede velocità con il vostro is_prime implementazione.

Prima di tutto, si filtra un flusso per trovare tutti i divisori, quindi controllare se non ce ne sono (l.size == 0). Ma è più veloce di tornare false non appena il primo divisore si trova:

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

Questa diminuito runtime da secondo a secondi per primes(5000) sulla mia macchina.

Il secondo problema è Stream stesso. Gli Stream Scala sono lenti e usarli per semplici calcoli numerici è un enorme overkill. Sostituzione Stream con Range diminuito runtime seguito 1,2 secondo:

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

Questo è decente 5x più lento di C++. Di solito, mi fermerei qui, ma è possibile ridurre un po 'di più il tempo di esecuzione se togliamo la funzione di ordine superiore find.

Anche se bello e funzionale, lo find genera anche un sovraccarico. implementazione del ciclo (sostanzialmente sostituendo find con foreach) diminuisce ulteriormente runtime 0,45 secondo, che è meno di 2 volte più lento di C++ (che è già dell'ordine di JVM dall'alto):

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

C'è un'altra Flusso in gen_primes, quindi fare qualcosa con esso può migliorare di più il tempo di esecuzione, ma a mio parere non è necessario. A quel punto del miglioramento delle prestazioni, penso che sarebbe meglio passare ad un altro algoritmo di generazione di numeri primi: ad esempio, usando solo numeri primi, invece di tutti i numeri dispari, per cercare i divisori, o usando il Sieve di Eratostene.

Tutto sommato, le astrazioni funzionali in Scala sono implementate con oggetti reali nell'heap, che hanno un sovraccarico, e il compilatore JIT non può risolvere tutto.Ma il punto di forza del C++ è rappresentato dalle astrazioni a costo zero: tutto ciò che è possibile viene ampliato durante la compilazione tramite template s, constexpr e ulteriormente ottimizzato dal compilatore.