性能-Scala函数式编程是否比传统编码慢?

在我第一次创建功能代码的尝试中,我遇到了一个性能问题。

我从一个常见的任务开始-将两个数组的元素相乘并得出结果:

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倍的时间才能完成!

为什么第二种方法需要这么长时间? 我如何才能使工作既高效又能使用函数式编程风格呢?

9个解决方案
68 votes

这两个示例的速度差异如此之大的主要原因是:

  • 更快的速度不使用任何泛型,因此不会面对装箱/拆箱。
  • 更快的速度不会创建临时集合,因此避免了额外的内存副本。

让我们逐个考虑较慢的一个。 第一:

first.zip(second)

这将创建一个新数组,即Function2数组。它将两个数组中的所有元素复制到Int297对象中,然后将对每个对象的引用复制到第三个数组中。 现在,请注意Long已参数化,因此无法直接存储Double。 而是,为每个编号创建Double的新实例,将这些编号存储在其中,然后将每个编号的引用存储到Tuple2中。

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

现在,创建第四个数组。 要计算这些元素的值,它需要从第三个数组中读取对元组的引用,读取对其中存储的Function2的引用,读取数字,相乘,创建一个新的Int297以存储结果,然后传递 返回此引用,它将再次被取消引用以存储在数组中(数组未类型擦除)。

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

reduceLeft(_+_)

那是相对无害的,只是它仍然在迭代中进行装箱/拆箱和Function2的创建,因为Int接收到了Long,并对其进行了参数化。

Scala 2.8引入了一项称为“专业化”的功能,该功能将消除很多此类装箱/拆箱操作。 但是,让我们考虑其他更快的版本。 例如,我们可以一步完成Function2Int

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

我们可以使用Function2(Scala 2.8)或2983706863268791791297(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(_+_)

这给出了比前者更好的结果。 比Function2还要好,尽管不是很多。 不幸的是,我们不能将IntLong结合起来,因为前者不支持后者。

最后一个是我能得到的最快的。 比那更快,只有专业化。 现在,Function2恰好是专门的,但对于Int,2983706863268791791和Double则被遗漏了。其他基本原语被省略了,因为专门化极大地增加了每个原语的代码大小。 在我的测试中,尽管Double实际上花费的时间更长。 这可能是因为它的大小是原来的两倍,或者可能是我做错了。

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

Daniel C. Sobral answered 2020-07-26T16:22:33Z
34 votes

我使用Scala 2.8对此做了一些变化。 循环版本与您编写时相同,但是功能版本略有不同:

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

我使用Double而不是Float来运行,因为当前专业化仅适用于Double。 然后,我将数组和向量作为载体类型进行了测试。 此外,我测试了可在java.lang.Double而不是原始Doubles上运行的Boxed变量基本类型装箱和拆箱的效果。 这就是我得到的(运行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

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

如果从数组转到向量,您会注意到几件事。 首先,reduce版本现在比命令循环更快! 这是因为vector reduce可以利用有效的批量操作。 其次,向量归约比数组归约要快,这说明了原始类型的数组对通用高阶函数造成的固有开销。

如果仅通过使用装箱的java.lang.Double值来消除装箱/拆箱的开销,则图片将发生变化。 现在,reduce over array的速度比循环慢2倍,而不是之前的15倍。 这更接近于具有中间数据结构的三个循环的固有开销,而不是命令式版本的融合循环。 到目前为止,遍历向量是最慢的解决方案,而减少向量的速度要比减少数组的速度慢一些。

因此,总体答案是:这取决于。 如果您在原始值数组上有紧密的循环,那么没有什么比命令式循环更好的了。 编写循环没有问题,因为它们比功能版本既长又不容易理解。 在所有其他情况下,FP解决方案都具有竞争力。

Martin Odersky answered 2020-07-26T16:23:18Z
15 votes

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

压缩 。 地图。 折

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

现在,了解组成这三个函数的含义是理解功能编程语言性能的关键-实际上,在Haskell中,这三个循环将被优化为可重用底层缓冲区的单个循环-但Scala无法做到 那。

坚持使用组合器方法是有好处的-但是,通过区分这三个函数,可以更轻松地并行化代码(用parMap替换映射等)。 实际上,在给定正确的数组类型(例如并行数组)的情况下,足够聪明的编译器将能够自动并行化您的代码,从而获得更多的性能优势。

因此,总而言之:

  • 天真的翻译可能会有意想不到的副本和效率低下
  • 聪明的FP编译器消除了这种开销(但Scala尚不能)
  • 如果您想重新定位代码,例如坚持 并行化
Don Stewart answered 2020-07-26T16:24:16Z
14 votes

唐·斯图尔特(Don Stewart)有一个很好的答案,但是从一个循环到三个循环如何造成40倍的减速可能并不明显。 我将在他的回答中补充说Scala可以编译为JVM字节码,不仅Scala编译器不会将这三个循环融合为一个,而且Scala编译器几乎肯定会分配所有中间数组。 众所周知,JVM的实现并非旨在处理功能语言所需的分配率。 分配是功能程序中的一项重大成本,而这正是Don Stewart和他的同事为Haskell实现的循环融合转换功能如此强大:它们消除了很多分配。 当您没有这些转换时,加上您正在使用昂贵的分配器(例如在典型的JVM上发现的分配器),这就是造成大幅下降的原因。

Scala是尝试非常规语言概念(类,mixin,模块,函数等)的表达能力的绝佳工具。 但这是一种相对较年轻的研究语言,它可以在JVM上运行,因此,除了具有JVM擅长的那种代码之外,期望具有出色的性能是不合理的。 如果您想尝试Scala提供的各种语言思想,那很棒-这是一个非常有趣的设计-但不要指望在纯函数式代码上具有与成熟的函数式编译器一样的性能,例如 GHC或MLton。

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

不必要。 与一流功能,模式匹配和循环相关的工作不必特别慢。 但是,与其他功能语言的其他实现相比,使用Scala的确要多加留心,因为它们可能非常昂贵。

Norman Ramsey answered 2020-07-26T16:24:51Z
9 votes

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)

然后这些操作将更快。 (如果您使用Double和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中的功能编码变慢的功能风格,而是因为库的设计考虑到了最大的功能/灵活性,而不是最大的速度。 这是明智的,因为每个人的速度要求通常略有不同,因此很难很好地覆盖所有人。 但是,如果您要做的事情多于一点,那么您可以编写自己的东西,其中功能样式的性能损失非常小。

Rex Kerr answered 2020-07-26T16:25:26Z
5 votes

我不是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
dbyrne answered 2020-07-26T16:25:46Z
3 votes

要回答标题中的问题:在JVM上,简单的功能构造可能比命令式的慢。

但是,如果我们仅考虑简单的构造,那么我们最好扔掉所有现代语言,并坚持使用C或汇编程序。 如果您看过编程语言大战,C总是赢。

那么为什么选择现代语言呢? 因为它可以让您表达出更简洁的设计。 更简洁的设计可提高应用程序整体操作的性能。 即使某些底层方法可能会变慢。 我最喜欢的示例之一是BuildR vs. Maven的性能。 BuildR用Ruby(一种解释缓慢的语言)编写。 Maven用Java编写。 BuildR中的构建速度是Maven的两倍。 这主要是由于BuildR的设计比Maven轻巧。

IttayD answered 2020-07-26T16:26:16Z
2 votes

您的功能解决方案很慢,因为它会生成不必要的临时数据结构。 删除它们被称为砍伐森林,并且可以使用严格的功能语言轻松地完成这些操作,方法是将您的匿名函数滚动到一个匿名函数中,并使用一个聚合器。 例如,您使用zipfold2inline用F#编写的解决方案:

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 t x y -> t + x * y) 0.0 xs ys

这要快得多,并且可以使用Scala和其他严格的功能语言进行相同的转换。 在F#中,您也可以将fold2定义为inline,以使高阶函数与其函数参数内联,这样您就可以恢复命令式循环的最佳性能。

Jon Harrop answered 2020-07-26T16:26:46Z
1 votes

这是带有数组的dbyrnes解决方案(假设要使用数组),并且仅遍历索引:

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,因此您必须自己测试@tailrec。 :)

user unknown answered 2020-07-26T16:27:11Z
translate from https://stackoverflow.com:/questions/2794823/is-scala-functional-programming-slower-than-traditional-coding