Dlaczego zip jest szybszy niż zip w Scali?

Napisałem kod Scali, aby wykonać elementową operację na kolekcji. Tutaj zdefiniowałem dwie metody, które wykonują to samo zadanie. Jedna metoda wykorzystuje, zipa druga wykorzystuje 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)

Aby porównać te dwie metody pod względem prędkości, napisałem następujący kod:

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

Wywołuję funmetodę i przekazuję ESi ES1jak poniżej:

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)

Wyniki pokazują, że metoda, ES1która używa, zippedjest szybsza niż metoda, ESktóra używa zip. Na podstawie tych obserwacji mam dwa pytania.

Dlaczego jest zippedszybszy niż zip?

Czy istnieje jeszcze szybszy sposób wykonywania elementarnych operacji na kolekcji w Scali?

Aby odpowiedzieć na drugie pytanie:

Czy jest jakiś szybszy sposób na mądre działanie elementu na kolekcji w Scali?

Smutna prawda jest taka, że ​​pomimo zwięzłości, zwiększonej produktywności i odporności na błędy, języki funkcjonalne niekoniecznie są najbardziej wydajne - użycie funkcji wyższego rzędu do zdefiniowania projekcji, która ma być wykonana na kolekcjach, które nie są wolne, a twoja wąska pętla podkreśla to. Jak zauważyli inni, dodatkowy przydział pamięci dla wyników pośrednich i końcowych również będzie miał narzut.

Jeśli wydajność ma kluczowe znaczenie, choć nie jest uniwersalna, w takich przypadkach jak twoje możesz cofnąć operacje Scali z powrotem do bezwzględnych odpowiedników, aby odzyskać bardziej bezpośrednią kontrolę nad wykorzystaniem pamięci i wyeliminować wywołania funkcji.

W konkretnym przykładzie zippedsumy można wykonać imperatywnie, wstępnie przydzielając stałą, zmienną tablicę o prawidłowym rozmiarze (ponieważ zip zatrzymuje się, gdy w jednej z kolekcji zabraknie elementów), a następnie dodając elementy o odpowiednim indeksie razem (od momentu uzyskania dostępu elementy tablic według indeksu porządkowego to bardzo szybka operacja).

Dodanie trzeciej funkcji ES3do zestawu testów:

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
}

Na moim i7 otrzymuję następujące czasy odpowiedzi:

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

Jeszcze bardziej haniebne byłoby dokonanie bezpośredniej mutacji w miejscu krótszej z dwóch tablic, co oczywiście zniszczyłoby zawartość jednej z tablic, i byłoby to zrobione tylko wtedy, gdyby pierwotna tablica ponownie nie była potrzebna:

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

Ale oczywiście bezpośrednia mutacja elementów tablicy nie jest w duchu Scali.

Żadna z pozostałych odpowiedzi nie wspomina o głównej przyczynie różnicy prędkości, która polega na tym, że zippedwersja unika 10.000 alokacji krotek. Jak kilka innych odpowiedzi zrobić noty, zipwersja obejmuje pośrednią tablicę, natomiast zippedwersja nie robi, ale przydzielanie tablicę do 10000 elementów nie jest to, co sprawia, że zipwersja o wiele gorsze jest to 10,000 krótkotrwałe krotki że są umieszczane w tej tablicy. Są one reprezentowane przez obiekty w JVM, więc wykonujesz kilka przydziałów obiektów dla rzeczy, które natychmiast zamierzasz wyrzucić.

Reszta tej odpowiedzi zawiera tylko trochę więcej szczegółów na temat tego, jak możesz to potwierdzić.

Lepsze testy porównawcze

Naprawdę chcesz używać frameworku, takiego jak jmh, do odpowiedzialnego testowania wydajności w JVM, a nawet wtedy odpowiedzialna część jest trudna, chociaż samo skonfigurowanie jmh nie jest takie złe. Jeśli masz coś project/plugins.sbttakiego:

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

I build.sbtpodobne (używam 2.11.8, ponieważ wspominasz, że tego właśnie używasz):

scalaVersion := "2.11.8"

enablePlugins(JmhPlugin)

Następnie możesz napisać swój test porównawczy w następujący sposób:

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

I uruchom z 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

Co pokazuje, że zippedwersja uzyskuje około 80% większą przepustowość, co prawdopodobnie jest mniej więcej takie samo jak twoje pomiary.

Pomiar przydziałów

Możesz także poprosić jmh o pomiar przydziałów za pomocą -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

… Gdzie gc.alloc.rate.normjest prawdopodobnie najciekawsza część, pokazująca, że zipwersja przydziela ponad trzy razy więcej zipped.

Konieczne wdrożenia

Gdybym wiedział, że ta metoda będzie wywoływana w kontekstach bardzo wrażliwych na wydajność, prawdopodobnie zastosowałbym ją w następujący sposób:

  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
  }

Zauważ, że w przeciwieństwie do wersji zoptymalizowanej w jednej z pozostałych odpowiedzi, ta funkcja jest używana whilezamiast, forponieważ fornadal będzie się przełączać do operacji kolekcji Scala. Możemy porównać tę implementację ( withWhile), zoptymalizowaną (ale nie na miejscu) implementację drugiej odpowiedzi ( withFor) oraz dwie oryginalne implementacje:

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

To naprawdę ogromna różnica między wersjami imperatywną i funkcjonalną, a wszystkie sygnatury metod są dokładnie identyczne, a implementacje mają tę samą semantykę. To nie jest tak, że implementacje imperatywne używają stanu globalnego itp. Chociaż wersje zipi zippedsą bardziej czytelne, osobiście nie sądzę, by istniał sens, w którym wersje imperatywne są sprzeczne z „duchem Scali”, i nie zawahałbym się korzystać z nich osobiście.

Z tabelą

Aktualizacja: Dodałem tabulateimplementację do testu porównawczego na podstawie komentarza w innej odpowiedzi:

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

Jest znacznie szybszy niż zipwersje, choć wciąż znacznie wolniejszy niż te niezbędne:

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

Tego się spodziewałem, ponieważ wywoływanie funkcji nie jest z natury drogie, a dostęp do elementów tablicy za pomocą indeksu jest bardzo tani.

Rozważać lazyZip

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

zamiast zip

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

Scala 2.13 dodana lazyZip na korzyść.zipped

Wraz z .zipwidokami zastępuje .zipped(obecnie przestarzałe). ( scala / collection-strawman # 223 )

zipped(i stąd lazyZip) jest szybszy niż zipdlatego, że, jak wyjaśnili Tim i Mike Allen , zipnastępna mapspowoduje dwie osobne transformacje ze względu na ścisłość, a zippednastępnie mapspowoduje pojedynczą transformację wykonaną za jednym razem z powodu lenistwa.

zippeddaje Tuple2Zipped, i analizowanie 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()
  }

widzimy dwie kolekcje coll1i coll2są iterowane, a po każdej iteracji fprzekazywana funkcja mapjest stosowana po drodze

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

bez konieczności przydzielania i przekształcania struktur pośrednich.

Stosując metodę testu porównawczego Travisa, oto porównanie między nowym lazyZipa przestarzałym zippedgdzie

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

daje

[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

lazyZipwydaje się działać nieco lepiej niż zippedna ArraySeq. Co ciekawe, zauważy znacznie pogorszeniu podczas używania lazyZipna Array.

Zawsze powinieneś być ostrożny przy pomiarze wydajności ze względu na kompilację JIT, ale prawdopodobnie przyczyną jest zippedlenistwo i Arraywyciąganie elementów z oryginalnych vaules podczas mappołączenia, podczas gdy ziptworzy nowy Arrayobiekt, a następnie wywołuje mapnowy obiekt.