Programmation fonctionnelle - l'immuabilité est-elle chère? [fermé]

La question est en deux parties. Le premier est conceptuel. Le suivant aborde la même question plus concrètement dans Scala.

1. L'utilisation uniquement de structures de données immuables dans un langage de programmation rend-elle la mise en œuvre de certains algorithmes / logiques intrinsèquement plus coûteuse en calcul? Cela tient au fait que l'immuabilité est un principe fondamental des langages purement fonctionnels. Y a-t-il d'autres facteurs qui ont un impact sur cela?
2. Prenons un exemple plus concret. Quicksort est généralement enseigné et implémenté à l'aide d'opérations mutables sur une structure de données en mémoire. Comment implémenter une telle chose de manière fonctionnelle PURE avec une surcharge de calcul et de stockage comparable à la version mutable. Plus précisément dans Scala. J'ai inclus quelques repères bruts ci-dessous.

Plus de détails:

Je viens d'un fond de programmation impératif (C ++, Java). J'ai exploré la programmation fonctionnelle, en particulier Scala.

Certains des principes fondamentaux de la programmation fonctionnelle pure:

1. Les fonctions sont des citoyens de première classe.
2. Les fonctions n'ont pas d'effets secondaires et donc les objets / structures de données sont immuables .

Même si les JVM modernes sont extrêmement efficaces avec la création d'objets et le garbage collection est très peu coûteux pour les objets de courte durée, il est probablement toujours préférable de minimiser la création d'objets, n'est-ce pas? Au moins dans une application à un seul thread où la concurrence et le verrouillage ne sont pas un problème. Puisque Scala est un paradigme hybride, on peut choisir d'écrire du code impératif avec des objets mutables si nécessaire. Mais, en tant que personne qui a passé de nombreuses années à essayer de réutiliser des objets et de minimiser l'allocation. J'aimerais avoir une bonne compréhension de l'école de pensée qui ne permettrait même pas cela.

En tant que cas particulier, j'ai été un peu surpris par cet extrait de code dans ce tutoriel 6 . Il a une version Java de Quicksort suivie d'une implémentation Scala soignée de la même chose.

Voici ma tentative de comparer les implémentations. Je n'ai pas fait de profilage détaillé. Mais, je suppose que la version Scala est plus lente car le nombre d'objets alloués est linéaire (un par appel de récursivité). Y a-t-il une chance que les optimisations des appels de queue puissent entrer en jeu? Si j'ai raison, Scala prend en charge les optimisations des appels de queue pour les appels auto-récursifs. Donc, cela ne devrait que l'aider. J'utilise Scala 2.8.

Version Java

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

Version Scala

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

Code Scala pour comparer les implémentations

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

Résultats

Temps en millisecondes pour cinq exécutions consécutives

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

Puisqu'il y a quelques idées fausses qui volent ici, j'aimerais clarifier certains points.

• Le tri rapide «en place» n'est pas vraiment en place (et le tri rapide n'est pas par définition en place). Il nécessite un stockage supplémentaire sous forme d'espace de pile pour l'étape récursive, qui est de l'ordre de O (log n ) dans le meilleur des cas, mais O ( n ) dans le pire des cas.

• L'implémentation d'une variante fonctionnelle de tri rapide qui fonctionne sur des tableaux va à l'encontre de l'objectif. Les tableaux ne sont jamais immuables.

• L'implémentation fonctionnelle «appropriée» du tri rapide utilise des listes immuables. Il n'est bien sûr pas en place, mais il a le même runtime asymptotique dans le pire des cas ( O ( n ^ 2)) et la même complexité spatiale ( O ( n )) que la version procédurale sur place.

  En moyenne, son temps de fonctionnement est toujours comparable à celui de la variante en place ( O ( n log n )). Sa complexité spatiale, cependant, est toujours O ( n ).

Une implémentation fonctionnelle de tri rapide présente deux inconvénients évidents . Dans ce qui suit, considérons cette implémentation de référence dans Haskell (je ne connais pas Scala…) de l' introduction de Haskell :

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

1. Le premier inconvénient est le choix de l'élément de pivot , qui est très rigide. La force des implémentations modernes de tri rapide repose en grande partie sur un choix intelligent du pivot (comparez avec «Engineering a sort function» de Bentley et al. ). L'algorithme ci-dessus est médiocre à cet égard, ce qui dégrade considérablement les performances moyennes.

2. Deuxièmement, cet algorithme utilise la concaténation de liste (au lieu de la construction de liste) qui est un O ( n ). Cela n'a pas d'impact sur la complexité asymptotique mais c'est un facteur mesurable.

Un troisième inconvénient est quelque peu caché: contrairement à la variante «in-place», cette implémentation demande continuellement de la mémoire du tas pour les cellules cons de la liste et disperse potentiellement de la mémoire partout. En conséquence, cet algorithme a une localisation de cache très pauvre . Je ne sais pas si les allocateurs intelligents dans les langages de programmation fonctionnels modernes peuvent atténuer cela - mais sur les machines modernes, les erreurs de cache sont devenues un tueur majeur des performances.

Quelle est la conclusion?Contrairement à d'autres, je ne dirais pas que le tri rapide est intrinsèquement impératif et c'est pourquoi il fonctionne mal dans un environnement FP. Bien au contraire, je dirais que le tri rapide est un exemple parfait d'algorithme fonctionnel: il se traduit de manière transparente en un environnement immuable, son temps d'exécution asymptotique et sa complexité spatiale sont à égalité avec l'implémentation procédurale, et même son implémentation procédurale utilise la récursivité.

Mais cet algorithme toujours moins bien lorsqu'il est contraint à un domaine immuable. La raison en est que l'algorithme a la propriété particulière de bénéficier de nombreux réglages fins (parfois de bas niveau) qui ne peuvent être effectués efficacement que sur des tableaux. Une description naïve du tri rapide passe à côté de toutes ces subtilités (à la fois dans la variante fonctionnelle et dans la variante procédurale).

Après avoir lu «Ingénierie d'une fonction de tri», je ne peux plus considérer le tri rapide comme un algorithme élégant. Mis en œuvre efficacement, c'est un gâchis maladroit, une œuvre d'ingénieur, pas d'artiste (ne pas dévaloriser l'ingénierie! Cela a sa propre esthétique).

Mais je voudrais aussi souligner que ce point est particulier au tri rapide. Tous les algorithmes ne se prêtent pas au même type d'ajustement de bas niveau. De nombreux algorithmes et structures de données peuvent vraiment être exprimés sans perte de performances dans un environnement immuable.

Et l'immuabilité peut même réduire les coûts de performance en supprimant le besoin de copies coûteuses ou de synchronisations cross-thread.

Donc, pour répondre à la question initiale, «l' immuabilité est-elle chère? »- Dans le cas particulier du tri rapide, il y a un coût qui résulte bien de l'immuabilité. Mais en général, non .

Il y a un tas de choses qui ne vont pas avec cela comme référence de la programmation fonctionnelle. Les points forts incluent:

• Vous utilisez des primitives, qui peuvent devoir être encadrées / déballées. Vous n'essayez pas de tester la surcharge de l'encapsulation d'objets primitifs, vous essayez de tester l'immuabilité.
• Vous avez choisi un algorithme dans lequel le fonctionnement sur place est exceptionnellement efficace (et cela est prouvé). Si vous voulez montrer qu'il existe des algorithmes qui sont plus rapides lorsqu'ils sont implémentés mutuellement, alors c'est un bon choix; sinon, cela est susceptible d'induire en erreur.
• Vous utilisez la mauvaise fonction de chronométrage. Utilisez System.nanoTime.
• Le benchmark est trop court pour que vous puissiez être sûr que la compilation JIT ne représentera pas une partie significative du temps mesuré.
• Le tableau n'est pas divisé de manière efficace.
• Les tableaux sont mutables, donc les utiliser avec FP est de toute façon une comparaison étrange.

Donc, cette comparaison est une excellente illustration que vous devez comprendre votre langage (et algorithme) en détail afin d'écrire du code haute performance. Mais ce n'est pas une très bonne comparaison entre FP et non-FP. Si vous le souhaitez, consultez Haskell vs C ++ au jeu de référence des langages informatiques . Le message à retenir est que la pénalité n'est généralement pas supérieure à un facteur de 2 ou 3 ou plus, mais cela dépend vraiment. (Aucune promesse que les gens de Haskell ont écrit les algorithmes les plus rapides possible non plus, mais au moins certains d'entre eux ont probablement essayé! Là encore, certains des Haskell appellent des bibliothèques C ....)

Maintenant, supposons que vous souhaitiez un benchmark plus raisonnable de Quicksort, en reconnaissant qu'il s'agit probablement de l'un des pires cas pour les algorithmes FP vs mutables, et en ignorant le problème de structure des données (c'est-à-dire en prétendant que nous pouvons avoir un Array immuable):

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

Notez la modification du tri rapide fonctionnel afin qu'il ne passe par les données qu'une seule fois, si possible, et la comparaison avec le tri intégré. Lorsque nous l'exécutons, nous obtenons quelque chose comme:

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

Donc, en plus d'apprendre qu'essayer d'écrire votre propre tri est une mauvaise idée, nous constatons qu'il y a une pénalité de ~ 3x pour un tri rapide immuable si ce dernier est mis en œuvre avec un peu de soin. (Vous pouvez également écrire une méthode trisect qui renvoie trois tableaux: ceux inférieurs à, ceux égaux et ceux supérieurs au pivot. Cela pourrait accélérer légèrement les choses.)

Je ne pense pas que la version Scala soit réellement récursive, puisque vous utilisez Array.concat.

De plus, ce n'est pas parce qu'il s'agit d'un code Scala idiomatique que c'est la meilleure façon de le faire.

La meilleure façon de le faire serait d'utiliser l'une des fonctions de tri intégrées de Scala. De cette façon, vous obtenez la garantie d'immuabilité et savez que vous disposez d'un algorithme rapide.

Voir la question Stack Overflow Comment trier un tableau dans Scala? à titre d'exemple.

L'immuabilité n'est pas chère. Cela peut certainement être coûteux si vous mesurez un petit sous-ensemble des tâches qu'un programme doit effectuer et choisissez une solution basée sur la mutabilité pour démarrer, comme la mesure du tri rapide.

Pour faire simple, vous ne faites pas de tri rapide lorsque vous utilisez des langages purement fonctionnels.

Considérons cela sous un autre angle. Considérons ces deux fonctions:

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

Benchmark THAT, et vous constaterez que le code utilisant des structures de données mutables a des performances bien pires, car il doit copier le tableau, alors que le code immuable n'a pas besoin de se préoccuper de cela.

Lorsque vous programmez avec des structures de données immuables, vous structurez votre code pour tirer parti de ses atouts. Ce n'est pas simplement le type de données, ni même les algorithmes individuels. Le programme sera conçu d'une manière différente.

C'est pourquoi l'analyse comparative n'a généralement pas de sens. Soit vous choisissez des algorithmes naturels à un style ou à un autre, et ce style l'emporte, soit vous comparez l'ensemble de l'application, ce qui est souvent peu pratique.

Le tri d'un tableau est, par exemple, la tâche la plus impérative de l'univers. Il n'est pas surprenant que de nombreuses stratégies / implémentations élégantes «immuables» échouent mal sur un microbenchmark «trier un tableau». Cela n'implique cependant pas que l'immuabilité soit chère "en général". Il existe de nombreuses tâches où les implémentations immuables fonctionneront de manière comparable à celles modifiables, mais le tri de tableaux n'en fait souvent pas partie.

Si vous réécrivez simplement vos algorithmes impératifs et vos structures de données dans un langage fonctionnel, cela sera en effet coûteux et inutile. Pour faire briller les choses, vous devez utiliser les fonctionnalités disponibles uniquement en programmation fonctionnelle: persistance des structures de données, évaluations paresseuses, etc.

Le coût de l'immuabilité dans Scala

Voici une version presque aussi rapide que celle de Java. ;)

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

Cette version fait une copie du tableau, le trie en place à l'aide de la version Java et renvoie la copie. Scala ne vous oblige pas à utiliser une structure immuable en interne.

L'avantage de Scala est que vous pouvez tirer parti de la mutabilité et de l'immuabilité comme bon vous semble. L'inconvénient est que si vous faites cela mal, vous n'obtenez pas vraiment les avantages de l'immuabilité.

QuickSort est connu pour être plus rapide lorsqu'il est effectué sur place, ce n'est donc pas une comparaison juste!

Cela dit ... Array.concat? Si rien d'autre, vous montrez comment un type de collection optimisé pour la programmation impérative est particulièrement lent lorsque vous essayez de l'utiliser dans un algorithme fonctionnel; presque n'importe quel autre choix serait plus rapide!

Un autre point très important à prendre en compte, peut - être le problème le plus important lors de la comparaison des deux approches est: "Dans quelle mesure cette échelle est-elle étendue à plusieurs nœuds / cœurs?"

Si vous recherchez un tri rapide immuable, il y a de fortes chances que vous le fassiez parce que vous voulez en fait un tri rapide parallèle. Wikipedia a quelques citations à ce sujet: http://en.wikipedia.org/wiki/Quicksort#Parallelizations

La version scala peut simplement bifurquer avant que la fonction ne se répète, ce qui lui permet de trier très rapidement une liste contenant des milliards d'entrées si vous avez suffisamment de cœurs disponibles.

À l'heure actuelle, le GPU de mon système a 128 cœurs à ma disposition si je pouvais simplement exécuter le code Scala dessus, et cela sur un simple système de bureau avec deux ans de retard sur la génération actuelle.

Comment cela se comparerait-il à l'approche impérative à un seul thread, je me demande ...

La question la plus importante est peut-être donc:

"Étant donné que les cœurs individuels ne vont pas être plus rapides et que la synchronisation / verrouillage présente un réel défi pour la parallélisation, la mutabilité est-elle chère?"

Il a été dit que la programmation OO utilise l'abstraction pour masquer la complexité, et la programmation fonctionnelle utilise l'immuabilité pour éliminer la complexité. Dans le monde hybride de Scala, nous pouvons utiliser OO pour masquer le code impératif en laissant le code d'application pas plus sage. En effet, les bibliothèques de collections utilisent beaucoup de code impératif mais cela ne signifie pas que nous ne devrions pas les utiliser. Comme d'autres l'ont dit, utilisé avec soin, vous obtenez vraiment le meilleur des deux mondes ici.