Wie kann ich das Verständnis und die Schleifen in Scala optimieren?

Scala soll also so schnell sein wie Java. Ich besuche einige Project Euler- Probleme in Scala, die ich ursprünglich in Java angegangen bin. Speziell Problem 5: "Was ist die kleinste positive Zahl, die durch alle Zahlen von 1 bis 20 gleichmäßig 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
    }
}

Zum Schluss noch mein Versuch einer funktionalen Programmierung, die 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 nur viel schneller?

Das Problem in diesem speziellen Fall ist, dass Sie aus dem for-Ausdruck zurückkehren. Dies wird wiederum in einen Wurf einer NonLocalReturnException übersetzt, die bei der einschließenden Methode abgefangen wird. Der Optimierer kann den Foreach eliminieren, aber den Wurf / Fang noch nicht 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 eines forVerständnisses in der Methode isEvenlyDivisible. Das Ersetzen fordurch eine äquivalente whileSchleife sollte den Leistungsunterschied zu Java beseitigen.

Im Gegensatz zu Javas forSchleifen ist Scalas forVerständnis tatsächlich syntaktischer Zucker für Methoden höherer Ordnung. In diesem Fall rufen Sie die foreachMethode für ein RangeObjekt auf. Scala forist sehr allgemein, führt aber manchmal zu schmerzhaften Leistungen.

Vielleicht möchten Sie das -optimizeFlag in Scala Version 2.9 ausprobieren . Die beobachtete Leistung kann von der jeweils verwendeten JVM abhängen, und der JIT-Optimierer verfügt über eine ausreichende Aufwärmzeit, um Hotspots zu identifizieren und zu optimieren.

Jüngste Diskussionen auf der Mailingliste zeigen, dass das Scala-Team forin einfachen Fällen daran arbeitet, die Leistung zu verbessern :

• 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 Bug-Tracker: https://issues.scala-lang.org/browse/SI-4633

Update 5/28 :

• Als kurzfristige Lösung wandelt das ScalaCL- Plugin (Alpha) einfache Scala-Schleifen in das Äquivalent von whileSchleifen um.
• Als mögliche längerfristige Lösung arbeiten Teams aus der EPFL und Stanford an einem Projekt, das die Laufzeitkompilierung von "virtuellen" Scala für eine sehr hohe Leistung ermöglicht. Beispielsweise können mehrere idiomatische Funktionsschleifen zur Laufzeit zu einem optimalen JVM-Bytecode oder zu einem anderen Ziel wie einer GPU zusammengeführt werden. Das System ist erweiterbar und ermöglicht benutzerdefinierte DSLs und Transformationen. Lesen Sie die Veröffentlichungen und Stanford- Kursnotizen . Der vorläufige Code ist auf Github verfügbar und wird in den kommenden Monaten veröffentlicht.

Als Folge habe ich das Flag -optimize 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 versuchen herauszufinden, wie man das "Forall" auf prägnante Weise loswird. Ich habe kläglich versagt und mir etwas ausgedacht

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

wobei meine listige 5-Zeilen-Lösung auf 12 Zeilen aufgestockt wurde. Diese Version läuft jedoch in 0,71 Sekunden , der gleichen 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 bestand mein nächster Schritt darin, das oben Gesagte wieder in Java zu übersetzen, aber Java kann damit nicht umgehen und wirft einen StackOverflowError mit n um die 22000-Marke.

Ich kratzte mir dann ein bisschen am Kopf und ersetzte das "while" durch ein bisschen mehr Schwanzrekursion, die ein paar Zeilen spart, genauso schnell läuft, aber seien wir ehrlich, es 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 wortreiche "whiles" oder Schwanzrekursion ersetzt werden muss . Viele der Gründe, warum ich Scala ausprobiere, sind die präzise Syntax, aber es ist nicht gut, wenn mein Code 100-mal langsamer ausgeführt wird!

BEARBEITEN : (gelöscht)

EDIT OF EDIT : Frühere Abweichungen zwischen Laufzeiten von 2,5 s und 0,7 s waren ausschließlich darauf zurückzuführen, ob 32-Bit- oder 64-Bit-JVMs verwendet wurden. Scala über die Befehlszeile verwendet alles, was von JAVA_HOME festgelegt wurde, während Java 64-Bit verwendet, sofern 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 returnin isEvenlyDivisiblenicht kostenlos ist. Die Verwendung von return innerhalb von forzwingt den Scala-Compiler, eine nicht lokale Rückgabe zu generieren (dh außerhalb seiner Funktion zurückzukehren).

Dies erfolgt durch die Verwendung einer Ausnahme zum Verlassen der Schleife. Das gleiche passiert, wenn Sie Ihre eigenen Steuerelementabstraktionen 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()

Dies druckt "Hi" nur einmal.

Beachten Sie, dass die returnIn- fooExits foo(was Sie erwarten würden). Da der Ausdruck in Klammern ein Funktionsliteral ist, das Sie in der Signatur loopdieses Ausdrucks sehen können, wird der Compiler gezwungen, eine nicht lokale Rückgabe zu generieren, returndh die Sie zum Beenden zwingen foo, nicht 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 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 falseist ein Funktionsliteral, das eine Rückgabe hat. Jedes Mal, wenn die Rückgabe getroffen wird, muss die Laufzeit eine Ausnahme auslösen und abfangen, was einen erheblichen GC-Overhead verursacht.

Einige Möglichkeiten, um die von forallmir entdeckte Methode zu beschleunigen :

Das Original: 41,3 s

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

Vorinstanziieren des Bereichs, damit nicht jedes Mal ein neuer Bereich erstellt wird: 9,0 s

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

Konvertieren in eine Liste anstelle eines Bereichs: 4,8 s

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 die Funktion höherer Ordnung insgesamt vermeiden).

Obwohl ich neu in Scala bin, würde ich vermuten, dass der Compiler leicht einen schnellen und signifikanten Leistungsgewinn erzielen kann, indem er Range-Literale in Methoden (wie oben) 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 gleich wie Range, aber interessanterweise führte das Pimpen einer neuen forallMethode (siehe unten) zu einer 24% schnelleren Ausführung auf 64-Bit und 8% schneller auf 32-Bit. Als ich die Berechnungsgröße durch Reduzieren der Anzahl der Faktoren von 20 auf 15 reduzierte, verschwand der Unterschied, sodass es sich möglicherweise um einen Speicherbereinigungseffekt handelt. Was auch immer die Ursache sein mag, es ist wichtig, wenn Sie längere Zeit unter Volllast arbeiten.

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 könnten, kommentieren, dass diese Art von Problemen bei der Ausführung nahezu aller funktionalen Sprachen auftreten. Wenn Sie eine Falte in Haskell optimieren, müssen Sie sie häufig als rekursive, für Endanrufe optimierte Schleife neu schreiben, da sonst Leistungs- und Speicherprobleme auftreten.

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

Scala-spezifische Probleme wurden bereits diskutiert, aber das Hauptproblem ist, dass die Verwendung eines Brute-Force-Algorithmus nicht sehr cool ist. Beachten 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
}))

Probieren Sie den in der Lösung Scala for Project Euler angegebenen Einzeiler aus

Die angegebene Zeit ist mindestens schneller als Ihre, obwohl weit entfernt von der while-Schleife .. :)