performance - 为什么 Scala "for loop comprehensions"与 FOR 循环相比非常慢？

Question

有人说 Scala For comprehensions 实际上很慢。我得到的原因是，由于 Java 的限制，对于推导式(例如下面使用的“reduce”)需要在每次迭代时生成一个临时对象，以便调用传入的函数。

这是真的？下面的测试似乎证实了这一点，但我不完全理解为什么会这样。

这对于“lambdas”或匿名函数可能有意义，但对于非匿名函数则不然。

在我的测试中，我针对 list.reduce 运行了 for 循环(参见下面的代码)，发现它们的速度提高了两倍多，即使每次迭代调用传递给 reduce 的完全相同的函数时也是如此!

我发现这非常违反直觉(曾经认为 Scala 库会被精心创建以尽可能优化)。

在我放在一起的测试中，我以五种不同的方式运行了相同的循环(将数字 1 加到一百万，不考虑溢出):

for 循环值数组

for 循环，但调用函数而不是内联算术

for 循环，创建一个包含加法函数的对象

list.reduce，传递给我一个匿名函数

list.reduce，传入一个对象成员函数

结果如下:
测试:最小/最大/平均值(毫秒)

1. 27/157/64.78
2. 27/192/65.77 <--- note the similarity between tests 1,2 and 4,5
3. 139/313/202.58
4. 63/342/150.18
5. 63/341/149.99

可以看出，“for comprehension”版本的顺序是“for with new for each instance”，这意味着实际上可以为匿名和非匿名函数版本执行“new”。

方法:下面的代码(删除了测试调用)被编译成一个单一的 .jar 文件，以确保所有版本运行相同的库代码。每次迭代中的每个测试都在新的 JVM 中调用(即每个测试的 scala -cp ...)，以消除堆大小问题。

class t(val i: Int) {
    def summit(j: Int) = j + i
}

object bar {
    val biglist:List[Int]  =  (1 to 1000000).toList

    def summit(i: Int, j:Int) = i+j

    // Simple for loop
    def forloop:  Int = {
        var result: Int = 0
        for(i <- biglist) {
            result += i
        }
        result
    }

    // For loop with a function instead of inline math
    def forloop2:  Int = {
        var result: Int = 0
        for(i <- biglist) {
            result = summit(result,i)
        }
        result
    }

    // for loop with a generated object PER iteration
    def forloop3: Int = {
        var result: Int = 0
        for(i <- biglist) {
            val t = new t(result)
            result = t.summit(i)
        }
        result
    }

    // list.reduce with an anonymous function passed in
    def anonymousfunc: Int = {
        biglist.reduce((i,j) => {i+j})
    }

    // list.reduce with a named function
    def realfunc: Int = {
        biglist.reduce(summit)
    }

    // test calling code excised for brevity. One example given:
    args(0) match {
        case "1" => {
                    val start = System.currentTimeMillis()
                    forloop
                    val end = System.currentTimeMillis()
                    println("for="+(end - start))
                    }
         ...
}

Answer 1

你被告知关于“for comprehensions”的说法是正确的，但你的问题的问题是你把“for comprehensions”与“匿名函数”混为一谈。

Scala 中的“For comprehension”是一系列 .flatMap 的语法糖。 , .map和 .filter应用程序。由于您正在测试归约算法，并且不可能使用这三个函数来实现归约算法，因此您的测试用例是不正确的。

这是一个“理解”的例子:

val listOfLists = List(List(1,2), List(3,4), List(5))
val result = 
  for {
    itemOfListOfLists <- listOfLists
    itemOfItemOfListOfLists <- itemOfListOfLists
  }
  yield (itemOfItemOfListOfLists + 1)
assert( result == List(2,3,4,5,6) )

编译器将 Comprehension 部分脱糖为以下内容:

val result =
  listOfLists.flatMap(
    itemOfListOfLists => itemOfListOfLists.map(
      itemOfItemOfListOfLists => itemOfItemOfListOfLists + 1
    )
  )

然后它对匿名函数语法进行脱糖:

val result =
  listOfLists.flatMap(
    new Function1[List[Int], List[Int]] {
      override def apply(itemOfListOfLists: List[Int]): List[Int] =
        itemOfListOfLists.map(
          new Function1[Int, Int] {
            override def apply(itemOfItemOfListOfLists: Int): Int =
              itemOfItemOfListOfLists + 1
          }
        )
    }
  )

从脱糖代码现在很明显 Function1[Int, Int]每次 apply(itemOfListOfLists: List[Int]): List[Int] 都会实例化类方法被调用。对于 listOfLists 的每个条目都会发生这种情况.因此，您的理解越复杂， Function 的实例化就越多。你得到的对象。