Pourquoi la fermeture éclair est-elle plus rapide que la fermeture éclair dans Scala?

J'ai écrit du code Scala pour effectuer une opération élément par élément sur une collection. Ici, j'ai défini deux méthodes qui effectuent la même tâche. Une méthode utilise zipet l'autre utilise zipped.

def ES (arr :Array[Double], arr1 :Array[Double]) :Array[Double] = arr.zip(arr1).map(x => x._1 + x._2)

def ES1(arr :Array[Double], arr1 :Array[Double]) :Array[Double] = (arr,arr1).zipped.map((x,y) => x + y)

Pour comparer ces deux méthodes en termes de vitesse, j'ai écrit le code suivant:

def fun (arr : Array[Double] , arr1 : Array[Double] , f :(Array[Double],Array[Double]) => Array[Double] , itr : Int) ={
  val t0 = System.nanoTime()
  for (i <- 1 to itr) {
       f(arr,arr1)
       }
  val t1 = System.nanoTime()
  println("Total Time Consumed:" + ((t1 - t0).toDouble / 1000000000).toDouble + "Seconds")
}

J'appelle la funméthode et passe ESet ES1comme ci-dessous:

fun(Array.fill(10000)(math.random), Array.fill(10000)(math.random), ES , 100000)
fun(Array.fill(10000)(math.random), Array.fill(10000)(math.random), ES1, 100000)

Les résultats montrent que la méthode nommée ES1qui utilise zippedest plus rapide que la méthode ESqui utilise zip. Sur la base de ces observations, j'ai deux questions.

Pourquoi est zippedplus rapide que zip?

Existe-t-il un moyen encore plus rapide d'effectuer des opérations élément par élément sur une collection dans Scala?

Pour répondre à votre deuxième question:

Existe-t-il un moyen plus rapide d'effectuer des opérations par élément sur une collection dans Scala?

La triste vérité est que malgré sa concision, sa productivité améliorée et sa résilience aux bogues, les langages fonctionnels ne sont pas nécessairement les plus performants - en utilisant des fonctions d'ordre supérieur pour définir une projection à exécuter contre des collections non libres, et votre boucle serrée le met en évidence. Comme d'autres l'ont souligné, l'allocation de stockage supplémentaire pour les résultats intermédiaires et finaux aura également des frais généraux.

Si les performances sont critiques, bien que nullement universelles, dans des cas comme le vôtre, vous pouvez dérouler les opérations de Scala en équivalents impératifs afin de reprendre un contrôle plus direct sur l'utilisation de la mémoire et d'éliminer les appels de fonction.

Dans votre exemple spécifique, les zippedsommes peuvent être effectuées impérativement en pré-allouant un tableau fixe et modifiable de taille correcte (car zip s'arrête lorsque l'une des collections manque d'éléments), puis en ajoutant ensemble des éléments à l'index approprié (depuis l'accès à éléments de tableau par index ordinal est une opération très rapide).

Ajout d'une troisième fonction ES3à votre suite de tests:

def ES3(arr :Array[Double], arr1 :Array[Double]) :Array[Double] = {
   val minSize = math.min(arr.length, arr1.length)
   val array = Array.ofDim[Double](minSize)
   for (i <- 0 to minSize - 1) {
     array(i) = arr(i) + arr1(i)
   }
  array
}

Sur mon i7, je reçois les temps de réponse suivants:

OP ES Total Time Consumed:23.3747857Seconds
OP ES1 Total Time Consumed:11.7506995Seconds
--
ES3 Total Time Consumed:1.0255231Seconds

Encore plus haineux serait de faire une mutation directe sur place du plus court des deux tableaux, ce qui corromprait évidemment le contenu de l'un des tableaux, et ne serait fait que si le tableau d'origine à nouveau n'était pas nécessaire:

def ES4(arr :Array[Double], arr1 :Array[Double]) :Array[Double] = {
   val minSize = math.min(arr.length, arr1.length)
   val array = if (arr.length < arr1.length) arr else arr1
   for (i <- 0 to minSize - 1) {
      array(i) = arr(i) + arr1(i)
   }
  array
}

Total Time Consumed:0.3542098Seconds

Mais évidemment, la mutation directe des éléments du tableau n'est pas dans l'esprit de Scala.

Aucune des autres réponses ne mentionne la principale raison de la différence de vitesse, à savoir que la zippedversion évite 10 000 attributions de tuple. En tant que deux autres réponses ne note, la zipVersion implique un tableau intermédiaire, alors que la zippedversion ne pas, mais l' attribution d' un tableau pour 10.000 éléments ne sont pas ce qui fait la la zipversion tellement pire , ce sont les 10.000 tuples vécu court que sont mis dans ce tableau. Celles-ci sont représentées par des objets sur la JVM, donc vous faites un tas d'allocations d'objets pour des choses que vous allez immédiatement jeter.

Le reste de cette réponse va juste dans un peu plus de détails sur la façon dont vous pouvez le confirmer.

Meilleure analyse comparative

Vous voulez vraiment utiliser un framework comme jmh pour effectuer n'importe quel type d'analyse comparative de manière responsable sur la JVM, et même dans ce cas, la partie responsable est difficile, bien que la configuration de jmh lui-même ne soit pas trop mauvaise. Si vous en avez un project/plugins.sbtcomme ça:

addSbtPlugin("pl.project13.scala" % "sbt-jmh" % "0.3.7")

Et un build.sbtcomme ça (j'utilise 2.11.8 puisque vous mentionnez que c'est ce que vous utilisez):

scalaVersion := "2.11.8"

enablePlugins(JmhPlugin)

Ensuite, vous pouvez écrire votre référence comme ceci:

package zipped_bench

import org.openjdk.jmh.annotations._

@State(Scope.Benchmark)
@BenchmarkMode(Array(Mode.Throughput))
class ZippedBench {
  val arr1 = Array.fill(10000)(math.random)
  val arr2 = Array.fill(10000)(math.random)

  def ES(arr: Array[Double], arr1: Array[Double]): Array[Double] =
    arr.zip(arr1).map(x => x._1 + x._2)

  def ES1(arr: Array[Double], arr1: Array[Double]): Array[Double] =
    (arr, arr1).zipped.map((x, y) => x + y)

  @Benchmark def withZip: Array[Double] = ES(arr1, arr2)
  @Benchmark def withZipped: Array[Double] = ES1(arr1, arr2)
}

Et lancez-le avec sbt "jmh:run -i 10 -wi 10 -f 2 -t 1 zipped_bench.ZippedBench":

Benchmark                Mode  Cnt     Score    Error  Units
ZippedBench.withZip     thrpt   20  4902.519 ± 41.733  ops/s
ZippedBench.withZipped  thrpt   20  8736.251 ± 36.730  ops/s

Ce qui montre que la zippedversion obtient environ 80% de débit en plus, ce qui est probablement plus ou moins le même que vos mesures.

Mesurer les allocations

Vous pouvez également demander à jmh de mesurer les allocations avec -prof gc:

Benchmark                                                 Mode  Cnt        Score       Error   Units
ZippedBench.withZip                                      thrpt    5     4894.197 ±   119.519   ops/s
ZippedBench.withZip:·gc.alloc.rate                       thrpt    5     4801.158 ±   117.157  MB/sec
ZippedBench.withZip:·gc.alloc.rate.norm                  thrpt    5  1080120.009 ±     0.001    B/op
ZippedBench.withZip:·gc.churn.PS_Eden_Space              thrpt    5     4808.028 ±    87.804  MB/sec
ZippedBench.withZip:·gc.churn.PS_Eden_Space.norm         thrpt    5  1081677.156 ± 12639.416    B/op
ZippedBench.withZip:·gc.churn.PS_Survivor_Space          thrpt    5        2.129 ±     0.794  MB/sec
ZippedBench.withZip:·gc.churn.PS_Survivor_Space.norm     thrpt    5      479.009 ±   179.575    B/op
ZippedBench.withZip:·gc.count                            thrpt    5      714.000              counts
ZippedBench.withZip:·gc.time                             thrpt    5      476.000                  ms
ZippedBench.withZipped                                   thrpt    5    11248.964 ±    43.728   ops/s
ZippedBench.withZipped:·gc.alloc.rate                    thrpt    5     3270.856 ±    12.729  MB/sec
ZippedBench.withZipped:·gc.alloc.rate.norm               thrpt    5   320152.004 ±     0.001    B/op
ZippedBench.withZipped:·gc.churn.PS_Eden_Space           thrpt    5     3277.158 ±    32.327  MB/sec
ZippedBench.withZipped:·gc.churn.PS_Eden_Space.norm      thrpt    5   320769.044 ±  3216.092    B/op
ZippedBench.withZipped:·gc.churn.PS_Survivor_Space       thrpt    5        0.360 ±     0.166  MB/sec
ZippedBench.withZipped:·gc.churn.PS_Survivor_Space.norm  thrpt    5       35.245 ±    16.365    B/op
ZippedBench.withZipped:·gc.count                         thrpt    5      863.000              counts
ZippedBench.withZipped:·gc.time                          thrpt    5      447.000                  ms

… Où gc.alloc.rate.normest probablement la partie la plus intéressante, montrant que la zipversion alloue plus de trois fois plus zipped.

Implémentations impératives

Si je savais que cette méthode allait être appelée dans des contextes extrêmement sensibles aux performances, je l'implémenterais probablement comme ceci:

  def ES3(arr: Array[Double], arr1: Array[Double]): Array[Double] = {
    val minSize = math.min(arr.length, arr1.length)
    val newArr = new Array[Double](minSize)
    var i = 0
    while (i < minSize) {
      newArr(i) = arr(i) + arr1(i)
      i += 1
    }
    newArr
  }

Notez que contrairement à la version optimisée dans l'une des autres réponses, celle-ci utilise à la whileplace d'un forcar la forva toujours se dissiper dans les opérations de collections Scala. Nous pouvons comparer cette implémentation ( withWhile), l' implémentation optimisée (mais pas en place) de l'autre réponse ( withFor), et les deux implémentations originales:

Benchmark                Mode  Cnt       Score      Error  Units
ZippedBench.withFor     thrpt   20  118426.044 ± 2173.310  ops/s
ZippedBench.withWhile   thrpt   20  119834.409 ±  527.589  ops/s
ZippedBench.withZip     thrpt   20    4886.624 ±   75.567  ops/s
ZippedBench.withZipped  thrpt   20    9961.668 ± 1104.937  ops/s

C'est une énorme différence entre les versions impérative et fonctionnelle, et toutes ces signatures de méthode sont exactement identiques et les implémentations ont la même sémantique. Ce n'est pas comme si les implémentations impératives utilisaient l'état global, etc. Bien que les versions zipet zippedsoient plus lisibles, personnellement, je ne pense pas qu'il y ait un sens dans lequel les versions impératives sont contre "l'esprit de Scala", et je n'hésiterais pas de les utiliser moi-même.

Avec tabuler

Mise à jour: j'ai ajouté une tabulateimplémentation à la référence basée sur un commentaire dans une autre réponse:

def ES4(arr: Array[Double], arr1: Array[Double]): Array[Double] = {
  val minSize = math.min(arr.length, arr1.length)
  Array.tabulate(minSize)(i => arr(i) + arr1(i))
}

C'est beaucoup plus rapide que les zipversions, bien que beaucoup plus lent que les impératifs:

Benchmark                  Mode  Cnt      Score     Error  Units
ZippedBench.withTabulate  thrpt   20  32326.051 ± 535.677  ops/s
ZippedBench.withZip       thrpt   20   4902.027 ±  47.931  ops/s

C'est ce à quoi je m'attendrais, car il n'y a rien de intrinsèquement coûteux à appeler une fonction, et parce que l'accès aux éléments de tableau par index est très bon marché.

Considérer lazyZip

(as lazyZip bs) map { case (a, b) => a + b }

au lieu de zip

(as zip bs) map { case (a, b) => a + b }

Scala 2.13 ajouté lazyZip en faveur de.zipped

Avec .zipon vues, cela remplace .zipped(désormais obsolète). ( scala / collection-paille # 223 )

zipped(et donc lazyZip) est plus rapide que zipparce que , comme expliqué par Tim et Mike Allen , zipsuivi de mapentraînera deux transformations distinctes en raison de la rigueur, tandis que zippedsuivi mapentraînera une seule transformation exécutée en une seule fois en raison de la paresse.

zippeddonne Tuple2Zippedet analyse Tuple2Zipped.map,

class Tuple2Zipped[...](val colls: (It1, It2)) extends ... {
  private def coll1 = colls._1
  private def coll2 = colls._2

  def map[...](f: (El1, El2) => B)(...) = {
    val b = bf.newBuilder(coll1)
    ...
    val elems1 = coll1.iterator
    val elems2 = coll2.iterator

    while (elems1.hasNext && elems2.hasNext) {
      b += f(elems1.next(), elems2.next())
    }

    b.result()
  }

nous voyons les deux collections coll1et coll2sommes itérés sur et à chaque itération la fonction fpassée mapest appliquée en cours de route

b += f(elems1.next(), elems2.next())

sans avoir à allouer et transformer des structures intermédiaires.

En appliquant la méthode d'analyse comparative de Travis, voici une comparaison entre les nouveaux lazyZipet les obsolètes zippedoù

@State(Scope.Benchmark)
@BenchmarkMode(Array(Mode.Throughput))
class ZippedBench {
  import scala.collection.mutable._
  val as = ArraySeq.fill(10000)(math.random)
  val bs = ArraySeq.fill(10000)(math.random)

  def lazyZip(as: ArraySeq[Double], bs: ArraySeq[Double]): ArraySeq[Double] =
    as.lazyZip(bs).map{ case (a, b) => a + b }

  def zipped(as: ArraySeq[Double], bs: ArraySeq[Double]): ArraySeq[Double] =
    (as, bs).zipped.map { case (a, b) => a + b }

  def lazyZipJavaArray(as: Array[Double], bs: Array[Double]): Array[Double] =
    as.lazyZip(bs).map{ case (a, b) => a + b }

  @Benchmark def withZipped: ArraySeq[Double] = zipped(as, bs)
  @Benchmark def withLazyZip: ArraySeq[Double] = lazyZip(as, bs)
  @Benchmark def withLazyZipJavaArray: ArraySeq[Double] = lazyZipJavaArray(as.toArray, bs.toArray)
}

donne

[info] Benchmark                          Mode  Cnt      Score      Error  Units
[info] ZippedBench.withZipped            thrpt   20  20197.344 ± 1282.414  ops/s
[info] ZippedBench.withLazyZip           thrpt   20  25468.458 ± 2720.860  ops/s
[info] ZippedBench.withLazyZipJavaArray  thrpt   20   5215.621 ±  233.270  ops/s

lazyZipsemble fonctionner un peu mieux que zippedsur ArraySeq. Fait intéressant, notez les performances considérablement dégradées lors de l'utilisation lazyZipsur Array.

Vous devez toujours être prudent avec la mesure des performances en raison de la compilation JIT, mais une raison probable est qu'il zippedest paresseux et extrait des éléments des Arrayvaules d' origine pendant l' mapappel, alors qu'il zipcrée un nouvel Arrayobjet et appelle ensuite maple nouvel objet.