Почему в Scala архивируется быстрее, чем zip?
Я написал код Scala для выполнения поэлементной операции с коллекцией. Здесь я определил два метода, которые выполняют одну и ту же задачу. Один метод используетzip и другие виды использования 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)
Чтобы сравнить эти два метода по скорости, я написал следующий код:
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")
}
Я звоню fun метод и пройти ES а также ES1 как показано ниже:
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)
Результаты показывают, что названный метод ES1 который использует zipped быстрее, чем метод ES который использует zip. На основании этих наблюдений у меня есть два вопроса.
Почему zipped быстрее, чем zip?
Есть ли еще более быстрый способ выполнять поэлементные операции с коллекцией в Scala?
4 ответа
Чтобы ответить на ваш второй вопрос:
Есть ли более быстрый способ выполнить поэлементную операцию с коллекцией в Scala?
Печальная правда заключается в том, что, несмотря на лаконичность, повышенную производительность и устойчивость к ошибкам, функциональные языки не обязательно являются наиболее производительными - использование функций более высокого порядка для определения проекции, которая будет выполняться против коллекций, не является бесплатным, и ваш жесткий цикл подчеркивает это. Как указывали другие, дополнительное выделение памяти для промежуточных и конечных результатов также будет иметь накладные расходы.
Если производительность имеет решающее значение, хотя отнюдь не универсально, в таких случаях, как ваш, вы можете свернуть операции Scala обратно в императивные эквиваленты, чтобы восстановить более прямой контроль над использованием памяти и исключить вызовы функций.
В вашем конкретном примере zipped суммы могут быть выполнены императивно путем предварительного выделения фиксированного изменяемого массива правильного размера (поскольку zip останавливается, когда в одной из коллекций заканчиваются элементы), а затем добавления элементов по соответствующему индексу вместе (поскольку доступ к элементам массива по порядковому индексу является очень быстрая операция).
Добавляем третью функцию, ES3 в ваш набор тестов:
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
}
На моем i7 я получаю следующее время отклика:
OP ES Total Time Consumed:23.3747857Seconds
OP ES1 Total Time Consumed:11.7506995Seconds
--
ES3 Total Time Consumed:1.0255231Seconds
Еще более отвратительным было бы выполнить прямую мутацию на месте более короткого из двух массивов, что, очевидно, повредило бы содержимое одного из массивов и было бы сделано только в том случае, если исходный массив снова не понадобится:
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
Но очевидно, что прямая мутация элементов массива не в духе Scala.
Ни в одном из других ответов не упоминается основная причина разницы в скорости, заключающаяся в том, что zippedверсия позволяет избежать 10000 распределений кортежей. Как пара других ответов делать заметки оzip версия включает промежуточный массив, в то время как zipped версии нет, но выделение массива для 10000 элементов - не то, что делает zipверсия намного хуже - это 10000 короткоживущих кортежей, которые помещаются в этот массив. Они представлены объектами на JVM, поэтому вы делаете кучу выделения объектов для вещей, которые сразу же выбросите.
Остальная часть этого ответа просто дает немного больше информации о том, как вы можете это подтвердить.
Лучшее тестирование
Вы действительно хотите использовать фреймворк, такой как jmh, для ответственного тестирования JVM любого типа, и даже в этом случае ответственная часть сложна, хотя сама настройка jmh не так уж и плоха. Если у тебя естьproject/plugins.sbt нравится:
addSbtPlugin("pl.project13.scala" % "sbt-jmh" % "0.3.7")
И build.sbt вот так (я использую 2.11.8, поскольку вы упомянули, что вы используете):
scalaVersion := "2.11.8"
enablePlugins(JmhPlugin)
Тогда вы можете написать свой тест следующим образом:
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)
}
И запустите его с 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
Это показывает, что zipped версия получает примерно на 80% больше пропускной способности, что, вероятно, более или менее соответствует вашим измерениям.
Измерение распределения
Вы также можете попросить jmh измерить распределение с помощью -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
…где gc.alloc.rate.norm наверное, самая интересная часть, показывающая, что zip версия выделяет в три раза больше, чем zipped.
Императивные реализации
Если бы я знал, что этот метод будет вызываться в контексте, чрезвычайно чувствительном к производительности, я бы, вероятно, реализовал его следующим образом:
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
}
Обратите внимание, что в отличие от оптимизированной версии в одном из других ответов, здесь используется while вместо for так как forпо-прежнему будет десахариваться в операции коллекций Scala. Мы можем сравнить эту реализацию (withWhile), оптимизированная (но не на месте) реализация другого ответа (withFor), и две оригинальные реализации:
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
Это действительно огромная разница между императивной и функциональной версиями, и все эти сигнатуры методов полностью идентичны, а реализации имеют одинаковую семантику. Это не похоже на то, что императивные реализации используют глобальное состояние и т.д.zip а также zipped версии более читабельны, я лично не думаю, что императивные версии противоречат "духу Scala", и я без колебаний использую их сам.
С таблицей
Обновление: я добавил tabulate реализация теста на основе комментария в другом ответе:
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))
}
Это намного быстрее, чем zip версии, хотя и намного медленнее императивных:
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
Это то, чего я ожидал, поскольку в вызове функции нет ничего дорогого по своей сути, и потому что доступ к элементам массива по индексу очень дешев.
Рассмотреть возможность lazyZip
(as lazyZip bs) map { case (a, b) => a + b }
вместо того zip
(as zip bs) map { case (a, b) => a + b }
Добавлен Scala 2.13 lazyZip в пользу .zipped
Вместе с
.zipпо просмотрам, это заменяет.zipped(теперь не рекомендуется). ( Scala / коллекция-соломенный № 223)
zipped (и поэтому lazyZip) быстрее, чем zipпотому что, как объяснили Тим и Майк Аллен,zip с последующим map приведет к двум отдельным преобразованиям из-за строгости, в то время как zipped с последующим map приведет к единственному преобразованию, выполненному за один раз из-за лени.
zipped дает Tuple2Zipped, и анализируя 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()
}
мы видим две коллекции coll1 а также coll2 повторяются снова, и на каждой итерации функция f перешел к map применяется по ходу
b += f(elems1.next(), elems2.next())
без необходимости выделять и трансформировать промежуточные структуры.
Применяя метод сравнительного анализа Трэвиса, вот сравнение новых lazyZip и устарел zipped где
@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)
}
дает
[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
lazyZip кажется, работает немного лучше, чем zipped на ArraySeq. Интересно отметить, что производительность значительно снизилась при использованииlazyZip на Array.
Вы всегда должны быть осторожны с измерением производительности из-за JIT-компиляции, но вероятная причина в том, что zipped ленив и извлекает элементы из оригинала Array vaules во время map звоните, тогда как zip создает новый Array объект, а затем вызывает map на новом объекте.