Come ottimizzare la for-comprehensions e i loop in Scala?

Quindi Scala dovrebbe essere veloce quanto Java. Sto rivisitando alcuni problemi di Project Euler in Scala che inizialmente avevo affrontato in Java. In particolare Problema 5: “Qual è il più piccolo numero positivo che è equamente divisibile per tutti i numeri da 1 a 20?”

Ecco la mia soluzione Java, che richiede 0,7 secondi per essere completata sulla mia macchina:

public class P005_evenly_divisible implements Runnable{ final int t = 20; public void run() { int i = 10; while(!isEvenlyDivisible(i, t)){ i += 2; } System.out.println(i); } boolean isEvenlyDivisible(int a, int b){ for (int i = 2; i <= b; i++) { if (a % i != 0) return false; } return true; } public static void main(String[] args) { new P005_evenly_divisible().run(); } } 

Ecco la mia “traduzione diretta” in Scala, che richiede 103 secondi (147 volte di più!)

 object P005_JavaStyle { val t:Int = 20; def run { var i = 10 while(!isEvenlyDivisible(i,t)) i += 2 println(i) } def isEvenlyDivisible(a:Int, b:Int):Boolean = { for (i <- 2 to b) if (a % i != 0) return false return true } def main(args : Array[String]) { run } } 

Finalmente ecco il mio tentativo di programmazione funzionale, che richiede 39 secondi (55 volte di più)

 object P005 extends App{ def isDivis(x:Int) = (1 to 20) forall {x % _ == 0} def find(n:Int):Int = if (isDivis(n)) n else find (n+2) println (find (2)) } 

Utilizzando Scala 2.9.0.1 su Windows 7 64-bit. Come posso migliorare le prestazioni? Sto facendo qualcosa di sbagliato? O è Java molto più veloce?

Il problema in questo caso particolare è che tu ritorni dall’interno della for-expression. Questo a sua volta viene tradotto in una proiezione di NonLocalReturnException, che viene catturata nel metodo di inclusione. L’ottimizzatore può eliminare il foreach ma non può ancora eliminare il tiro / presa. E il lancio / presa è costoso. Ma poiché tali ritorni annidati sono rari nei programmi Scala, l’ottimizzatore non ha ancora affrontato questo caso. C’è un lavoro in corso per migliorare l’ottimizzatore che spero risolverà presto questo problema.

Il problema è più probabile che l’utilizzo di un metodo di comprensione nel metodo sia isEvenlyDivisible . La sostituzione di un ciclo while equivalente dovrebbe eliminare la differenza di prestazioni con Java.

A differenza di Java for loops, le scale di comprensione sono in realtà zucchero sintattico per i metodi di ordine superiore; in questo caso, stai chiamando il metodo foreach su un object Range . Scala è molto generico, ma a volte porta a prestazioni dolorose.

Potresti voler provare il flag -optimize in Scala versione 2.9. Le prestazioni osservate possono dipendere dalla particolare JVM in uso e l’ottimizzatore JIT dispone di un tempo di “riscaldamento” sufficiente per identificare e ottimizzare gli hot spot.

Recenti discussioni sulla mailing list indicano che il team di Scala sta lavorando per migliorare le prestazioni in casi semplici:

Ecco il problema nel bug tracker: https://issues.scala-lang.org/browse/SI-4633

Aggiornamento 5/28 :

  • Come soluzione a breve termine, il plugin ScalaCL (alpha) trasformsrà semplici loop di Scala nell’equivalente di loop while .
  • Come potenziale soluzione a lungo termine, i team dell’EPFL e di Stanford stanno collaborando a un progetto che consente la compilazione run-time di Scala “virtuale” per prestazioni molto elevate. Ad esempio, più loop funzionali idiomatici possono essere fusi in fase di esecuzione in un bytecode JVM ottimale o in un altro target come una GPU. Il sistema è estensibile, consentendo DSL definiti dall’utente e trasformazioni. Controlla le pubblicazioni e le note del corso di Stanford. Il codice preliminare è disponibile su Github, con una versione prevista per i prossimi mesi.

Come follow-up, ho provato il flag -optimize e ha ridotto il tempo di esecuzione da 103 a 76 secondi, ma è ancora 107 volte più lento di Java o di un ciclo while.

Poi stavo guardando la versione “funzionale”:

 object P005 extends App{ def isDivis(x:Int) = (1 to 20) forall {x % _ == 0} def find(n:Int):Int = if (isDivis(n)) n else find (n+2) println (find (2)) } 

e cercando di capire come sbarazzarsi del “forall” in maniera concisa. Ho fallito miseramente e mi sono inventato

 object P005_V2 extends App { def isDivis(x:Int):Boolean = { var i = 1 while(i <= 20) { if (x % i != 0) return false i += 1 } return true } def find(n:Int):Int = if (isDivis(n)) n else find (n+2) println (find (2)) } 

per cui la mia astuta soluzione a 5 linee è rimbalzata su 12 linee. Tuttavia, questa versione viene eseguita in 0,71 secondi , la stessa velocità della versione Java originale e 56 volte più veloce rispetto alla versione precedente utilizzando "forall" (40,2 s)! (vedi EDIT sotto per il motivo per cui questo è più veloce di Java)

Ovviamente il mio prossimo passo era quello di tradurre il precedente in Java, ma Java non può gestirlo e lancia un StackOverflowError con n attorno al segno 22000.

Poi ho graffiato la mia testa per un po 'e ho sostituito il "while" con un po' più di ricorsione della coda, che salva un paio di righe, corre altrettanto veloce, ma ammettiamolo, è più confusionario leggere:

 object P005_V3 extends App { def isDivis(x:Int, i:Int):Boolean = if(i > 20) true else if(x % i != 0) false else isDivis(x, i+1) def find(n:Int):Int = if (isDivis(n, 2)) n else find (n+2) println (find (2)) } 

Quindi la ricorsione a coda di Scala vince il giorno, ma sono sorpreso che qualcosa di semplice come un ciclo "for" (e il metodo "forall") sia essenzialmente rotto e debba essere sostituito da inelegant e verbose "whiles", o ricorsione di coda . Un sacco di motivi per cui sto provando Scala è dovuto alla syntax concisa, ma non va bene se il mio codice verrà eseguito 100 volte più lento!

EDIT : (cancellato)

MODIFICA DEL MODIFICO : le precedenti discrepanze tra i tempi di esecuzione di 2,5 e 0,7 secondi dipendevano interamente dal fatto che fossero utilizzate le JVM a 32 o 64 bit. Scala dalla riga di comando utilizza qualsiasi cosa sia impostata da JAVA_HOME, mentre Java utilizza 64-bit se disponibile indipendentemente. Gli IDE hanno le proprie impostazioni. Alcune misure qui: tempi di esecuzione Scala in Eclipse

La risposta sulla comprensione è giusta, ma non è tutta la storia. Si noti che l’utilizzo del isEvenlyDivisible in isEvenlyDivisible non è gratuito. L’uso del ritorno all’interno del for , costringe il compilatore di scala a generare un ritorno non locale (cioè a tornare al di fuori della sua funzione).

Questo viene fatto attraverso l’uso di un’eccezione per uscire dal ciclo. Lo stesso accade se costruisci le tue astrazioni di controllo, ad esempio:

 def loop[T](times: Int, default: T)(body: ()=>T) : T = { var count = 0 var result: T = default while(count < times) { result = body() count += 1 } result } def foo() : Int= { loop(5, 0) { println("Hi") return 5 } } foo() 

Questo stampa "Ciao" solo una volta.

Si noti che il return in foo esce da foo (che è quello che ci si aspetterebbe). Poiché l'espressione tra parentesi è una funzione letterale, che puoi vedere nella firma del loop questo costringe il compilatore a generare un ritorno non locale, cioè il return ti costringe a uscire da foo , non solo il body .

In Java (cioè la JVM) l'unico modo per implementare tale comportamento è generare un'eccezione.

Tornando a isEvenlyDivisible :

 def isEvenlyDivisible(a:Int, b:Int):Boolean = { for (i <- 2 to b) if (a % i != 0) return false return true } 

L' if (a % i != 0) return false è una funzione letterale che ha un ritorno, quindi ogni volta che viene colpito il runtime, il runtime deve lanciare e catturare un'eccezione, che causa un po 'di overhead GC.

Alcuni modi per accelerare il metodo di forall ho scoperto:

L’originale: 41,3 s

 def isDivis(x:Int) = (1 to 20) forall {x % _ == 0} 

Pre-istanziare la gamma, quindi non creiamo una nuova gamma ogni volta: 9.0 s

 val r = (1 to 20) def isDivis(x:Int) = r forall {x % _ == 0} 

Conversione in una lista anziché in un intervallo: 4,8 s

 val rl = (1 to 20).toList def isDivis(x:Int) = rl forall {x % _ == 0} 

Ho provato alcune altre raccolte ma List è stato il più veloce (anche se ancora 7 volte più lento di se evitiamo completamente la gamma e la funzione di ordine superiore).

Mentre sono nuovo di Scala, direi che il compilatore potrebbe facilmente implementare un guadagno di prestazioni rapido e significativo semplicemente sostituendo automaticamente i valori letterali di Range in metodi (come sopra) con le costanti di Intervallo nello scope più esterno. O meglio, internali come i letterali di Strings in Java.


nota a piè di pagina : gli array erano quasi uguali a quelli di Range, ma, interessantemente, la creazione di un nuovo metodo forall (mostrato sotto) ha prodotto un’esecuzione più rapida del 24% su 64 bit e dell’8% più veloce su 32 bit. Quando ho ridotto le dimensioni del calcolo riducendo il numero di fattori da 20 a 15, la differenza è scomparsa, quindi forse è un effetto di garbage collection. Qualunque sia la causa, è significativo quando si opera a pieno carico per lunghi periodi.

Anche un magnaccia simile per List ha ottenuto prestazioni migliori del 10% circa.

  val ra = (1 to 20).toArray def isDivis(x:Int) = ra forall2 {x % _ == 0} case class PimpedSeq[A](s: IndexedSeq[A]) { def forall2 (p: A => Boolean): Boolean = { var i = 0 while (i < s.length) { if (!p(s(i))) return false i += 1 } true } } implicit def arrayToPimpedSeq[A](in: Array[A]): PimpedSeq[A] = PimpedSeq(in) 

Volevo solo commentare per le persone che potrebbero perdere la fiducia in Scala su problemi come questo che questo genere di problemi emergono nell’esecuzione di quasi tutti i linguaggi funzionali. Se stai ottimizzando una piega in Haskell, dovrai spesso riscriverla come un ciclo ricorsivo ottimizzato per la coda, altrimenti avrai problemi di prestazioni e di memoria da affrontare.

So che è un peccato che i PQ non siano ancora ottimizzati al punto in cui non dobbiamo pensare a cose come questa, ma questo non è affatto un problema particolare per Scala.

I problemi specifici di Scala sono già stati discussi, ma il problema principale è che l’uso di un algoritmo a forza bruta non è molto interessante. Considera questo (molto più veloce del codice Java originale):

 def gcd(a: Int, b: Int): Int = { if (a == 0) b else gcd(b % a, a) } print (1 to 20 reduce ((a, b) => { a / gcd(a, b) * b })) 

Prova il one-liner fornito nella soluzione Scala per Project Euler

Il tempo indicato è almeno più veloce del tuo, anche se lontano dal ciclo while .. 🙂