¿Por qué se comprime más rápido que zip en Scala?

He escrito un código Scala para realizar una operación basada en elementos en una colección. Aquí definí dos métodos que realizan la misma tarea. Un método usa zipy el otro usa 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)

Para comparar estos dos métodos en términos de velocidad, escribí el siguiente código:

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

Llamo al funmétodo y paso ESy ES1como a continuación:

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)

Los resultados muestran que el método nombrado ES1que usa zippedes más rápido que el método ESque usa zip. En base a estas observaciones, tengo dos preguntas.

¿Por qué es zippedmás rápido que zip?

¿Hay alguna forma aún más rápida de realizar operaciones basadas en elementos en una colección en Scala?

Para responder a su segunda pregunta:

¿Hay alguna forma más rápida de hacer operaciones con elementos inteligentes en una colección en Scala?

La triste verdad es que a pesar de su concisión, productividad mejorada y resistencia a los errores, los lenguajes funcionales no son necesariamente los más efectivos: el uso de funciones de orden superior para definir una proyección que se ejecutará en colecciones no gratuitas, y su ciclo cerrado lo resalta. Como otros han señalado, la asignación de almacenamiento adicional para resultados intermedios y finales también tendrá gastos generales.

Si el rendimiento es crítico, aunque de ninguna manera es universal, en casos como el suyo, puede desenrollar las operaciones de Scala en equivalentes imperativos para recuperar un control más directo sobre el uso de la memoria y eliminar las llamadas a funciones.

En su ejemplo específico, las zippedsumas se pueden realizar imperativamente asignando previamente una matriz fija y mutable del tamaño correcto (ya que zip se detiene cuando una de las colecciones se queda sin elementos) y luego agrega elementos juntos en el índice apropiado (desde acceder elementos de matriz por índice ordinal es una operación muy rápida).

Agregar una tercera función, ES3a su conjunto de pruebas:

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
}

En mi i7 obtengo los siguientes tiempos de respuesta:

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

Aún más audaz sería hacer una mutación directa en el lugar de las dos matrices más cortas, lo que obviamente corrompería el contenido de una de las matrices, y solo se haría si la matriz original nuevamente no fuera necesaria:

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

Pero obviamente, la mutación directa de los elementos de la matriz no está en el espíritu de Scala.

Ninguna de las otras respuestas menciona la razón principal de la diferencia de velocidad, que es que la zippedversión evita las asignaciones de 10.000 tuplas. Como un par de las otras respuestas hacer nota, la zipversión implica una serie intermedia, mientras que la zippedversión no, pero la asignación de un conjunto de 10.000 elementos no es lo que hace que la zipversión mucho peor-se las 10.000 tuplas de corta duración que se están poniendo en esa matriz. Estos están representados por objetos en la JVM, por lo que está haciendo un montón de asignaciones de objetos para cosas que inmediatamente va a tirar.

El resto de esta respuesta solo entra en un poco más de detalles sobre cómo puede confirmar esto.

Mejor benchmarking

Realmente desea utilizar un marco como jmh para realizar cualquier tipo de evaluación comparativa de manera responsable en la JVM, e incluso entonces la parte responsable es difícil, aunque configurar jmh en sí no es tan malo. Si tienes algo project/plugins.sbtcomo esto:

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

Y build.sbtasí (estoy usando 2.11.8 ya que mencionas que es lo que estás usando):

scalaVersion := "2.11.8"

enablePlugins(JmhPlugin)

Entonces puede escribir su punto de referencia de esta manera:

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

Y ejecútalo con 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

Lo que muestra que la zippedversión obtiene aproximadamente un 80% más de rendimiento, lo que probablemente es más o menos lo mismo que sus mediciones.

Medición de asignaciones

También puede pedirle a jmh que mida las asignaciones con -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

... donde gc.alloc.rate.normes probablemente la parte más interesante, que muestra que la zipversión se está asignando más de tres veces zipped.

Implementaciones imperativas

Si supiera que este método se llamaría en contextos extremadamente sensibles al rendimiento, probablemente lo implementaría así:

  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
  }

Tenga en cuenta que, a diferencia de la versión optimizada en una de las otras respuestas, esta utiliza en whilelugar de una forya forque todavía se desugará en las operaciones de colecciones Scala. Podemos comparar esta implementación ( withWhile), la implementación optimizada (pero no en el lugar) de la otra respuesta ( withFor) y las dos implementaciones 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

Esa es una gran diferencia entre las versiones imperativas y funcionales, y todas estas firmas de métodos son exactamente idénticas y las implementaciones tienen la misma semántica. No es como si las implementaciones imperativas estuvieran usando un estado global, etc. Si bien las versiones zipy zippedson más legibles, personalmente no creo que tenga sentido que las versiones imperativas estén en contra del "espíritu de Scala", y no dudaría para usarlos yo mismo.

Con tabular

Actualización: agregué una tabulateimplementación al punto de referencia basado en un comentario en otra respuesta:

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

Es mucho más rápido que las zipversiones, aunque sigue siendo mucho más lento que los imperativos:

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

Esto es lo que esperaría, ya que no hay nada inherentemente costoso en llamar a una función, y porque acceder a los elementos de la matriz por índice es muy barato.

Considerar lazyZip

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

en vez de zip

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

Scala 2.13 añadido lazyZip a favor de.zipped

Junto con las .zipvistas, esto reemplaza .zipped(ahora en desuso). ( scala / colección-strawman # 223 )

zipped(y, por lo tanto lazyZip) es más rápido que zipporque, como lo explicaron Tim y Mike Allen , zipseguido mapresultará en dos transformaciones separadas debido a la rigidez, mientras que zippedseguido mapdará como resultado una sola transformación ejecutada de una vez debido a la pereza.

zippedda Tuple2Zipped, y analizando 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()
  }

vemos las dos colecciones coll1y coll2se repiten una y otra vez en cada iteración, la función que se fpasa mapse aplica a lo largo del camino

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

sin tener que asignar y transformar estructuras intermedias.

Aplicando el método de evaluación comparativa de Travis, aquí hay una comparación entre nuevos lazyZipy obsoletos zippeddonde

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

da

[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

lazyZipparece funcionar un poco mejor que zippeden ArraySeq. Curiosamente, observe el rendimiento degradado significativamente cuando se utiliza lazyZipen Array.

Siempre debe tener cuidado con la medición del rendimiento debido a la compilación JIT, pero una razón probable es que zippedes perezosa y extrae elementos de las Arraycápsulas originales durante la mapllamada, mientras que zipcrea un nuevo Arrayobjeto y luego llama mapal nuevo objeto.