如何优化Scala中的for-understanding和循环？

Question

所以Scala应该和Java一样快.我正在重新审视我最初用Java解决的Scala中的一些Project Euler问题.具体问题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 7 64位上使用Scala 2.9.0.1.如何提高性能？难道我做错了什么？或者Java速度更快？

Answer 1

这种特殊情况下的问题是你从for-expression中返回.这反过来被转换为NonLocalReturnException的抛出,它被封闭的方法捕获.优化器可以消除foreach但是还不能消除throw/catch.投掷/捕获是昂贵的.但由于这种嵌套返回在Scala程序中很少见,因此优化器还没有解决这种情况.有一些工作正在改进优化器,希望很快能解决这个问题.

Answer 2

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

与Java的for循环相反,Scala的for理解实际上是高阶方法的语法糖; 在这种情况下,您将foreach在Range对象上调用该方法.Scala for非常普遍,但有时会导致痛苦的表现.

您可能想-optimize在Scala版本2.9中尝试该标志.观察到的性能可能取决于所使用的特定JVM,并且JIT优化器具有足够的"预热"时间来识别和优化热点.

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

• http://groups.google.com/group/scala-user/browse_thread/thread/86adb44d72ef4498
• http://groups.google.com/group/scala-language/browse_thread/thread/94740a10205dddd2

以下是错误跟踪器中的问题:https: //issues.scala-lang.org/browse/SI-4633

更新5/28:

• 作为一个短期解决方案,ScalaCL插件(alpha)将简单的Scala循环转换为等效的while循环.
• 作为一个潜在的长期解决方案,来自EPFL和斯坦福的团队正在合作开展一个项目,以实现"虚拟"Scala的运行时编译,实现极高的性能.例如,多个惯用功能循环可以在运行时融合到最佳JVM字节码中,或者融合到另一个目标(例如GPU).该系统是可扩展的,允许用户定义的DSL和转换.查看出版物和斯坦福大学课程笔记.初步代码可在Github上获得,预计将在未来几个月发布.

Answer 3

作为后续,我尝试了-optimize标志,它将运行时间从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))
}

并试图弄清楚如何以简洁的方式摆脱"forall".我悲惨地失败了,想出来了

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秒)的版本快56倍!(请参阅下面的编辑,了解为什么这比Java快)

显然,我的下一步是将上述内容转换回Java,但Java无法处理它并抛出一个带有n的StackOverflowError,大约在22000标记处.

然后我抓了一下头,用更多的尾递归替换了"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"方法)之类的东西基本上被打破了,必须被不优雅和冗长的"whiles"或尾递归所取代. .我尝试使用Scala的原因很多,原因在于简洁的语法,但如果我的代码运行速度慢100倍,那就不好了!

编辑 :(已删除)

编辑编辑:运行时间在2.5秒和0.7秒之间的前差异完全是由于是否使用了32位或64位JVM.命令行中的Scala使用JAVA_HOME设置的任何内容,而Java则使用64位(如果可用).IDE有自己的设置.这里的一些测量:Eclipse中的Scala执行时间

Answer 4

关于理解的答案是正确的,但这不是整个故事.您应该注意,使用returnin isEvenlyDivisible不是免费的.在里面使用return for,强制scala编译器生成非本地返回(即返回它的外部函数).

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

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

这只打印一次"Hi".

需要注意的是,return在foo出口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开销.

Answer 5

有些方法可以加快forall我发现的方法:

原文:41.3秒

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

预先实例化范围,因此我们不会每次创建新范围:9.0 s

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

转换为List而不是Range:4.8 s

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来减少计算大小时,差异消失了,所以这可能是垃圾收集效应.无论原因是什么,在长时间满负荷运行时都很重要.

List的类似pimp也使性能提高了约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)