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

在我创buildfunction代码的第一次尝试之一,我遇到了性能问题。

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

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

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

为什么第二种方法需要更长时间? 我怎样才能改变工作既高效又利用函数式编程风格?

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

  • 更快的一个不使用任何generics,所以它不面临拳击/拆箱。
  • 更快的一个不创build临时集合,从而避免了额外的内存拷贝。

让我们考虑慢一点的部分。 第一:

 first.zip(second) 

这将创build一个新的数组,一个Tuple2数组。 它会将两个数组中的所有元素复制到Tuple2对象中,然后Tuple2这些对象的引用复制到第三个数组中。 现在注意到Tuple2被参数化了,所以它不能直接存储Float 。 而是为每个数字创build新的java.lang.Float实例,将数字存储在这些实例中,然后将每个实例的引用存储到Tuple2

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

现在创build了第四个数组。 为了计算这些元素的值,需要从第三个数组读取对元组的引用,读取存储在它们中的java.lang.Float的引用,读取数字,乘法,创build一个新的java.lang.Float来存储结果,然后传回这个引用,这个引用将被重新引用以存储在数组中(数组没有被types擦除)。

不过,我们还没有完成。 接下来的部分是:

 reduceLeft(_+_) 

这是一个相对无害的,除了它仍然做拳击/拆箱和迭代创buildjava.lang.Float ,因为reduceLeft接收一个Function2 ,它被参数化。

斯卡拉2.8引入了一个称为专业化的function,将摆脱很多这些拳击/拆箱。 但是让我们考虑替代更快的版本。 比如,我们可以在一个步骤中进行mapreduceLeft

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

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

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

实际上,这最后一个节省不了多less,所以我认为非严格的“迷失”是相当快的(即这些方法之一即使在一个视图中也是严格的)。 还有一种压缩方法是非严格的(即避免一些中间结果),默认情况下:

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

这给了前者更好的结果。 比foldLeft ,虽然不是很多。 不幸的是,我们不能合并与foldLeft zipped ,因为前者不支持后者。

最后一个是我能得到的最快的。 比这更快,只有专业化。 现在, Function2碰巧是专门的,但是对于IntLongDouble 。 其他的原语被遗漏了,因为专门化增加了每个原语的代码大小。 在我的testing中,尽pipeDouble实际上需要更长的时间。 这可能是其规模的两倍,也可能是我做错了。

因此,最后,问题是多种因素的结合,包括产生元素的中间副本,以及Java(JVM)处理基元和generics的方式。 Haskell中使用超级编译的类似代码将等于任何缺less汇编程序的代码。 在JVM上,您必须意识到权衡,并准备优化关键代码。

我用Scala 2.8做了一些变化。 循环版本是你写的,但function版本略有不同:

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

我用Double而不是Float来运行,因为目前专业化只能用于Double。 然后我testing了arrays和载体作为载体types。 此外,我testing了工作在java.lang.Double而不是原始Doubles上的Boxed变体来测量原始types装箱和拆箱的效果。 这是我得到的(运行Java 1.6_10服务器VM,Scala 2.8 RC1,每次testing5次)。

 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

首先要注意的是,到目前为止,最原始的数组循环和原始数组函数reduce之间的区别是最大的。 这大约是15倍,而不是你所看到的40倍,这反映了Scala 2.8在2.7以上的改进。 尽pipe如此,原始数组循环是所有testing中速度最快的,而基本数组减less速度最慢。 原因是原始Java数组和generics操作并不是很合适。 从generics函数访问原始Java数组的元素需要大量的装箱/拆箱,有时甚至需要反思。 未来的Scala版本将专门化Array类,然后我们应该看到一些改进。 但是现在就是这样。

如果你从数组到vector,你会注意到几件事情。 首先,reduce版本现在比命令循环更快! 这是因为vector减less可以利用高效的批量操作。 其次,向量减less比数组减less要快,这说明了基元types数组对于一般的高阶函数造成的内在开销。

如果通过仅使用装箱的java.lang.Double值来消除装箱/拆箱的开销,则图片会更改。 现在减less数组比循环慢2倍,而不是以前的15倍。 这更接近中间数据结构的三个循环的固有开销,而不是命令式的融合循环。 循环向量现在是最慢的解决scheme,而减less向量比减less数组慢一点。

所以总的答案是:这取决于。 如果你对原始值数组有严格的循环,没有什么比命令式循环更好的了。 编写循环也没有问题,因为它们不再比function版本更容易理解。 在所有其他情况下,FP解决scheme看起来有竞争力。

这是一个微观基准,它取决于编译器如何优化你的代码。 你在这里有3个循环,

压缩 。 地图。 折

现在,我相当确定Scala编译器不能将这三个循环合并为一个循环,而底层的数据types是严格的,所以每个(。)对应一个正在创build的中间数组。 必要的/可变的解决scheme将每次重复使用缓冲区,避免复制。

现在,理解构成这三个函数是什么意思是理解函数式编程语言的性能的关键 – 实际上,在Haskell中,这三个循环将被优化成一个循环,重用一个底层缓冲区 – 但Scala不能做那。

然而,坚持使用combinator方法是有好处的 – 通过区分这三个函数,代码的并行化将更容易(用parMap等代替地图)。 事实上,给定正确的数组types(例如并行数组 ),一个足够智能的编译器将能够自动并行化您的代码,从而获得更多的性能优势。

总之:

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

唐·斯图尔特(Don Stewart)有一个很好的答案,但是从一个循环到三个循环如何造成40个因素的放缓可能并不明显。 我会补充他的答案,斯卡拉编译为JVM字节码,不仅斯卡拉编译器不融合三个循环为一体,但斯卡拉编译器几乎肯定分配所有的中间arrays。 众所周知, JVM的实现不是为了处理函数式语言所要求的分配率而devise的 。 分配是function程序中的一个重要的成本,这是Don Stewart和他的同事们为Haskell实现的循环融合转换非常强大:它们消除了大量的分配。 当你没有这些转换时,再加上你使用了一个昂贵的分配器,比如在一个典型的JVM上find的,这就是大幅放缓的地方。

Scala是一个伟大的工具,用于体验不同寻常的语言思想组合的performance力:类,混合,模块,函数等等。 但是这是一个相对年轻的研究语言,它运行在JVM上,所以除了JVM擅长的那些代码之外,期望有很好的性能是不合理的。 如果你想尝试一下Scala提供的语言思想,那么这是一个非常有趣的devise,但是不要指望在一个function性语言的成熟编译器中获得的纯函数代码的性能相同,就像GHC或MLton 。

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

不一定 。 与一stream的function,模式匹配和currying做的东西不需要特别慢。 但是对于Scala来说,与其他function语言的其他实现相比,您真的不得不小心分配 – 它们可能非常昂贵。

Scala集合库是完全通用的,所提供的操作是为了最大的能力而不是最大的速度。 所以,是的,如果你没有注意到使用Scala的function范例(特别是如果你使用的是原始数据types的话),那么你的代码运行的时间就会比不使用注意力/迭代范例的时间要长。

也就是说,您可以轻松创build非通用的function操作,快速执行所需的任务。 在使用浮游物对的情况下,我们可以做以下事情:

 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) 

然后这些操作会更快。 (如果使用Double和2.8.RC1,则更快;因为那么函数(Double,Double)=>Double将是专用的,而不是通用的;如果您使用较早的东西,则可以创build自己的abstract class F { def f(a: Float) : Float }然后用new F { def f(a: Float) = a*a }而不是(a: Float) => a*a调用。

无论如何,重要的一点是,它不是使Scala中的函数式编码变得很慢的函数式样,而是为了devise库的最大功率/灵活性,而不是最大速度。 这是明智的,因为每个人的速度要求通常是微妙的不同的,所以很难把每个人都做的最好。 但是,如果你所做的不只是一点点,你可以写自己的东西,function风格的性能损失是非常小的。

我不是一个专家的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 

为了回答标题中的问题:简单的function结构可能比JVM上的命令慢。

但是,如果我们只考虑简单的构造,那么我们不妨扔掉所有的现代语言,并坚持使用C语言或汇编语言。 如果你看编程语言枪战,C总是赢。

那么为什么select现代语言呢? 因为它可以让你expression更清洁的devise。 清洁devise可以提高应用程序的整体运行性能。 即使一些低级方法可能会变慢。 我最喜欢的例子之一是BuildR vs. Maven的performance。 BuildR是用Ruby编写的,这是一种解释性的,慢的语言。 Maven是用Java编写的。 BuildR的构build速度是Maven的两倍。 这主要是由于与Maven相比轻量级的BuildR的devise。

你的function解决scheme很慢,因为它正在产生不必要的临时数据结构 去除这些被称为“砍伐森林”,通过将匿名函数转换为单个匿名函数并使用单个聚合器,可以使用严格的函数式语言轻松完成。 例如,用F#编写的解决scheme使用zipmapreduce

 let dot xs ys = Array.zip xs ys |> Array.map (fun (x, y) -> x * y) -> Array.reduce ( * ) 

可以使用fold2来重写,以避免所有的临时数据结构:

 let dot xs ys = Array.fold2 (fun txy -> t + x * y) 0.0 xs ys 

这要快得多,而且可以在Scala和其他严格的函数式语言中完成相同的转换。 在F#中,还可以将fold2定义为inline函数,以便使函数参数内联高阶函数,从而恢复命令循环的最佳性能。

这里是数组的dbyrnes解决scheme(假设要使用数组),只是迭代索引:

 def multiplyAndSum (l1: Array[Int], l2: Array[Int]) : Int = { def productSum (idx: Int, sum: Int) : Int = if (idx < l1.length) productSum (idx + 1, sum + (l1(idx) * l2(idx))) else sum if (l2.length == l1.length) productSum (0, 0) else error ("lengths don't fit " + l1.length + " != " + l2.length) } val first = (1 to 500).map (_ * 1.1) toArray val second = (11 to 510).map (_ * 1.2) toArray def loopi (n: Int) = (1 to n).foreach (dummy => multiplyAndSum (first, second)) println (timed (loopi (100*1000))) 

这需要大约1/40的列表方式。 我没有安装2.8,所以你必须自己testing@tailrec。 🙂