Pourquoi ma rentrée de queue Scala est-elle plus rapide que la boucle while?

Question

Voici deux solutions pour l'exercice 4.9 Cay Horstmann de la Scala pour les Impatients: "Écrire une fonction lteqgt(valeurs: Array[Int], v: Int) renvoie une triple contenant le nombre de valeurs inférieures à v, égal à v, et plus grande que v." On utilise la récursivité tail, l'autre utilise une boucle while. Je pensais que les deux se compiler similaire bytecode, mais la boucle while est plus lente que la queue de la récursivité par un facteur de près de 2. Cela me fait penser que ma tandis que la méthode est mal écrit.

import scala.annotation.tailrec
import scala.util.Random
object PerformanceTest {

  def main(args: Array[String]): Unit = {
    val bigArray:Array[Int] = fillArray(new Array[Int](100000000))
    println(time(lteqgt(bigArray, 25)))
    println(time(lteqgt2(bigArray, 25)))
  }

  def time[T](block : => T):T = {
    val start = System.nanoTime : Double
    val result = block
    val end = System.nanoTime : Double
    println("Time = " + (end - start) / 1000000.0 + " millis")
    result
  }

  @tailrec def fillArray(a:Array[Int], pos:Int=0):Array[Int] = {
    if (pos == a.length)
      a
    else {
      a(pos) = Random.nextInt(50)
      fillArray(a, pos+1)
    }
  }

  @tailrec def lteqgt(values: Array[Int], v:Int, lt:Int=0, eq:Int=0, gt:Int=0, pos:Int=0):(Int, Int, Int) = {
    if (pos == values.length)
      (lt, eq, gt)
    else
      lteqgt(values, v, lt + (if (values(pos) < v) 1 else 0), eq + (if (values(pos) == v) 1 else 0), gt + (if (values(pos) > v) 1 else 0), pos+1) 
  }

  def lteqgt2(values:Array[Int], v:Int):(Int, Int, Int) = {
    var lt = 0
    var eq = 0
    var gt = 0
    var pos = 0
    val limit = values.length
    while (pos < limit) {
      if (values(pos) > v)
        gt += 1
      else if (values(pos) < v)
        lt += 1
      else
        eq += 1
      pos += 1
    }
    (lt, eq, gt)
  }
}

Ajuster la taille de bigArray en fonction de votre taille de segment de mémoire. Voici un exemple de sortie:

Time = 245.110899 millis
(50004367,2003090,47992543)
Time = 465.836894 millis
(50004367,2003090,47992543)

Pourquoi le tout en méthode beaucoup plus lent que la tailrec? Naïvement le tailrec version a l'air d'être à un léger désavantage, car il doit toujours effectuer 3 "si" vérifie pour chaque itération, alors que le tout en version souvent seulement d'effectuer 1 ou 2 tests en raison de la construction. (NB l'inversion de l'ordre-je effectuer les deux méthodes n'affecte pas le résultat).

Answer 1

Des résultats de Test (après réduction de la taille de la matrice à 20000000)

Sous Java 1.6.22 - je obtenir de l' 151 and 122 ms de la queue-de récursivité et de tout-boucle respectivement.

Sous Java 1.7.0 - je obtenir de l' 55 and 101 ms

Ainsi, en vertu de la version 6 de Java votre tout-boucle est en fait plus rapide, et les deux sont l'amélioration de performance dans le cadre de Java 7, mais la queue-une version récursive a dépassé la boucle.

Explication

La différence de performances est due au fait que, dans votre boucle, vous conditionnellement ajouter 1 à la somme des totaux, tandis que la récursivité vous toujours ajouter 1 ou 0. Donc, ils ne sont pas équivalents. L'équivalent, tandis que la boucle de votre méthode récursive est:

  def lteqgt2(values:Array[Int], v:Int):(Int, Int, Int) = {
    var lt = 0
    var eq = 0
    var gt = 0
    var pos = 0
    val limit = values.length
    while (pos < limit) {
      gt += (if (values(pos) > v) 1 else 0)
      lt += (if (values(pos) < v) 1 else 0)
      eq += (if (values(pos) == v) 1 else 0)
      pos += 1
    }
    (lt, eq, gt)
  }

et cela donne exactement le même temps d'exécution comme la méthode récursive (indépendamment de la version de Java).

Discussion

Je ne suis pas un expert sur les raisons de la VM Java 7 (HotSpot) peut optimiser ce mieux que la première version, mais je suppose que c'est parce que c'est prendre le même chemin à travers le code à chaque fois (plutôt que de ramification le long de la if / else if de chemins), de sorte que le bytecode peut être incorporé de manière plus efficace.

Mais n'oubliez pas que ce n'est pas le cas dans la version 6 de Java. Pourquoi un tout-boucle surpasse les autres est une question de JVM internes. Heureusement pour la Scala programmeur, la version produite à partir de l'orchestration à la queue-la récursivité est la plus rapide dans la dernière version de la JVM.

Answer 2

Les deux concepts ne sont pas identiques. En particulier, dans le premier cas, vous n'avez pas besoin de sauts (sur x86, vous pouvez utiliser le cpm et le setle et d'ajouter, au lieu d'avoir à utiliser le cpm et le jb et (si vous ne sautez pas) ajouter. Pas de saut est plus rapide que de sauter sur à peu près tous à l'architecture moderne.

Donc, si vous avez un code qui ressemble à

if (a < b) x += 1

où vous pouvez ajouter ou vous pouvez sauter au lieu de cela, vs

x += (a < b)

(qui n'a de sens en C/C++, où 1 = vrai et 0 = faux), celle-ci tend à être plus rapide, car il peut être transformé en de plus en plus compacts du code assembleur. En Scala/Java, vous ne pouvez pas faire cela, mais vous pouvez le faire

x += if (a < b) 1 else 0

qui une smart JVM doit reconnaître, c'est la même chose que x += (a < b), qui a un jump-gratuit code machine de la traduction, qui est généralement plus rapide que de sauter. Encore plus intelligent JVM permettrait de reconnaître que

if (a < b) x += 1

est le même encore une fois (car l'ajout de zéro ne fait rien).

Compilateurs C/C++ régulièrement procéder à des optimisations de ce genre. Étant dans l'impossibilité d'appliquer l'un de ces optimisations n'était pas une marque dans le compilateur JIT faveur; apparemment, il peut en tant que de 1,7, mais seulement en partie (c'est à dire qu'il ne reconnaît pas que l'ajout de zéro est le même comme une condition de l'ajout d'une, mais elle permet au moins d'convertir x += if (a<b) 1 else 0 rapide code machine).

Maintenant, rien de tout cela n'a rien à voir avec la queue de la récursivité ou les boucles "while" en soi. Avec la queue de la récursivité, c'est plus naturel d'écrire l' if (a < b) 1 else 0 formulaire, mais vous pouvez le faire soit; et avec des boucles while vous pouvez aussi le faire. Il se trouve que vous avez choisi une forme de queue de la récursivité et l'autre pour la boucle while, la faire ressembler à la récursivité vs boucle était le changement au lieu de deux différentes façons de faire de l'conditionnelles.