如何在 Scala 中优化 for-understand 和循环？

所以 Scala 应该和 Java 一样快。我正在重温 Scala 中的一些 欧拉计划问题，这些问题最初是在 Java 中解决的。具体的问题5: “什么是最小的正数是均匀整除的所有数字从1到20?”

这是我的 Java 解决方案，在我的机器上完成需要0.7秒:

public class P005_evenly_divisible implements Runnable{
final int t = 20;


public void run() {
int i = 10;
while(!isEvenlyDivisible(i, t)){
i += 2;
}
System.out.println(i);
}


boolean isEvenlyDivisible(int a, int b){
for (int i = 2; i <= b; i++) {
if (a % i != 0)
return false;
}
return true;
}


public static void main(String[] args) {
new P005_evenly_divisible().run();
}
}

下面是我对 Scala 的“直接翻译”，它需要103秒(147倍的时间!)

object P005_JavaStyle {
val t:Int = 20;
def run {
var i = 10
while(!isEvenlyDivisible(i,t))
i += 2
println(i)
}
def isEvenlyDivisible(a:Int, b:Int):Boolean = {
for (i <- 2 to b)
if (a % i != 0)
return false
return true
}
def main(args : Array[String]) {
run
}
}

最后是函数式编程的尝试，它需要39秒(55倍长)

object P005 extends App{
def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}
def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
println (find (2))
}

在 Windows 764位上使用 Scala 2.9.0.1。如何提高性能？我做错什么了吗？还是 Java 更快？

20494 次浏览
小开

问题很可能是在方法 isEvenlyDivisible中使用了 for理解。用等效的 while循环代替 for应该可以消除与 Java 的性能差异。

与 Java 的 for循环不同，Scala 的 for理解实际上是高阶方法的语法糖; 在本例中，您在 Range对象上调用 foreach方法。Scala 的 for非常普遍，但有时会导致令人痛苦的性能。

您可能想尝试 Scala 2.9版本中的 -optimize标志。观察到的性能可能取决于所使用的特定 JVM，以及 JIT 优化器有足够的“预热”时间来识别和优化热点。

最近关于邮件列表的讨论表明，Scala 团队正致力于在简单情况下提高 for的性能:

这就是 bug 追踪器的问题所在: Https://issues.scala-lang.org/browse/si-4633

更新5/28 :

  • 作为一个短期的解决方案，ScalaCL插件(alpha)将把简单的 Scala 循环转换成相当于 while循环的东西。
  • 作为一个潜在的长期解决方案，来自 EPFL 和 Stanford 的团队使用 在一个项目上合作来支持 “虚拟”Scala的运行时编译，以获得非常高的性能。例如，多个惯用函数循环可以将 在运行时融合转换为最佳的 JVM 字节码，或者转换为另一个目标，例如 GPU。该系统是可扩展的，允许用户定义的 DSL 和转换。看看 出版物和斯坦福 课程笔记。初步代码可以在 Github 上找到，预计将在未来几个月发布。
小开

作为后续工作，我尝试使用了-Optimstag，它将运行时间从103秒减少到76秒，但是这仍然比 Java 或 while 循环慢107倍。

然后我看到了“功能性”版本:

object P005 extends App{
def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}
def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
println (find (2))
}

并试图找出如何摆脱“所有”在一个简洁的方式。我悲惨地失败了

object P005_V2 extends App {
def isDivis(x:Int):Boolean = {
var i = 1
while(i <= 20) {
if (x % i != 0) return false
i += 1
}
return true
}
def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
println (find (2))
}

我狡猾的5行解法已经膨胀到12行了。但是，这个版本在 0.71秒中运行，与原来的 Java 版本速度相同，并且比使用“ forall”(40.2 s)的上述版本快56倍！(请参阅下面的 EDIT，了解为什么这比 Java 更快)

显然，我的下一步是将上面的代码转换回 Java，但是 Java 无法处理它，并在大约22000的时候抛出一个带 n 的 StackOverflow Error。

然后我挠了挠头，把“ while”换成了更多的尾递归，这样可以节省几行代码，运行速度也一样快，但是让我们面对现实吧，读起来更让人困惑:

object P005_V3 extends App {
def isDivis(x:Int, i:Int):Boolean =
if(i > 20) true
else if(x % i != 0) false
else isDivis(x, i+1)


def find(n:Int):Int = if (isDivis(n, 2)) n else find (n+2)
println (find (2))
}

所以 Scala 的尾部递归赢得了胜利，但是我很惊讶像“ for”循环(和“ forall”方法)这样简单的东西本质上是被破坏的，必须被不优雅和冗长的“ while”或尾部递归所替代。我尝试使用 Scala 的很多原因是因为它的语法简洁，但是如果我的代码运行速度要慢100倍，那就没有用了！

编辑 : (删除)

编辑编辑 : 以前2.5 s 和0.7 s 的运行时间之间的差异完全是由于使用了32位或64位 JVM。命令行中的 Scala 使用 JAVA _ HOME 设置的任何内容，而 JAVA 使用64位(如果可用的话)。IDE 有自己的设置。这里有一些测量: Scala 在 Eclipse 中的执行时间

小开
最佳答案

在这种特殊情况下，问题在于您从 for-expression 中返回。然后转换为一个 NonLocalReturn nException 抛出，该异常在封闭方法处捕获。优化器可以消除 foreach，但不能消除 throw/catch。而且抛接球很贵。但是由于这样的嵌套返回在 Scala 程序中很少见，所以优化器还没有解决这个问题。正在进行改进优化器的工作，希望能很快解决这个问题。

小开

关于理解的答案是正确的，但这不是整个故事。您应该注意到，在 isEvenlyDivisible中使用 return并不是免费的。在 for中使用 return 会迫使 scala 编译器生成一个非本地的 return (即在函数外部返回)。

这是通过使用异常退出循环来完成的。如果您构建自己的控件抽象，也会发生同样的情况，例如:

def loop[T](times: Int, default: T)(body: ()=>T) : T = {
var count = 0
var result: T = default
while(count < times) {
result = body()
count += 1
}
result
}


def foo() : Int= {
loop(5, 0) {
println("Hi")
return 5
}
}


foo()

这个只能打印一次“嗨”。

请注意，foo中的 return退出 foo(这是您所期望的)。由于括号中的表达式是一个匿名函数，你可以在 loop的签名中看到，这迫使编译器生成一个非本地返回，也就是说，return迫使你退出 foo，而不仅仅是 body。

在 Java (即 JVM)中，实现这种行为的唯一方法是抛出异常。

返回 isEvenlyDivisible:

def isEvenlyDivisible(a:Int, b:Int):Boolean = {
for (i <- 2 to b)
if (a % i != 0) return false
return true
}

if (a % i != 0) return false是一个有返回值的匿名函数，因此每次命中返回值时，运行时都必须抛出并捕获一个异常，这会导致相当多的 GC 开销。

小开

我发现了一些加速 forall方法的方法:

原版: 41.3秒

def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}

预实例化范围，这样我们就不会每次都创建一个新的范围: 9.0秒

val r = (1 to 20)
def isDivis(x:Int) = r forall {x % _ == 0}

转换为 List 而不是 Range: 4.8秒

val rl = (1 to 20).toList
def isDivis(x:Int) = rl forall {x % _ == 0}

我尝试了一些其他的集合，但 List 是最快的(尽管仍然比我们完全避开 Range 和高阶函数的速度慢7倍)。

虽然我对 Scala 还是个新手，但我猜编译器可以通过简单地将方法中的 Range 文本(如上所述)替换为最外层作用域中的 Range 常量，轻松地实现快速而显著的性能提升。或者更好的方法是像 Java 中的字符串文字那样将它们实体化。

脚注 : 数组与 Range 大致相同，但有趣的是，一个新的 forall方法(如下所示)在64位上的执行速度提高了24% ，在32位上的执行速度提高了8% 。当我通过将因子的数量从20减少到15来减少计算大小时，差异就消失了，所以这可能是一种垃圾收集效应。不管是什么原因，在长时间满负荷运行时，这是非常重要的。

一个类似的皮条客为李斯特也导致约10% 更好的性能。

  val ra = (1 to 20).toArray
def isDivis(x:Int) = ra forall2 {x % _ == 0}


case class PimpedSeq[A](s: IndexedSeq[A]) {
def forall2 (p: A => Boolean): Boolean = {
var i = 0
while (i < s.length) {
if (!p(s(i))) return false
i += 1
}
true
}
}
implicit def arrayToPimpedSeq[A](in: Array[A]): PimpedSeq[A] = PimpedSeq(in)
小开

我只是想对那些可能因为类似这样的问题而对 Scala 失去信心的人发表一下看法，这类问题在几乎所有函数式语言的性能中都会出现。如果你在哈斯克尔优化折叠，你经常不得不重写它作为一个递归的尾部调用优化循环，否则你将有性能和内存问题要处理。

我知道不幸的是 FP 还没有优化到我们不需要考虑这些事情的地步，但是这根本不是 Scala 特有的问题。

小开

尝试解决方案 Scala for Project Euler中给出的一行程序

给定的时间至少比你的快，虽然远离 while 循环. . :)

小开

Scala 特有的问题已经被讨论过了，但是主要的问题是使用蛮力算法并不是很酷。考虑一下(比原来的 Java 代码快得多) :

def gcd(a: Int, b: Int): Int = {
if (a == 0)
b
else
gcd(b % a, a)
}
print (1 to 20 reduce ((a, b) => {
a / gcd(a, b) * b
}))

提交答案