Mengapa zip lebih cepat daripada zip di Scala?

38

Saya telah menulis beberapa kode Scala untuk melakukan operasi elemen-bijaksana pada koleksi. Di sini saya mendefinisikan dua metode yang melakukan tugas yang sama. Satu metode menggunakan zipdan yang lainnya menggunakan 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)

Untuk membandingkan kedua metode ini dalam hal kecepatan, saya menulis kode berikut:

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

Saya memanggil funmetode dan lulus ESdan ES1seperti di bawah ini:

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)

Hasil menunjukkan bahwa metode bernama ES1yang menggunakan zippedlebih cepat daripada metode ESyang digunakan zip. Berdasarkan pengamatan ini, saya punya dua pertanyaan.

Kenapa zippedlebih cepat dari itu zip?

Apakah ada cara yang lebih cepat untuk melakukan operasi elemen pada koleksi di Scala?

pengguna12140540
sumber
2
Pertanyaan terkait: stackoverflow.com/questions/59125910/…
Mario Galic
8
Karena JIT memutuskan untuk mengoptimalkan secara lebih agresif pada kali kedua ia melihat 'kesenangan' sedang digunakan. Atau karena GC memutuskan untuk membersihkan sesuatu ketika ES sedang berjalan. Atau karena sistem operasi Anda memutuskan bahwa ada hal-hal yang lebih baik untuk dilakukan ketika tes ES Anda berjalan. Bisa apa saja, microbenchmark ini tidak konklusif.
Andrey Tyukin
1
Apa hasil pada mesin Anda? Seberapa cepat?
Peeyush Kushwaha
Untuk ukuran dan konfigurasi populasi yang sama, Zip mengambil 32 detik sementara Zip mengambil 44 detik
user12140540
3
Hasil Anda tidak ada artinya. Gunakan JMH jika Anda harus melakukan tolok ukur mikro.
OrangeDog

Jawaban:

17

Untuk menjawab pertanyaan kedua Anda:

Apakah ada cara yang lebih cepat untuk melakukan operasi elemen pada koleksi di Scala?

Kebenaran yang menyedihkan adalah bahwa meskipun memiliki keringkasan, peningkatan produktivitas, dan ketahanan terhadap bug yang bahasa fungsional belum tentu paling berkinerja tinggi - menggunakan fungsi urutan yang lebih tinggi untuk menentukan proyeksi yang akan dijalankan terhadap koleksi yang tidak gratis, dan loop ketat Anda menyoroti ini. Seperti yang telah ditunjukkan orang lain, alokasi penyimpanan tambahan untuk hasil antara dan akhir juga akan memiliki overhead.

Jika kinerja sangat penting, meskipun tidak berarti universal, dalam kasus seperti milik Anda, Anda dapat melepas operasi Scala menjadi setara dengan imperatif untuk mendapatkan kembali kendali langsung atas penggunaan memori dan menghilangkan panggilan fungsi.

Dalam contoh spesifik Anda, zippedjumlah dapat dilakukan secara imperatif dengan mengalokasikan sebelumnya, array yang dapat diubah yang dapat diubah ukurannya (karena zip berhenti ketika salah satu koleksi kehabisan elemen), dan kemudian menambahkan elemen pada indeks yang sesuai bersama-sama (sejak mengakses elemen array dengan indeks ordinal adalah operasi yang sangat cepat).

Menambahkan fungsi ketiga, ES3ke suite pengujian Anda:

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
}

Pada i7 saya, saya mendapatkan waktu respons berikut:

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

Bahkan yang lebih kejam adalah melakukan mutasi langsung di tempat yang lebih pendek dari dua array, yang jelas akan merusak isi dari salah satu array, dan hanya akan dilakukan jika array asli lagi tidak diperlukan:

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

Tapi jelas, mutasi elemen array langsung tidak dalam semangat Scala.

StuartLC
sumber
2
Tidak ada yang diparalelkan dalam kode saya di atas. Meskipun masalah khusus ini dapat diparalelkan (karena beberapa utas dapat bekerja pada bagian array yang berbeda), tidak akan ada banyak gunanya dalam operasi sederhana seperti ini hanya pada elemen 10k - overhead pembuatan dan sinkronisasi utas baru kemungkinan akan lebih besar daripada manfaatnya . Sejujurnya, jika Anda memerlukan tingkat optimasi kinerja ini, Anda mungkin lebih baik menulis algoritma semacam ini di Rust, Go atau C.
StuartLC
3
Akan lebih seperti skala dan lebih cepat digunakan Array.tabulate(minSize)(i => arr(i) + arr1(i))untuk membuat array Anda
Sarvesh Kumar Singh
1
@SarveshKumarSingh ini jauh lebih lambat. Membutuhkan waktu hampir 9 detik
user12140540
1
Array.tabulateharus jauh lebih cepat daripada salah satu zipatau di zippedsini (dan ada di tolok ukur saya).
Travis Brown
1
@StuartLC "Kinerja hanya akan setara jika fungsi urutan yang lebih tinggi entah bagaimana dibuka dan diuraikan." Ini tidak terlalu akurat. Bahkan Anda foringin panggilan fungsi tingkat tinggi ( foreach). Lambda hanya akan dipakai satu kali dalam kedua kasus.
Travis Brown
50

Tidak ada jawaban lain yang menyebutkan alasan utama perbedaan kecepatan, yaitu zippedversi menghindari 10.000 alokasi tuple. Sebagai beberapa jawaban yang lain melakukan catatan, zipversi melibatkan array menengah, sedangkan zippedversi tidak, tapi mengalokasikan sebuah array untuk 10.000 elemen tidak apa yang membuat zipversi jauh lebih buruk-itu 10.000 tupel berumur pendek yang sedang dimasukkan ke dalam array itu. Ini diwakili oleh objek pada JVM, jadi Anda melakukan banyak alokasi objek untuk hal-hal yang akan segera Anda buang.

Sisa dari jawaban ini hanya menjelaskan sedikit lebih detail tentang bagaimana Anda dapat mengonfirmasi hal ini.

Pembandingan yang lebih baik

Anda benar-benar ingin menggunakan kerangka kerja seperti jmh untuk melakukan pembandingan apa pun secara bertanggung jawab pada JVM, dan bahkan bagian yang bertanggung jawab itu sulit, meskipun mengatur jmh itu sendiri tidak terlalu buruk. Jika Anda memiliki yang project/plugins.sbtseperti ini:

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

Dan build.sbtseperti ini (saya menggunakan 2.11.8 karena Anda menyebutkan itu yang Anda gunakan):

scalaVersion := "2.11.8"

enablePlugins(JmhPlugin)

Maka Anda dapat menulis patokan Anda seperti ini:

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

Dan jalankan dengan 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

Yang menunjukkan bahwa zippedversi tersebut mendapatkan throughput sekitar 80% lebih banyak, yang mungkin kurang lebih sama dengan pengukuran Anda.

Mengukur alokasi

Anda juga dapat meminta jmh untuk mengukur alokasi dengan -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

... di mana gc.alloc.rate.normmungkin bagian yang paling menarik, menunjukkan bahwa zipversi tersebut mengalokasikan lebih dari tiga kali lipat zipped.

Implementasi imperatif

Jika saya tahu bahwa metode ini akan dipanggil dalam konteks yang sangat sensitif terhadap kinerja, saya mungkin akan menerapkannya seperti ini:

  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
  }

Perhatikan bahwa tidak seperti versi yang dioptimalkan dalam salah satu jawaban lain, ini menggunakan whilealih-alih forkarena forakan tetap masuk ke operasi koleksi Scala. Kita dapat membandingkan implementasi ini ( withWhile), implementasi yang lain dioptimalkan (tetapi bukan di tempat) ( withFor), dan dua implementasi asli:

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

Itu perbedaan yang sangat besar antara versi imperatif dan fungsional, dan semua tanda tangan metode ini persis identik dan implementasinya memiliki semantik yang sama. Ini tidak seperti implementasi imperatif menggunakan negara global, dll. Sementara zipdan zippedversi lebih mudah dibaca, saya pribadi tidak berpikir ada arti di mana versi imperatif menentang "semangat Scala", dan saya tidak akan ragu untuk menggunakannya sendiri.

Dengan tabulasi

Pembaruan: Saya menambahkan tabulateimplementasi ke tolok ukur berdasarkan komentar di jawaban lain:

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

Ini jauh lebih cepat daripada zipversi, meskipun masih jauh lebih lambat daripada versi imperatif:

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

Inilah yang saya harapkan, karena tidak ada yang secara inheren mahal untuk memanggil fungsi, dan karena mengakses elemen array dengan indeks sangat murah.

Travis Brown
sumber
8

Mempertimbangkan lazyZip

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

dari pada zip

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

Scala 2.13 ditambahkan lazyZip untuk mendukung.zipped

Bersama dengan .zippada pandangan, ini menggantikan .zipped(sekarang sudah usang). ( scala / koleksi-strawman # 223 )

zipped(dan karenanya lazyZip) lebih cepat daripada zipkarena, seperti yang dijelaskan oleh Tim dan Mike Allen , zipdiikuti oleh mapakan menghasilkan dua transformasi terpisah karena ketatnya, sementara zippeddiikuti oleh mapakan menghasilkan satu transformasi yang dijalankan dalam sekali jalan karena kemalasan.

zippedmemberi Tuple2Zipped, dan menganalisis 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()
  }

kita melihat dua koleksi coll1dan coll2diiterasi berulang dan pada setiap iterasi fungsi fdilewatkan untuk mapditerapkan di sepanjang jalan

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

tanpa harus mengalokasikan dan mengubah struktur perantara.


Menerapkan Travis' metode benchmarking, di sini adalah perbandingan antara baru lazyZipdan ditinggalkan zippeddi mana

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

memberi

[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

lazyZiptampaknya melakukan sedikit lebih baik daripada zippeddi ArraySeq. Menariknya, melihat kinerja terdegradasi secara signifikan ketika menggunakan lazyZippada Array.

Mario Galic
sumber
lazyZip tersedia di Scala 2.13.1. Saat ini saya menggunakan Scala 2.11.8
user12140540
5

Anda harus selalu berhati-hati dengan pengukuran kinerja karena kompilasi JIT, tetapi kemungkinan alasannya adalah karena zippedmalas dan mengekstrak elemen dari Arrayvaules asli selama mappanggilan, sedangkan zipmembuat Arrayobjek baru dan kemudian memanggil mapobjek baru.

Tim
sumber