Por que o zipado é mais rápido que o zip no Scala?

Eu escrevi algum código Scala para executar uma operação elemento a elemento em uma coleção. Aqui eu defini dois métodos que executam a mesma tarefa. Um método usa zipe o outro 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 esses dois métodos em termos de velocidade, escrevi o seguinte 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")
}

Eu chamo o funmétodo e passo ESe ES1como abaixo:

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)

Os resultados mostram que o método nomeado ES1que usa zippedé mais rápido que o método ESque usa zip. Com base nessas observações, tenho duas perguntas.

Por que é zippedmais rápido que zip?

Existe uma maneira ainda mais rápida de executar operações por elementos em uma coleção no Scala?

Para responder sua segunda pergunta:

Existe alguma maneira mais rápida de executar operações com elementos em uma coleção no Scala?

A triste verdade é que, apesar da concisão, da produtividade aprimorada e da resiliência aos bugs, as linguagens funcionais não são necessariamente as de maior desempenho - usando funções de ordem superior para definir uma projeção a ser executada em coleções não gratuitas, e seu loop restrito destaca isso. Como outros salientaram, a alocação de armazenamento adicional para resultados intermediários e finais também terá custos indiretos.

Se o desempenho for crítico, embora de modo algum universal, em casos como o seu, você pode recuperar as operações do Scala de volta a equivalentes imperativos, a fim de recuperar um controle mais direto sobre o uso da memória e eliminar as chamadas de função.

No seu exemplo específico, as zippedsomas podem ser executadas imperativamente pré-alocando uma matriz fixa e mutável do tamanho correto (já que o zip pára quando uma das coleções fica sem elementos) e, em seguida, adiciona elementos no índice apropriado (desde o acesso elementos da matriz pelo índice ordinal é uma operação muito rápida).

Adicionando uma terceira função ES3ao seu conjunto de testes:

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
}

No meu i7, recebo os seguintes tempos de resposta:

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

Ainda mais hediondo seria fazer a mutação direta no local da mais curta das duas matrizes, o que obviamente corromperia o conteúdo de uma das matrizes e só seria feita se a matriz original novamente não fosse necessária:

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

Mas, obviamente, a mutação direta dos elementos da matriz não está no espírito de Scala.

Nenhuma das outras respostas menciona o principal motivo da diferença de velocidade: a zippedversão evita 10.000 alocações de tupla. Como um casal das outras respostas fazer nota, a zipversão envolve um conjunto intermediário, enquanto que a zippedversão não, mas alocar uma matriz para 10.000 elementos não é o que faz com que a zipversão muito pior-É a 10.000 tuplas viveu-curtas que estão sendo colocados nessa matriz. Eles são representados por objetos na JVM, portanto, você está realizando várias alocações de objetos para coisas que imediatamente descartará.

O restante desta resposta entra em um pouco mais de detalhes sobre como você pode confirmar isso.

Melhor benchmarking

Você realmente quer usar uma estrutura como jmh para fazer qualquer tipo de benchmarking de forma responsável na JVM, e mesmo assim a parte responsável é difícil, embora a configuração do jmh em si não seja tão ruim. Se você tem algo project/plugins.sbtassim:

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

E algo build.sbtassim (estou usando o 2.11.8, já que você mencionou que é isso que está usando):

scalaVersion := "2.11.8"

enablePlugins(JmhPlugin)

Em seguida, você pode escrever sua referência como esta:

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

E execute-o com 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

O que mostra que a zippedversão obtém uma taxa de transferência 80% mais alta, o que provavelmente é mais ou menos o mesmo que suas medidas.

Medindo alocações

Você também pode pedir ao jmh para medir alocações com -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

… Onde gc.alloc.rate.normé provavelmente a parte mais interessante, mostrando que ozip versão está alocando mais de três vezes o valor zipped.

Implementações imperativas

Se eu soubesse que esse método seria chamado em contextos extremamente sensíveis ao desempenho, provavelmente o implementaria assim:

  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
  }

Observe que, diferentemente da versão otimizada em uma das outras respostas, isso usa, em whilevez de um, forpois o forainda será desugar nas operações de coleta do Scala. Podemos comparar essa implementação ( withWhile), a outra resposta otimizada (mas não no local) ( withFor) e as duas implementações originais:

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

Essa é realmente uma enorme diferença entre as versões imperativa e funcional, e todas essas assinaturas de método são exatamente idênticas e as implementações têm a mesma semântica. Não é como se as implementações imperativas estivessem usando o estado global, etc.zipzipped versões e sejam mais legíveis, eu pessoalmente acho que não há sentido em que as versões imperativas sejam contrárias ao "espírito de Scala" e não hesitaria em para usá-los eu mesmo.

With tabate

Atualização: eu adicionei uma tabulateimplementação ao benchmark com base em um comentário em outra resposta:

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

É muito mais rápido que as zipversões, embora ainda muito mais lento que as imperativas:

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

Isso é o que eu esperaria, já que não há nada inerentemente caro em chamar uma função e porque acessar elementos de matriz por índice é muito barato.

Considerar lazyZip

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

ao invés de zip

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

Scala 2.13 adicionado a lazyZip favor de.zipped

Juntamente com as .zipvisualizações, isso substitui .zipped(agora descontinuado). ( scala / collection-strawman # 223 )

zipped(e, portanto lazyZip) é mais rápido do que zipporque, conforme explicado por Tim e Mike Allen , zipseguido por mapresultará em duas transformações separadas devido ao rigor, enquanto zippedseguido pormap resultará em uma única transformação executada de uma só vez devido à preguiça.

zippeddá Tuple2Zipped, e analisando 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 as duas coleções coll1e coll2somos iterados repetidamente e a cada iteração à qual a função ftransmitida mapé aplicada ao longo do caminho

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

sem ter que alocar e transformar estruturas intermediárias.

Aplicando o método de benchmarking de Travis, aqui está uma comparação entre novo lazyZipe obsoleto, zippedonde

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

dá

[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 ter um desempenho um pouco melhor do que zippedem ArraySeq. Curiosamente, notar um desempenho significativamente degradada pelo uso lazyZipon Array.

Você deve sempre ter cuidado com a medição de desempenho por causa da compilação JIT, mas um motivo provável é que isso zippedé preguiçoso e extrai elementos dos Arrayvaules originais durante a mapchamada, enquanto zipcria um novo Arrayobjeto e depois chama mapo novo objeto.