为什么在Scala中使用zipped比zip更快？

Question

我用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)

结果表明，使用zipped的名为ES1的方法比使用zip的方法ES更快。 基于这些观察结果，我有两个问题。

为什么zipped比zip更快？

在Scala中，是否有更快的方式对集合进行逐元素操作？

- Asif

---

相关问题：https://dev59.com/Wrfna4cB1Zd3GeqPztSI - Mario Galic

因为JIT决定第二次调用“fun”时更积极地进行优化。或者因为GC在ES运行时决定清理一些内容。或者因为您的操作系统在运行ES测试时决定有更重要的任务要处理。可能是任何原因，这个微基准测试并不具有决定性。 - Andrey Tyukin

你的机器上有什么结果？快了多少？ - Peeyush Kushwaha

对于相同的人口规模和配置，Zipped 花费了 32 秒，而 Zip 花费了 44 秒。 - Asif

如果你必须进行微基准测试，请使用[JMH]（https://openjdk.java.net/projects/code-tools/jmh/），因为你的结果毫无意义。 - OrangeDog

Answer 1

没有其他答案提到速度差异的主要原因，即zipped版本避免了10,000个元组分配。正如其他答案中所指出的，zip版本涉及一个中间数组，而zipped版本则不涉及，但是为10,000个元素分配一个数组并不是使zip版本变得更糟糕的原因——而是被放入该数组中的10,000个短暂元组。这些在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

这表明使用压缩版本可以获得大约80%的吞吐量，这可能与你的测量结果差不多。

测量分配也可以通过-prof gc命令来请求jmh进行。

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： 更新：根据另一个答案中的评论，我添加了一个基于 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

这正是我所期望的，因为调用函数本身并不会很耗费资源，而通过索引访问数组元素也非常便宜。

- Travis Brown

Answer 2

回答你的第二个问题：

在Scala中是否有更快的方法来对集合进行逐元素操作？

不幸的是，尽管函数式语言具有简洁性、提高生产力和抗错误性等优点，但它们并不一定是最高效的。在OP的例子中，使用高阶函数定义要对集合执行的投影会产生开销，并且紧密的循环会放大这种开销。正如其他人指出的那样，中间和最终结果的额外存储分配也会有开销。

如果性能至关重要，则可以将简洁的函数式代码展开成等效的命令式代码，以便重新获得对内存使用的更直接控制并消除函数调用开销，尽管这种情况并不普遍。

在您特定的示例中，可以通过预先分配正确大小的固定可变数组来以命令式的方式执行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的设计理念——这段代码带有副作用的味道。

老实说，如果你需要在紧密循环中进行这种程度的性能优化，最好使用Rust、Go或C来编写这些算法。

- StuartLC

---

上面的代码中没有任何并行化。虽然这个特定的问题是可并行化的（因为多个线程可以在数组的不同部分上工作），但在仅有10k元素的情况下进行如此简单的操作可能没有太大意义——创建和同步新线程的开销很可能会超过任何好处。说实话，如果您需要这种级别的性能优化，最好使用Rust、Go或C编写这些类型的算法。 - StuartLC

使用Array.tabulate(minSize)(i => arr(i) + arr1(i))创建数组更加类似于Scala，并且速度更快。 - sarveshseri

@SarveshKumarSingh 这个速度慢多了，几乎需要9秒钟。 - Asif

Array.tabulate 在这里应该比 zip 或 zipped 快得多（在我的基准测试中是如此）。 - Travis Brown

@StuartLC “只有在某种程度上解包和内联高阶函数时，性能才会相当。” 这并不完全准确。即使是您的 for 循环也会被转换为高阶函数调用（foreach）。在两种情况下，lambda 表达式只会被实例化一次。 - Travis Brown

Answer 3

考虑使用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/collection-strawman #223）

zipped （因此lazyZip）比zip 更快，因为正如Tim和Mike Allen所解释的那样，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被遍历，并且在每次迭代中，传递给map的函数f也会被应用。

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

可以不需要分配和转换中间结构。

---

应用Travis的基准测试方法，这里是新的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 在 ArraySeq 上的表现似乎比 zipped 更好。有趣的是，当在 Array 上使用 lazyZip 时，性能显著下降。

- Mario Galic

---

lazyZip 可在 Scala 2.13.1 中使用。目前我正在使用 Scala 2.11.8。 - Asif

Answer 4

由于JIT编译，性能测量应始终谨慎。但可能的原因是，zipped是惰性求值，在map调用期间从原始Array值中提取元素，而zip创建一个新的Array对象，然后在该新对象上调用map。

- Tim