为什么Scala中的“for循环推导式”与FOR循环相比非常缓慢？

Question

据说Scala的For comprehensions实际上非常慢。我得到的原因是由于Java的限制，for comprehensions（如下面使用的“reduce”）需要在每次迭代中生成一个临时对象才能调用传递进来的函数。

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

这对于“lambdas”或匿名函数可能是有道理的，但对于非匿名函数则不然。

在我的测试中，我对比了使用list.reduce的for循环（见下面的代码），即使每次迭代调用的是传递给reduce的完全相同的函数，它们也要快两倍以上！

我觉得这非常反直觉（人们可能认为Scala库应该被精心创建以尽可能地优化）。

在我编写的一个测试中，我以五种不同的方式运行了同一个循环（将数字1到一百万相加，无论是否溢出）：

1. for循环遍历值数组 2. for循环，但调用函数而不是内联算术 3. for循环，创建一个包含加法函数的对象 4. list.reduce，传递i一个匿名函数 5. 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))
                    }
         ...
}

- Mark Gerolimatos

---

.reduce与“for comprehensions”无关。 - Nikita Volkov

顺便提一下，有一个 Scala 编译器插件旨在消除常见情况下的开销：https://code.google.com/p/scalacl/wiki/ScalaCLPlugin。不过我自己还没有尝试过。 - Régis Jean-Gilles

实际上，你的前三个测试正在使用for-comprehensions，而你正在将这些与reduce的时间进行比较。 - Richard Sitze

@RégisJean-Gilles :: ScalaCL 旨在（回到 Scala 2.9）为 OpenCL 生成代码，即可在 GPU 上运行。特别是，您还可以告诉它执行任务，但生成 CPU 而不是 GPU 的代码。它的工作非常出色，但不幸的是，它主要基于宏，在 Scala 中是一个不断变化的目标，从版本到版本不同。ScalaCL 在最近的 Scala 版本中不可用。 - Richard Gomes

好的，当我写下那个评论时，scala 2.10 刚刚发布。而 scalaCL 被明确地宣传为一种加速循环的方法（除了其 OpenCL 的能力之外）。我引用一下：「它还经常通过很大的优势来优化普通的 Scala 循环（在数组、列表和内联范围上），所以即使你不关心 OpenCL，你也会想使用它。」顺便说一句，它是/曾经是一个编译器插件，而不是一组宏（尽管我认为这是一个无关紧要的问题，因为它更依赖于实现细节，因此更加不可靠）。 - Régis Jean-Gilles

Answer 1

你听到的"for comprehensions"的说法是正确的，但你的问题在于把"for comprehensions"和"anonymous functions"混淆了。

在Scala中，"for comprehension"是一系列.flatMap、.map和.filter应用的语法糖。由于你正在测试缩减算法，而使用这三个函数无法实现缩减算法，因此你的测试用例是不正确的。

这是一个"for comprehension"的示例：

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

编译器将推导部分简化为以下内容：

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

从解糖后的代码可以明显看出，每次调用apply(itemOfListOfLists: List[Int]): List[Int]方法时，Function1[Int, Int]类都会被实例化。这发生在listOfLists的每个条目中。因此，您的综合越复杂，您将获得更多Function对象的实例。

- Nikita Volkov