Funktionale Programmierung - ist Unveränderlichkeit teuer? [geschlossen]

Die Frage besteht aus zwei Teilen. Der erste ist konzeptionell. Der nächste befasst sich konkreter mit der gleichen Frage in Scala.

1. Macht die Verwendung nur unveränderlicher Datenstrukturen in einer Programmiersprache die Implementierung bestimmter Algorithmen / Logik in der Praxis von Natur aus rechenintensiver? Dies beruht auf der Tatsache, dass Unveränderlichkeit ein zentraler Grundsatz rein funktionaler Sprachen ist. Gibt es andere Faktoren, die dies beeinflussen?
2. Nehmen wir ein konkreteres Beispiel. Quicksort wird im Allgemeinen unter Verwendung veränderlicher Operationen an einer speicherinternen Datenstruktur gelehrt und implementiert. Wie implementiert man so etwas auf PURE-funktionale Weise mit einem vergleichbaren Rechen- und Speicheraufwand wie die veränderbare Version? Speziell in Scala. Ich habe unten einige grobe Benchmarks aufgeführt.

Mehr Details:

Ich komme aus einem zwingenden Programmierhintergrund (C ++, Java). Ich habe mich mit funktionaler Programmierung befasst, insbesondere mit Scala.

Einige der Hauptprinzipien der reinen funktionalen Programmierung:

1. Funktionen sind erstklassige Bürger.
2. Funktionen haben keine Nebenwirkungen und daher sind Objekte / Datenstrukturen unveränderlich .

Auch wenn moderne JVMs sind extrem effizient mit Objekterstellung und Garbage Collection ist sehr preiswert für kurzlebige Objekte, ist es wahrscheinlich noch besser Objekterstellung richtig zu minimieren? Zumindest in einer Single-Threaded-Anwendung, in der Parallelität und Sperren kein Problem darstellen. Da Scala ein hybrides Paradigma ist, kann man bei Bedarf imperativen Code mit veränderlichen Objekten schreiben. Aber als jemand, der viele Jahre damit verbracht hat, Objekte wiederzuverwenden und die Zuordnung zu minimieren. Ich hätte gerne ein gutes Verständnis der Denkschule, das das nicht einmal zulässt.

Als spezieller Fall war ich ein wenig überrascht von diesem Code-Snippet in diesem Tutorial 6 . Es hat eine Java-Version von Quicksort, gefolgt von einer ordentlich aussehenden Scala-Implementierung derselben.

Hier ist mein Versuch, die Implementierungen zu bewerten. Ich habe keine detaillierte Profilerstellung durchgeführt. Ich vermute jedoch, dass die Scala-Version langsamer ist, da die Anzahl der zugewiesenen Objekte linear ist (eines pro Rekursionsaufruf). Gibt es eine Möglichkeit, dass Tail-Call-Optimierungen ins Spiel kommen können? Wenn ich recht habe, unterstützt Scala Tail-Call-Optimierungen für selbstrekursive Anrufe. Es sollte also nur helfen. Ich benutze Scala 2.8.

Java-Version

public class QuickSortJ {

    public static void sort(int[] xs) {
      sort(xs, 0, xs.length -1 );
    }

    static void sort(int[] xs, int l, int r) {
      if (r >= l) return;
      int pivot = xs[l];
      int a = l; int b = r;
      while (a <= b){
        while (xs[a] <= pivot) a++;
        while (xs[b] > pivot) b--;
        if (a < b) swap(xs, a, b);
      }
      sort(xs, l, b);
      sort(xs, a, r);
    }

    static void swap(int[] arr, int i, int j) {
      int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
    }
}

Scala-Version

object QuickSortS {

  def sort(xs: Array[Int]): Array[Int] =
    if (xs.length <= 1) xs
    else {
      val pivot = xs(xs.length / 2)
      Array.concat(
        sort(xs filter (pivot >)),
        xs filter (pivot ==),
        sort(xs filter (pivot <)))
    }
}

Scala-Code zum Vergleichen von Implementierungen

import java.util.Date
import scala.testing.Benchmark

class BenchSort(sortfn: (Array[Int]) => Unit, name:String) extends Benchmark {

  val ints = new Array[Int](100000);

  override def prefix = name
  override def setUp = {
    val ran = new java.util.Random(5);
    for (i <- 0 to ints.length - 1)
      ints(i) = ran.nextInt();
  }
  override def run = sortfn(ints)
}

val benchImmut = new BenchSort( QuickSortS.sort , "Immutable/Functional/Scala" )
val benchMut   = new BenchSort( QuickSortJ.sort , "Mutable/Imperative/Java   " )

benchImmut.main( Array("5"))
benchMut.main( Array("5"))

Ergebnisse

Zeit in Millisekunden für fünf aufeinanderfolgende Läufe

Immutable/Functional/Scala    467    178    184    187    183
Mutable/Imperative/Java        51     14     12     12     12

Da hier ein paar Missverständnisse herumfliegen, möchte ich einige Punkte klarstellen.

• Die „in-place“ QuickSort ist nicht wirklich in-place (und quicksort ist nicht per Definition in-place). Es erfordert zusätzlichen Speicher in Form von Stapelspeicher für die rekursive Schritt, der in der Reihenfolge ist O (log n ) im besten Fall, aber O ( n ) im schlechtesten Fall.

• Die Implementierung einer funktionalen Variante von Quicksort, die mit Arrays arbeitet, macht den Zweck zunichte. Arrays sind niemals unveränderlich.

• Die "richtige" funktionale Implementierung von Quicksort verwendet unveränderliche Listen. Es ist natürlich nicht an Ort und Stelle, aber es hat die gleiche asymptotische Laufzeit ( O ( n ^ 2)) und Raumkomplexität ( O ( n )) im schlimmsten Fall wie die prozedurale In-Place-Version.

  Im Durchschnitt liegt die Laufzeit immer noch auf dem Niveau der In-Place-Variante ( O ( n log n )). Seine Raumkomplexität ist jedoch immer noch O ( n ).

Es gibt zwei offensichtliche Nachteile einer funktionalen Quicksort-Implementierung. Betrachten wir im Folgenden diese Referenzimplementierung in Haskell (ich kenne Scala nicht…) aus der Haskell-Einführung :

qsort []     = []
qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
    where lesser  = (filter (< x) xs)
          greater = (filter (>= x) xs)

1. Der erste Nachteil ist die Wahl des Schwenkelements , das sehr unflexibel ist. Die Stärke moderner Quicksort-Implementierungen hängt stark von einer intelligenten Auswahl des Pivots ab (vergleiche „Engineering a sort function“ von Bentley et al. ). Der obige Algorithmus ist in dieser Hinsicht schlecht, was die durchschnittliche Leistung erheblich verschlechtert.

2. Zweitens verwendet dieser Algorithmus die Listenverkettung (anstelle der Listenkonstruktion), bei der es sich um eine O ( n ) -Operation handelt. Dies hat keinen Einfluss auf die asymptotische Komplexität, ist jedoch ein messbarer Faktor.

Ein dritter Nachteil ist etwas verborgen: Im Gegensatz zur "In-Place" -Variante fordert diese Implementierung kontinuierlich Speicher vom Heap für die Nachteile der Liste an und streut möglicherweise Speicher überall hin. Infolgedessen weist dieser Algorithmus eine sehr schlechte Cache-Lokalität auf . Ich weiß nicht, ob intelligente Allokatoren in modernen funktionalen Programmiersprachen dies abmildern können - aber auf modernen Maschinen sind Cache-Fehler zu einem großen Leistungskiller geworden.

Was ist die Schlussfolgerung? Im Gegensatz zu anderen würde ich nicht sagen, dass Quicksort von Natur aus unerlässlich ist und deshalb in einer FP-Umgebung eine schlechte Leistung erbringt. Ganz im Gegenteil, ich würde argumentieren, dass Quicksort ein perfektes Beispiel für einen funktionalen Algorithmus ist: Es lässt sich nahtlos in eine unveränderliche Umgebung übersetzen, seine asymptotische Laufzeit und Raumkomplexität entsprechen der prozeduralen Implementierung, und selbst seine prozedurale Implementierung verwendet Rekursion.

Dieser Algorithmus ist jedoch immer noch schlechter, wenn er auf eine unveränderliche Domäne beschränkt ist. Der Grund dafür ist, dass der Algorithmus die besondere Eigenschaft hat, von einer Menge (manchmal niedriger) Feinabstimmung zu profitieren, die nur auf Arrays effizient durchgeführt werden kann. Eine naive Beschreibung des Quicksortes übersieht all diese Feinheiten (sowohl in der funktionalen als auch in der prozeduralen Variante).

Nachdem ich „Engineering a sort function“ gelesen habe, kann ich Quicksortierung nicht mehr als eleganten Algorithmus betrachten. Effizient implementiert, ist es ein klobiges Durcheinander, eine Arbeit eines Ingenieurs, keine Arbeit eines Künstlers (um die Technik nicht abzuwerten! Dies hat seine eigene Ästhetik).

Ich möchte aber auch darauf hinweisen, dass dieser Punkt speziell für Quicksort gilt. Nicht jeder Algorithmus ist für die gleiche Art der Optimierung auf niedriger Ebene zugänglich. Viele Algorithmen und Datenstrukturen können in einer unveränderlichen Umgebung tatsächlich ohne Leistungsverlust ausgedrückt werden.

Unveränderlichkeit kann sogar die Leistungskosten senken, da keine kostspieligen Kopien oder Thread-übergreifenden Synchronisierungen erforderlich sind.

Um die ursprüngliche Frage zu beantworten: „ Ist Unveränderlichkeit teuer? ”- Im speziellen Fall von Quicksort entstehen Kosten, die in der Tat auf Unveränderlichkeit zurückzuführen sind. Aber im Allgemeinen nein .

Es gibt eine Reihe von Dingen, die als Benchmark der funktionalen Programmierung falsch sind. Zu den Highlights gehören:

• Sie verwenden Grundelemente, die möglicherweise eingerahmt / entpackt werden müssen. Sie versuchen nicht, den Aufwand für das Umschließen primitiver Objekte zu testen, sondern die Unveränderlichkeit zu testen.
• Sie haben einen Algorithmus gewählt, bei dem der In-Place-Betrieb ungewöhnlich effektiv ist (und dies nachweislich). Wenn Sie zeigen möchten, dass es Algorithmen gibt, die bei veränderlicher Implementierung schneller sind, ist dies eine gute Wahl. Andernfalls ist dies wahrscheinlich irreführend.
• Sie verwenden die falsche Timing-Funktion. Verwenden Sie System.nanoTime.
• Der Benchmark ist zu kurz, als dass Sie sicher sein könnten, dass die JIT-Kompilierung keinen wesentlichen Teil der gemessenen Zeit ausmacht.
• Das Array wird nicht effizient aufgeteilt.
• Arrays sind veränderlich, daher ist die Verwendung mit FP ohnehin ein seltsamer Vergleich.

Dieser Vergleich ist ein gutes Beispiel dafür, dass Sie Ihre Sprache (und Ihren Algorithmus) im Detail verstehen müssen, um Hochleistungscode zu schreiben. Aber es ist kein sehr guter Vergleich zwischen FP und Nicht-FP. Wenn Sie das möchten, schauen Sie sich Haskell vs. C ++ im Computersprachen-Benchmark-Spiel an . Die Nachricht zum Mitnehmen ist, dass die Strafe normalerweise nicht mehr als den Faktor 2 oder 3 beträgt, aber es kommt wirklich darauf an. (Keine Versprechungen, dass die Haskell-Leute auch die schnellstmöglichen Algorithmen geschrieben haben, aber zumindest einige von ihnen haben es wahrscheinlich versucht! Andererseits rufen einige der Haskell C-Bibliotheken auf ...)

Angenommen, Sie möchten einen vernünftigeren Benchmark für Quicksort, indem Sie erkennen, dass dies wahrscheinlich einer der schlimmsten Fälle für FP im Vergleich zu veränderlichen Algorithmen ist, und das Problem der Datenstruktur ignorieren (dh vorgeben, dass wir ein unveränderliches Array haben können):

object QSortExample {
  // Imperative mutable quicksort
  def swap(xs: Array[String])(a: Int, b: Int) {
    val t = xs(a); xs(a) = xs(b); xs(b) = t
  }
  def muQSort(xs: Array[String])(l: Int = 0, r: Int = xs.length-1) {
    val pivot = xs((l+r)/2)
    var a = l
    var b = r
    while (a <= b) {
      while (xs(a) < pivot) a += 1
      while (xs(b) > pivot) b -= 1
      if (a <= b) {
        swap(xs)(a,b)
        a += 1
        b -= 1
      }
    }
    if (l<b) muQSort(xs)(l, b)
    if (b<r) muQSort(xs)(a, r)
  }

  // Functional quicksort
  def fpSort(xs: Array[String]): Array[String] = {
    if (xs.length <= 1) xs
    else {
      val pivot = xs(xs.length/2)
      val (small,big) = xs.partition(_ < pivot)
      if (small.length == 0) {
        val (bigger,same) = big.partition(_ > pivot)
        same ++ fpSort(bigger)
      }
      else fpSort(small) ++ fpSort(big)
    }
  }

  // Utility function to repeat something n times
  def repeat[A](n: Int, f: => A): A = {
    if (n <= 1) f else { f; repeat(n-1,f) }
  }

  // This runs the benchmark
  def bench(n: Int, xs: Array[String], silent: Boolean = false) {
    // Utility to report how long something took
    def ptime[A](f: => A) = {
      val t0 = System.nanoTime
      val ans = f
      if (!silent) printf("elapsed: %.3f sec\n",(System.nanoTime-t0)*1e-9)
      ans
    }

    if (!silent) print("Scala builtin ")
    ptime { repeat(n, {
      val ys = xs.clone
      ys.sorted
    }) }
    if (!silent) print("Mutable ")
    ptime { repeat(n, {
      val ys = xs.clone
      muQSort(ys)()
      ys
    }) }
    if (!silent) print("Immutable ")
    ptime { repeat(n, {
      fpSort(xs)
    }) }
  }

  def main(args: Array[String]) {
    val letters = (1 to 500000).map(_ => scala.util.Random.nextPrintableChar)
    val unsorted = letters.grouped(5).map(_.mkString).toList.toArray

    repeat(3,bench(1,unsorted,silent=true))  // Warmup
    repeat(3,bench(10,unsorted))     // Actual benchmark
  }
}

Beachten Sie die Änderung am funktionalen Quicksort, damit die Daten möglichst nur einmal durchlaufen werden, und den Vergleich mit der integrierten Sortierung. Wenn wir es ausführen, erhalten wir so etwas wie:

Scala builtin elapsed: 0.349 sec
Mutable elapsed: 0.445 sec
Immutable elapsed: 1.373 sec
Scala builtin elapsed: 0.343 sec
Mutable elapsed: 0.441 sec
Immutable elapsed: 1.374 sec
Scala builtin elapsed: 0.343 sec
Mutable elapsed: 0.442 sec
Immutable elapsed: 1.383 sec

Abgesehen davon, dass es eine schlechte Idee ist, zu versuchen, eine eigene Sorte zu schreiben, stellen wir fest, dass für eine unveränderliche Quicksortierung eine ~ 3-fache Strafe anfällt, wenn letztere etwas sorgfältig implementiert wird. (Sie können auch eine Trisect-Methode schreiben, die drei Arrays zurückgibt: diejenigen, die kleiner als, die gleich und die größer als der Pivot sind. Dies kann die Geschwindigkeit etwas erhöhen.)

Ich denke nicht, dass die Scala-Version tatsächlich rekursiv ist, da Sie sie verwenden Array.concat.

Nur weil dies ein idiomatischer Scala-Code ist, bedeutet dies nicht, dass dies der beste Weg ist, dies zu tun.

Der beste Weg, dies zu tun, wäre die Verwendung einer der in Scala integrierten Sortierfunktionen. Auf diese Weise erhalten Sie die Unveränderlichkeitsgarantie und wissen, dass Sie einen schnellen Algorithmus haben.

Siehe Frage zum Stapelüberlauf. Wie sortiere ich ein Array in Scala? zum Beispiel.

Unveränderlichkeit ist nicht teuer. Es kann sicher teuer sein, wenn Sie eine kleine Teilmenge der Aufgaben messen, die ein Programm ausführen muss, und eine Lösung auswählen, die auf der Veränderbarkeit beim Booten basiert - beispielsweise das Messen von Quicksort.

Um es einfach auszudrücken: Wenn Sie rein funktionale Sprachen verwenden, sortieren Sie nicht schnell.

Betrachten wir dies aus einem anderen Blickwinkel. Betrachten wir diese beiden Funktionen:

// Version using mutable data structures
def tailFrom[T : ClassManifest](arr: Array[T], p: T => Boolean): Array[T] = {
  def posIndex(i: Int): Int = {
    if (i < arr.length) {
      if (p(arr(i)))
        i
      else
        posIndex(i + 1)
    } else {
      -1
    }
  }

  var index = posIndex(0)

  if (index < 0) Array.empty
  else {
    var result = new Array[T](arr.length - index)
    Array.copy(arr, index, result, 0, arr.length - index)
    result
  }
}

// Immutable data structure:

def tailFrom[T](list: List[T], p: T => Boolean): List[T] = {
  def recurse(sublist: List[T]): List[T] = {
    if (sublist.isEmpty) sublist
    else if (p(sublist.head)) sublist
    else recurse(sublist.tail)
  }
  recurse(list)
}

Wenn Sie DAS vergleichen, werden Sie feststellen, dass der Code, der veränderbare Datenstrukturen verwendet, eine viel schlechtere Leistung aufweist, da er das Array kopieren muss, während sich der unveränderliche Code nicht darum kümmern muss.

Wenn Sie mit unveränderlichen Datenstrukturen programmieren, strukturieren Sie Ihren Code so, dass seine Stärken genutzt werden. Es ist nicht einfach der Datentyp oder sogar einzelne Algorithmen. Das Programm wird gestaltet in einer anderen Art und Weise.

Deshalb ist Benchmarking normalerweise bedeutungslos. Entweder wählen Sie Algorithmen, die für den einen oder anderen Stil natürlich sind, und dieser Stil gewinnt, oder Sie vergleichen die gesamte Anwendung, was häufig unpraktisch ist.

Das Sortieren eines Arrays ist wie die wichtigste Aufgabe im Universum. Es ist nicht überraschend, dass viele elegante 'unveränderliche' Strategien / Implementierungen auf einem 'Sort a Array'-Mikrobenchmark schlecht scheitern. Dies bedeutet jedoch nicht, dass Unveränderlichkeit "im Allgemeinen" teuer ist. Es gibt viele Aufgaben, bei denen unveränderliche Implementierungen vergleichbar mit veränderlichen ausgeführt werden, aber die Sortierung von Arrays gehört häufig nicht dazu.

Wenn Sie Ihre imperativen Algorithmen und Datenstrukturen einfach in eine funktionale Sprache umschreiben, ist dies in der Tat teuer und nutzlos. Um die Dinge zum Leuchten zu bringen, sollten Sie die Funktionen verwenden, die nur in der funktionalen Programmierung verfügbar sind: Persistenz der Datenstrukturen, verzögerte Auswertungen usw.

Die Kosten der Unveränderlichkeit in Scala

Hier ist eine Version, die fast so schnell ist wie die Java-Version. ;)

object QuickSortS {
  def sort(xs: Array[Int]): Array[Int] = {
    val res = new Array[Int](xs.size)
    xs.copyToArray(res)
    (new QuickSortJ).sort(res)
    res
  }
}

Diese Version erstellt eine Kopie des Arrays, sortiert es mithilfe der Java-Version und gibt die Kopie zurück. Scala zwingt Sie nicht dazu, intern unveränderliche Strukturen zu verwenden.

Der Vorteil von Scala ist also, dass Sie die Veränderlichkeit und Unveränderlichkeit nach Belieben nutzen können. Der Nachteil ist, dass Sie, wenn Sie das falsch machen, die Vorteile der Unveränderlichkeit nicht wirklich nutzen.

QuickSort ist bekanntermaßen schneller, wenn es vor Ort durchgeführt wird. Dies ist also kaum ein fairer Vergleich!

Trotzdem ... Array.concat? Wenn nichts anderes, zeigen Sie, wie langsam ein für die imperative Programmierung optimierter Sammlungstyp ist, wenn Sie versuchen, ihn in einem funktionalen Algorithmus zu verwenden. Fast jede andere Wahl wäre schneller!

Ein weiterer sehr wichtiger Punkt, der beim Vergleich der beiden Ansätze vielleicht am wichtigsten ist, ist: "Wie gut lässt sich dies auf mehrere Knoten / Kerne skalieren?"

Wenn Sie nach einer unveränderlichen Quicksortierung suchen, tun Sie dies wahrscheinlich, weil Sie tatsächlich eine parallele Quicksortierung wünschen. Wikipedia hat einige Zitate zu diesem Thema: http://en.wikipedia.org/wiki/Quicksort#Parallelizations

Die Scala-Version kann einfach gegabelt werden, bevor die Funktion erneut ausgeführt wird, sodass eine Liste mit Milliarden von Einträgen sehr schnell sortiert werden kann, wenn genügend Kerne verfügbar sind.

Derzeit stehen der GPU in meinem System 128 Kerne zur Verfügung, wenn ich nur den Scala-Code darauf ausführen könnte, und dies auf einem einfachen Desktop-System, das zwei Jahre hinter der aktuellen Generation liegt.

Wie würde sich das gegen den imperativen Ansatz mit einem Thread verhalten, frage ich mich ...

Vielleicht ist die wichtigere Frage daher:

"Angesichts der Tatsache, dass einzelne Kerne nicht schneller werden und Synchronisation / Sperren eine echte Herausforderung für die Parallelisierung darstellen, ist Mutabilität teuer?"

Es wurde gesagt, dass die OO-Programmierung Abstraktion verwendet, um Komplexität zu verbergen, und funktionale Programmierung Unveränderlichkeit verwendet, um Komplexität zu entfernen. In der hybriden Welt von Scala können wir OO verwenden, um den imperativen Code zu verbergen, sodass der Anwendungscode nicht klüger bleibt. In der Tat verwenden die Sammlungsbibliotheken viel imperativen Code, aber das bedeutet nicht, dass wir sie nicht verwenden sollten. Wie andere gesagt haben, bekommt man hier mit Sorgfalt das Beste aus beiden Welten.