一尘不染

快速性能:map()和reduce()与for循环

swift

我正在Swift中编写一些性能关键的代码。在实现了我能想到的所有优化并在Instruments中对应用程序进行了性能分析之后,我意识到,绝大多数CPU周期都花在了Floats数组上的执行map()reduce()操作上。所以,只是为了看看会发生什么,我更换的所有实例map,并reduce具有良好的老式for循环。令我惊讶的是,for循环快得多了!

对此感到有些困惑,我决定执行一些粗略的基准测试。在一个测试中,我map执行了一些简单的算术,然后返回了一个Floats数组,如下所示:

// Populate array with 1,000,000,000 random numbers
var array = [Float](count: 1_000_000_000, repeatedValue: 0)
for i in 0..<array.count {
    array[i] = Float(random())
}
let start = NSDate()
// Construct a new array, with each element from the original multiplied by 5
let output = array.map({ (element) -> Float in
    return element * 5
})
// Log the elapsed time
let elapsed = NSDate().timeIntervalSinceDate(start)
print(elapsed)

以及等效的for循环实现:

var output = [Float]()
for element in array {
    output.append(element * 5)
}

平均执行时间为map:20.1秒。for循环的平均执行时间:11.2秒。使用整数而不是浮点数的结果相似。

我创建了一个类似的基准来测试Swift的性能reduce。这一次,reducefor一个大阵的元素求和时,环路实现几乎相同的性能。但是当我像这样循环测试100,000次时:

// Populate array with 1,000,000 random numbers
var array = [Float](count: 1_000_000, repeatedValue: 0)
for i in 0..<array.count {
    array[i] = Float(random())
}
let start = NSDate()
// Perform operation 100,000 times
for _ in 0..<100_000 {
    let sum = array.reduce(0, combine: {$0 + $1})
}
// Log the elapsed time
let elapsed = NSDate().timeIntervalSinceDate(start)
print(elapsed)

vs:

for _ in 0..<100_000 {
    var sum: Float = 0
    for element in array {
        sum += element
    }
}

reduce方法花费29秒,而for循环花费(显然)0.000003秒。

当然,由于编译器优化的结果,我准备忽略上一个测试,但是我认为它可以为编译器与Swift的内置数组方法如何不同地优化循环提供一些见识。请注意,所有测试均在2.5
GHz i7 MacBook Pro上进行-
Os优化。结果取决于数组大小和迭代次数而有所不同,但是for循环总是比其他方法好至少1.5倍,有时甚至超过10倍。

我对Swift在这里的表现有些困惑。内置的Array方法难道不比执行此类操作的幼稚方法快吗?也许有人比我更了解底层知识,这使我对情况有所了解。


阅读 757

收藏
2020-07-07

共1个答案

一尘不染

内置的Array方法难道不比执行此类操作的幼稚方法快吗?也许有人比我更了解底层知识,这使我对情况有所了解。

我只想尝试用“不一定”来解决问题的这一部分,并且从概念的角度(对我的Swift优化器的本质了解很少)来解决更多问题。它更多的是来自于编译器设计和计算机体系结构的背景,而不仅仅是对Swift优化器本质的深入了解。

通话费用

通过将类似函数mapreduce接受函数作为输入,它给优化器施加了更大的压力,使它只能采用一种方式。在这种情况下,缺乏一些非常积极的优化的自然诱惑是,在的实现map和您提供的闭包之间不断地来回跳转,并同样在这些不同的代码分支之间传输数据(通过寄存器和栈,通常)。

That kind of branching/calling overhead is very difficult for the optimizer to
eliminate, especially given the flexibility of Swift’s closures (not
impossible but conceptually quite difficult). C++ optimizers can inline
function object calls but with far more restrictions and code generation
techniques required to do it where the compiler would effectively have to
generate a whole new set of instructions for map for each type of function
object you pass in (and with explicit aid of the programmer indicating a
function template used for the code generation).

因此,发现您的手动循环可以更快地执行并不奇怪,它们对优化器的负担要小得多。我已经看到有人指出,由于供应商能够执行诸如并行化循环之类的事情,因此这些高阶函数应该能够更快地运行,但是要有效地并行化循环首先会需要通常会提供的那种信息。允许优化器将嵌套函数调用内联到一个使它们变得与手动循环一样便宜的位置。否则,您传入的函数/闭包实现将对诸如map/reduce:他们只能调用它并为此付出开销,而不能并行化它,因为他们不能在此假设任何有关副作用的性质和线程安全性。

当然,这全都是概念性的-
Swift可能会在将来优化这些情况,或者现在可能已经做到了(-Ofast这是使Swift快速运行的一种常用方法,但会牺牲一些安全性)
。但这确实给优化器带来了更大的压力,至少要在手动循环上使用这些功能,并且您在第一个基准测试中看到的时间差异似乎反映了这种差异期望有额外的呼叫开销。找出答案的最佳方法是查看程序集并尝试各种优化标志。

标准功能

这并不是要阻止此类功能的使用。他们更简洁地表达意图,可以提高生产力。依靠它们可以使您的代码库在Swift的未来版本中更快地运行,而无需您的任何参与。但是它们并不一定总是会更快-
一个好的通用规则是,认为更直接表达您想要做的事情的高级库函数会变得更快,但是总是有例外。规则(但最好是在事后才发现有分析器,因为在这里信任错误比不信任要好得多)。

人为基准

至于您的第二个基准测试,几乎可以肯定是编译器优化了代码而没有影响用户输出的副作用的结果。由于优化程序为消除不相关的副作用(基本上不影响用户输出的副作用)而导致的人工基准测试往往会产生误导。因此,在构建基准测试时要特别小心,因为时间似乎太好了,以至于它们不是优化程序的结果,只是跳过了您实际想要进行基准测试的所有工作。至少,您希望测试输出从计算中收集到的一些最终结果。

2020-07-07