Scala函数式编程比传统编码慢吗？

Question

在我第一次尝试创建功能代码时,我遇到了性能问题.

我从一个共同的任务开始 - 将两个数组的元素相乘并总结结果:

var first:Array[Float] ...
var second:Array[Float] ...    
var sum=0f; 
for (ix<-0 until first.length) 
    sum += first(ix) * second(ix);

以下是我改革工作的方式:

sum = first.zip(second).map{ case (a,b) => a*b }.reduceLeft(_+_)

当我对这两种方法进行基准测试时,第二种方法需要40倍的时间才能完成!

为什么第二种方法需要更长的时间？如何将工作改造为速度效率和使用函数式编程风格？

Answer 1

这两个例子速度如此不同的主要原因是:

• 更快的一个不使用任何泛型,所以它不面临装箱/拆箱.
• 更快的一个不创建临时集合,因此,避免额外的内存副本.

让我们逐个考虑慢一点.第一:

first.zip(second)

这会创建一个新数组,一个数组Tuple2.它会将两个数组中的所有元素复制到Tuple2对象中,然后将对每个对象的引用复制到第三个数组中.现在,请注意Tuple2参数化,因此无法Float直接存储.相反,java.lang.Float为每个数字创建新的实例,数字存储在它们中,然后将每个数字的引用存储到数据中Tuple2.

map{ case (a,b) => a*b }

现在创建了第四个数组.要计算这些元素的值,需要从第三个数组中读取对元组的引用,读取java.lang.Float存储在其中的引用,读取数字,乘以,创建新的java.lang.Float以存储结果,然后传递此引用回,这将在去参考的再次被存储在数组中(数组不是类型擦除).

但是,我们还没有完成.这是下一部分:

reduceLeft(_+_)

那个是相对无害的,除了它仍然java.lang.Float在迭代时进行装箱/拆箱和创建,因为reduceLeft接收a Function2,参数化.

Scala 2.8引入了一个名为specialization的功能,可以摆脱很多这些装箱/拆箱.但是让我们考虑替代更快的版本.我们可以,例如,做map和reduceLeft在一个单一的步骤:

sum = first.zip(second).foldLeft(0f) { case (a, (b, c)) => a + b * c }

我们可以使用view(Scala 2.8)或projection(Scala 2.7)来完全避免创建中间集合:

sum = first.view.zip(second).map{ case (a,b) => a*b }.reduceLeft(_+_)

实际上,最后一个并没有节省太多,所以我认为非严格性如果被"丢失"得相当快(即,即使在视图中这些方法中的一个也是严格的).还有一种替代的压缩方法,默认情况下是非严格的(即,避免一些中间结果):

sum = (first,second).zipped.map{ case (a,b) => a*b }.reduceLeft(_+_)

这给前者带来了更好的结果.比foldLeft一个好,但不是很多.不幸的是,我们无法结合zipped,foldLeft因为前者不支持后者.

最后一个是我能得到的最快的.比这快,只有专业化.现在,Function2碰巧是专门的,但是Int,Long和Double.其他原语被省略了,因为专门化会为每个原语增加相当大的代码大小.在我的测试中,虽然Double实际上需要更长的时间.这可能是因为它的大小是它的两倍,或者它可能是我做错了.

因此,最终,问题是多种因素的组合,包括生成元素的中间副本,以及Java(JVM)处理基元和泛型的方式.使用超级编译的Haskell中的类似代码将等于任何缺少汇编程序的代码.在JVM上,您必须了解权衡并准备优化关键代码.

Answer 2

我用Scala 2.8做了一些变化.循环版本与您编写的一样,但功能版本略有不同:

(xs, ys).zipped map (_ * _) reduceLeft(_ + _)

我使用Double而不是Float运行,因为目前专业化只为Double启动.然后,我使用数组和向量作为载体类型进行测试.此外,我测试了Boxed变体,它们可以在java.lang.Double上使用而不是原始的双打来测量原始类型装箱和拆箱的效果.这是我得到的(运行Java 1.6_10服务器VM,Scala 2.8 RC1,每次测试运行5次).

loopArray               461             437             436             437             435
reduceArray             6573            6544            6718            6828            6554
loopVector              5877            5773            5775            5791            5657
reduceVector            5064            4880            4844            4828            4926

loopArrayBoxed          2627            2551            2569            2537            2546
reduceArrayBoxed        4809            4434            4496            4434            4365
loopVectorBoxed         7577            7450            7456            7463            7432
reduceVectorBoxed       5116            4903            5006            4957            5122

首先要注意的是,到目前为止,最大的区别在于原始数组循环和原始数组功能减少之间.它大约是15而不是你看到的40,这反映了Scala 2.8的改进超过2.7.尽管如此,原始数组循环是所有测试中最快的,而原始数组减少是最慢的.原因是原始Java数组和通用操作不是很合适.从泛型函数访问原始Java数组的元素需要大量的装箱/拆箱,有时甚至需要反射.Scala的未来版本将专门化Array类,然后我们应该看到一些改进.但是现在就是这样.

如果你从数组转向向量,你会注意到几件事.首先,reduce版本现在比命令式循环更快!这是因为矢量减少可以利用有效的批量操作.其次,向量减少比数组减少更快,这说明了基本类型数组为通用高阶函数带来的固有开销.

如果通过仅使用装箱的java.lang.Double值来消除装箱/拆箱的开销,则图片会发生变化.现在减少数组比循环慢一点,而不是之前的15倍.这更接近于具有中间数据结构的三个循环的固有开销,而不是命令式版本的融合循环.现在,在矢量上循环是最慢的解决方案,而减少矢量比减少数组要慢一点.

总的答案是:这取决于.如果你对原始值数组有紧密的循环,那么就没有什么能胜过命令式循环.编写循环没有问题,因为它们比功能版本既不长也不易理解.在所有其他情况下,FP解决方案看起来很有竞争力

Answer 3

这是一个微基准测试,它取决于编译器如何优化代码.这里有3个循环,

压缩 .地图.折

现在,我很确定Scala编译器不能将这三个循环融合到一个循环中,并且底层数据类型是严格的,因此每个(.)对应于正在创建的中间数组.命令式/可变解决方案每次都会重用缓冲区,避免复制.

现在,了解构成这三个函数的含义对于理解函数式编程语言中的性能至关重要 - 实际上,在Haskell中,这三个循环将被优化为一个重用底层缓冲区的循环 - 但Scala不能做那.

然而,坚持组合方法有一些好处 - 通过区分这三个函数,可以更容易地并行化代码(用mapMap替换map等).实际上,给定正确的数组类型(例如并行数组),足够智能的编译器将能够自动并行化您的代码,从而获得更多的性能优势.

所以,总结一下:

• 天真的翻译可能会有意想不到的副本和低效率
• 聪明的FP编译器删除了这个开销(但Scala还没有)
• 如果你想重新定位你的代码,例如并行化它,那么坚持高级方法会得到回报

Answer 4

唐斯图尔特有一个很好的答案,但从一个循环到三个循环可能会导致40减速因素可能并不明显. 我将补充他的答案,即Scala编译为JVM字节码,并且Scala编译器不仅不会将三个循环融合为一个,而且Scala编译器几乎肯定会分配所有中间数组.众所周知,JVM的实现并非旨在处理功能语言所需的分配率.分配是功能程序中的一个重要成本,而Don Stewart和他的同事为Haskell实现的循环融合转换是如此强大:它们消除了大量的分配.当你没有这些转换时,再加上你使用的是一个昂贵的分配器,例如在典型的JVM上找到的分配器,这就是大减速的来源.

Scala是一个很好的工具,用于尝试不同寻常的语言思想组合的表达能力:类,混合,模块,函数等.但它是一种相对年轻的研究语言,它运行在JVM上,因此除了JVM擅长的代码之外,期望出色的性能是不合理的.如果你想尝试Scala提供的混合语言思想,那么它很棒 - 这是一个非常有趣的设计 - 但是不要期望在功能语言的成熟编译器上获得相同的纯函数代码性能,比如GHC或MLton.

scala函数式编程比传统编码慢吗？

不一定.与一流功能,模式匹配和currying相关的东西不需要特别慢.但是使用Scala,与其他功能语言的其他实现相比,你真的必须注意分配 - 它们可能非常昂贵.

Answer 5

Scala集合库是完全通用的,并且选择的操作是为了获得最大功能,而不是最大速度.所以,是的,如果你在没有注意的情况下使用Scala的功能范例(特别是如果你使用原始数据类型),那么你的代码运行时间(在大多数情况下)比你使用命令式/迭代范式而不注意.

也就是说,您可以轻松创建非通用的功能操作,以便快速执行所需的任务.在使用浮动对的情况下,我们可能会执行以下操作:

class FastFloatOps(a: Array[Float]) {
  def fastMapOnto(f: Float => Float) = {
    var i = 0
    while (i < a.length) { a(i) = f(a(i)); i += 1 }
    this
  }
  def fastMapWith(b: Array[Float])(f: (Float,Float) => Float) = {
    val len = a.length min b.length
    val c = new Array[Float](len)
    var i = 0
    while (i < len) { c(i) = f(a(i),b(i)); i += 1 }
    c
  }
  def fastReduce(f: (Float,Float) => Float) = {
    if (a.length==0) Float.NaN
    else {
      var r = a(0)
      var i = 1
      while (i < a.length) { r = f(r,a(i)); i += 1 }
      r
    }
  }
}
implicit def farray2fastfarray(a: Array[Float]) = new FastFloatOps(a)

然后这些操作会快得多.(还要更快如果使用双和2.8.RC1,因为这样的功能(Double,Double)=>Double将以专业化,而不是通用的;如果你正在使用的东西前,你可以创建自己的 abstract class F { def f(a: Float) : Float },然后用打电话new F { def f(a: Float) = a*a }代替(a: Float) => a*a.)

无论如何,重点是它不是使Scala中的函数编码变慢的功能样式,而是库设计时考虑到最大功率/灵活性,而不是最大速度.这是明智的,因为每个人的速度要求通常略有不同,因此很难将每个人都覆盖得非常好.但是,如果你做的不仅仅是一点点,你可以编写自己的东西,其中功能风格的性能损失非常小.

Answer 6

我不是专家Scala程序员,所以可能有一个更有效的方法,但是这样的事情呢.这可以是尾调用优化,因此性能应该没问题.

def multiply_and_sum(l1:List[Int], l2:List[Int], sum:Int):Int = {
    if (l1 != Nil && l2 != Nil) {
        multiply_and_sum(l1.tail, l2.tail, sum + (l1.head * l2.head))
    }
    else {
        sum
    }
}

val first = Array(1,2,3,4,5)
val second = Array(6,7,8,9,10)
multiply_and_sum(first.toList, second.toList, 0)  //Returns: 130