Wie optimiert man For-Comprehensions und Schleifen in Scala?

Scala soll also so schnell sein wie Java. Ich greife einige wieder auf Projekt Euler Probleme in Scala, die ich ursprünglich in Java angegangen bin. Insbesondere Aufgabe 5: “Was ist die kleinste positive Zahl, die durch alle Zahlen von 1 bis 20 ohne Rest teilbar ist?”

Hier ist meine Java-Lösung, die auf meinem Computer 0,7 Sekunden dauert:

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

Hier ist meine “direkte Übersetzung” in Scala, die 103 Sekunden dauert (147-mal länger!)

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

Hier ist endlich mein Versuch der funktionalen Programmierung, der 39 Sekunden dauert (55-mal länger)

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

Verwenden von Scala 2.9.0.1 unter Windows 7 64-Bit. Wie verbessere ich die Leistung? Mache ich etwas falsch? Oder ist Java einfach viel schneller?

Das Problem in diesem speziellen Fall ist, dass Sie innerhalb des for-Ausdrucks zurückkehren. Dies wird wiederum in einen Wurf einer NonLocalReturnException übersetzt, die von der einschließenden Methode abgefangen wird. Der Optimierer kann foreach eliminieren, kann aber noch nicht throw/catch eliminieren. Und Werfen/Fangen ist teuer. Da solche verschachtelten Rückgaben in Scala-Programmen jedoch selten sind, hat der Optimierer diesen Fall noch nicht behandelt. Es wird daran gearbeitet, den Optimierer zu verbessern, der dieses Problem hoffentlich bald lösen wird.

Das Problem ist höchstwahrscheinlich die Verwendung von a for Verständnis in der Methode isEvenlyDivisible. Ersetzen for durch ein Äquivalent while Schleife sollte den Leistungsunterschied zu Java eliminieren.

Im Gegensatz zu Java for Schleifen, Scalas for Verständnisse sind eigentlich syntaktischer Zucker für Methoden höherer Ordnung; In diesem Fall rufen Sie die an foreach Methode auf a Range Objekt. Scalas for ist sehr allgemein, führt aber manchmal zu einer schmerzhaften Leistung.

Vielleicht möchten Sie die ausprobieren -optimize Flag in Scala-Version 2.9. Die beobachtete Leistung kann von der jeweils verwendeten JVM abhängen und davon, dass der JIT-Optimierer ausreichend “Aufwärmzeit” hat, um Hotspots zu identifizieren und zu optimieren.

Aktuelle Diskussionen auf der Mailingliste zeigen, dass das Scala-Team an Verbesserungen arbeitet for Leistung in einfachen Fällen:

• http://groups.google.com/group/scala-user/browse_thread/thread/86adb44d72ef4498
• http://groups.google.com/group/scala-language/browse_thread/thread/94740a10205dddd2

Hier ist das Problem im Bugtracker:
https://issues.scala-lang.org/browse/SI-4633

Update 28.5:

• Als kurzfristige Lösung bietet die ScalaCL plugin (Alpha) verwandelt einfache Scala-Loops in das Äquivalent von while Schleifen.
• Als potenzielle längerfristige Lösung gelten Teams von der EPFL und Stanford an einem Projekt mitarbeiten Aktivierung der Laufzeitkompilierung von “virtuelle” Scala für sehr hohe Leistung. Beispielsweise können mehrere idiomatische Funktionsschleifen sein zur Laufzeit verschmolzen in den optimalen JVM-Bytecode oder an ein anderes Ziel wie eine GPU. Das System ist erweiterbar und ermöglicht benutzerdefinierte DSLs und Transformationen. Probier das aus Veröffentlichungen und Stanford Kursnotizen. Vorläufiger Code ist auf Github verfügbar, eine Veröffentlichung ist in den kommenden Monaten geplant.

Als Folge habe ich das -optimize-Flag ausprobiert und es hat die Laufzeit von 103 auf 76 Sekunden reduziert, aber das ist immer noch 107x langsamer als Java oder eine While-Schleife.

Dann habe ich mir die “funktionale” Version angesehen:

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

und versucht herauszufinden, wie man das “forall” auf prägnante Weise loswird. Ich bin kläglich gescheitert und kam mit

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

wodurch sich meine schlaue 5-Zeilen-Lösung auf 12 Zeilen aufgebläht hat. Diese Version läuft jedoch ein 0,71 Sekunden, die gleiche Geschwindigkeit wie die ursprüngliche Java-Version und 56-mal schneller als die obige Version mit “forall” (40,2 s)! (siehe EDIT unten, warum dies schneller als Java ist)

Natürlich war mein nächster Schritt, das obige wieder in Java zu übersetzen, aber Java kann damit nicht umgehen und wirft einen StackOverflowError mit n um die 22000-Marke.

Ich habe mich dann ein bisschen am Kopf gekratzt und das “while” durch etwas mehr Schwanzrekursion ersetzt, was ein paar Zeilen spart, genauso schnell läuft, aber seien wir ehrlich, ist verwirrender zu lesen:

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

Scalas Schwanzrekursion gewinnt also den Tag, aber ich bin überrascht, dass etwas so Einfaches wie eine „for“-Schleife (und die „forall“-Methode) im Wesentlichen kaputt ist und durch unelegante und ausführliche „whiles“ oder Schwanzrekursion ersetzt werden muss . Viele der Gründe, warum ich Scala ausprobiere, sind die knappe Syntax, aber es nützt nichts, wenn mein Code 100-mal langsamer läuft!

BEARBEITEN: (gelöscht)

BEARBEITEN VON BEARBEITEN: Frühere Abweichungen zwischen den Laufzeiten von 2,5 s und 0,7 s waren ausschließlich darauf zurückzuführen, ob die 32-Bit- oder 64-Bit-JVMs verwendet wurden. Scala von der Befehlszeile verwendet, was auch immer von JAVA_HOME festgelegt wird, während Java 64-Bit verwendet, falls verfügbar, unabhängig davon. IDEs haben ihre eigenen Einstellungen. Einige Messungen hier: Scala-Ausführungszeiten in Eclipse

Die Antwort zum Verständnis ist richtig, aber es ist nicht die ganze Geschichte. Sie sollten beachten, dass die Verwendung von return in isEvenlyDivisible ist nicht frei. Die Verwendung von Return innerhalb der forzwingt den Scala-Compiler, eine nicht-lokale Rückgabe zu generieren (dh außerhalb seiner Funktion zurückzugeben).

Dies geschieht durch die Verwendung einer Ausnahme zum Verlassen der Schleife. Dasselbe passiert, wenn Sie Ihre eigenen Kontrollabstraktionen erstellen, zum Beispiel:

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

Dadurch wird “Hi” nur einmal gedruckt.

Notiere dass der return in foo Ausgänge foo (was man erwarten würde). Da der Ausdruck in Klammern ein Funktionsliteral ist, können Sie dies in der Signatur von sehen loop Dies zwingt den Compiler, eine nicht lokale Rückgabe zu generieren, d. h. die return zwingt Sie zum Ausstieg foonicht nur die body.

In Java (dh der JVM) besteht die einzige Möglichkeit, ein solches Verhalten zu implementieren, darin, eine Ausnahme auszulösen.

Zurück gehen zu isEvenlyDivisible:

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

Das if (a % i != 0) return false ist ein Funktionsliteral mit einer Rückgabe, sodass die Laufzeit jedes Mal, wenn die Rückgabe getroffen wird, eine Ausnahme auslösen und abfangen muss, was ziemlich viel GC-Overhead verursacht.

Einige Möglichkeiten, um die forall Methode, die ich entdeckt habe:

Das Original: 41,3 Sek

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

Den Bereich vorab instanziieren, damit wir nicht jedes Mal einen neuen Bereich erstellen: 9,0 Sek

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

Konvertieren in eine Liste statt in einen Bereich: 4,8 Sek

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

Ich habe ein paar andere Sammlungen ausprobiert, aber List war am schnellsten (obwohl immer noch 7x langsamer, als wenn wir die Range- und Higher-Order-Funktion insgesamt vermeiden würden).

Obwohl ich neu bei Scala bin, würde ich vermuten, dass der Compiler leicht eine schnelle und signifikante Leistungssteigerung implementieren könnte, indem er Range-Literale in Methoden (wie oben) einfach automatisch durch Range-Konstanten im äußersten Bereich ersetzt. Oder besser, internieren Sie sie wie Strings-Literale in Java.

Fußnote: Arrays waren ungefähr das gleiche wie Range, aber interessanterweise ein neues Pimping forall -Methode (siehe unten) führte zu einer um 24 % schnelleren Ausführung auf 64-Bit und zu einer um 8 % schnelleren Ausführung auf 32-Bit. Als ich die Berechnungsgröße reduzierte, indem ich die Anzahl der Faktoren von 20 auf 15 reduzierte, verschwand der Unterschied, also ist es vielleicht ein Garbage-Collection-Effekt. Was auch immer die Ursache ist, es ist wichtig, wenn es über längere Zeiträume unter Volllast betrieben wird.

Ein ähnlicher Zuhälter für List führte auch zu einer um etwa 10 % besseren Leistung.

  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)  

Ich wollte nur für Leute, die wegen solcher Probleme das Vertrauen in Scala verlieren, anmerken, dass diese Art von Problemen bei der Leistung von fast allen funktionalen Sprachen auftreten. Wenn Sie einen Fold in Haskell optimieren, müssen Sie ihn oft als rekursive Tail-Call-optimierte Schleife neu schreiben, da Sie sonst mit Leistungs- und Speicherproblemen zu kämpfen haben.

Ich weiß, es ist bedauerlich, dass FPs noch nicht so weit optimiert sind, dass wir über solche Dinge nicht nachdenken müssen, aber das ist überhaupt kein Scala-spezifisches Problem.

Scala-spezifische Probleme wurden bereits diskutiert, aber das Hauptproblem besteht darin, dass die Verwendung eines Brute-Force-Algorithmus nicht sehr cool ist. Bedenken Sie Folgendes (viel schneller als der ursprüngliche Java-Code):

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