Advanced Scala: Tail Recursion und Optimierung

Was bedeutet das für unser Beispiel? Ist sum endrekursiv? Natürlich nicht! Zwar steht der rekursive Aufruf „ganz hinten“, aber die letze Aktion ist die Addition. Daher sollten wir uns überlegen, wie wir die Implementierung ändern können, sodass sie endrekursiv wird. Das führt uns zu der Frage, wie wir die Addition umgehen können. Und zu folgender Antwort:

def sumtr(numbers: List[Int]): Int = {
  @tailrec
  def sumtr(numbers: List[Int], result: Int): Int = {
    numbers match {
      case Nil => result
      case x :: xs => sumtr(xs, x + result)
    }
  }
  sumtr(numbers, 0)
}

Wir behalten „nach außen hin“ die einfache Signatur und führen eine lokale Methode ein, die nicht nur die Int-Liste als Parameter enthält, sondern auch das Zwischenergebnis. Auf diese Weise können wir diese interne Methode so implementieren, dass sie endrekursiv ist: Wir rufen sie einfach mit der verkürzten Liste und dem Ergebnis der Addition auf, d. h. die Addition kommt jetzt vor der Rekursion.

Seit Scala 2.8 können wir die Annotation @tailrec verwenden, um sicherzustellen, dass die damit annotierte Methode tatsächlich endrekursiv ist. Würden wir diese Annotation auf die ursprüngliche sum-Variante anwenden, erhielten wir einen Compiler-Fehler.

Laufzeitverhalten

Anhand unseres kleinen Beispiels können wir ganz einfach die Auswirkungen der Tail Call Optimization sehen, wenn wir einen Micro-Benchmark schreiben. Der Code dazu befindet sich auf github unter http://wiki.github.com/weiglewilczek/demo-scala und natürlich sind Fragen oder Kommentare herzlich willkommen.

Das Ergebnis ist wie erwartet: Mit Tail Call Optimization läuft der Code deutlich schneller; auf einem aktuellen Mac Book Pro mit Java 1.6 und Scala 2.8.0 etwas mehr als doppelt so schnell. Und vor allem fliegt uns ohne Tail Call Optimization bald der Stack um die Ohren; ohne JVM-Tuning und mit obiger Konfiguration schon bei Listen mit 10 000 Elementen.

Das bedeutet, dass wir immer dann, wenn wir „nicht kleine“ Datenmengen rekursiv bearbeiten wollen, unbedingt endrekursiv im Sinne von Scala arbeiten sollten.

Heiko Seeberger ist geschäftsführender Gesellschafter der Weigle Wilczek GmbH und verantwortlich für die technologische Strategie des Unternehmens mit den Schwerpunkten Java, Scala, OSGi, Eclipse RCP, Lift und Akka. Zudem ist er aktiver Open Source Committer, Autor zahlreicher Fachartikel und Redner auf einschlägigen Konferenzen.
Kommentare

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.