Swift性能:map()和reduce()vs for循环

Question

我正在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秒.使用Integers而不是Floats,结果相似.

我创建了一个类似的基准来测试Swift的性能reduce.这一次,reduce和for一个大阵的元素求和时,环路实现几乎相同的性能.但当我循环测试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倍.

我对斯威夫特的表现感到有些困惑.内置的Array方法不应该比执行此类操作的天真方法更快吗？也许某些知识水平低于我的人可以对这种情况有所了解.

Answer 1

内置的Array方法不应该比执行此类操作的天真方法更快吗？也许某些知识水平低于我的人可以对这种情况有所了解.

我只是想尝试解决这个问题的这一部分,更多的是从概念层面(对我的Swift优化器的本质一无所知)和"不一定".它来自编译器设计和计算机体系结构的背景,而不是对Swift优化器性质的深层次了解.

呼叫开销

使用函数map和reduce接受函数作为输入,它会给优化器带来更大的压力,使其成为一种方式.在这种情况下,自然诱惑缺少一些非常积极的优化,就是在map你提供的闭包和闭包之间不断地来回分支,同样在这些不同的代码分支之间传输数据(通过寄存器和堆栈,通常情况下).

优化器很难消除这种分支/调用开销,特别是考虑到Swift关闭的灵活性(不是不可能,但在概念上非常困难).C++优化器可以内联函数对象调用,但具有更多限制和代码生成技术,编译器实际上必须为map您传入的每种类型的函数对象生成一组全新的指令(并明确帮助程序员指示用于代码生成的函数模板.

因此,发现手动循环可以更快地执行起来应该不会令人惊讶 - 它们对优化器施加了很大的压力.我看到有些人引用这些高阶函数应该能够更快,因为供应商能够执行诸如并行化循环之类的事情,但是为了有效地并行化循环首先需要那种典型的信息.允许优化器将嵌套函数调用内联到它们变得像手动循环一样便宜的点.否则你传入的函数/闭包实现对于以下函数实际上是不透明的map/reduce:它们只能调用它并支付这样做的开销,并且不能并行化它,因为它们不能假设任何关于副作用和线程的性质 - 安全这样做.

当然这完全是概念性的--Swift可能会在未来优化这些案例,或者现在可能已经能够这样做了(-Ofast作为一种常用的方法,可以让Swift以某种安全为代价加快速度) .但它确实给优化器带来了更大的压力,至少要在手动循环中使用这些功能,而你在第一个基准测试中看到的时间差异似乎反映了一种可能的差异.期望这个额外的呼叫开销.最好的方法是查看程序集并尝试各种优化标志.

标准功能

这并不是要阻止使用这些功能.他们更简洁地表达意图,他们可以提高生产力.依赖它们可以让您的代码库在未来版本的Swift中更快地完成,而不需要您的任何参与.但它们并不一定总是会更快 - 认为更直接表达你想要做的更高级别的库函数会更快,这是一个很好的一般规则,但总是存在例外情况.规则(但最好是事先见证了手中的剖析器,因为在信任方面比在这里不信任更容易犯错).

人工基准

至于你的第二个基准测试,它几乎可以肯定是编译器优化远离没有影响用户输出的副作用的代码的结果.由于优化者为消除不相关的副作用(基本上不影响用户输出的副作用),人工基准测试具有众所周知的误导性倾向.因此,在构建基准测试时必须要小心,因为它们不是优化器的结果,只是跳过了您实际想要进行基准测试的所有工作.至少,您希望测试输出从计算中收集的最终结果.

Answer 2

我不能说太多关于你的第一个测试(map()VS append()在一个循环中),但我可以确认你的结果.如果添加,追加循环会变得更快

output.reserveCapacity(array.count)

在数组创建之后.Apple似乎可以在这里改进,你可能会提交一份错误报告.

在

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

编译器(可能)删除整个循环,因为根本不使用计算结果.我只能推测为什么不会发生类似的优化

for _ in 0..<100_000 {
    let sum = array.reduce(0, combine: {$0 + $1})
}

但是更难以决定是否reduce()使用闭包调用有任何副作用.

如果稍微更改测试代码以计算并打印总和

do {
    var total = Float(0.0)
    let start = NSDate()
    for _ in 0..<100_000 {
        total += array.reduce(0, combine: {$0 + $1})
    }
    let elapsed = NSDate().timeIntervalSinceDate(start)
    print("sum with reduce:", elapsed)
    print(total)
}

do {
    var total = Float(0.0)
    let start = NSDate()
    for _ in 0..<100_000 {
        var sum = Float(0.0)
        for element in array {
            sum += element
        }
        total += sum
    }
    let elapsed = NSDate().timeIntervalSinceDate(start)
    print("sum with loop:", elapsed)
    print(total)
}

然后两种变体在我的测试中大约需要10秒钟.

Answer 3

我做了一组快速的性能测试,测量了一个字符串数组上重复转换的性能,它表明它.map比for循环的性能要好得多,大约是10倍.

下面的屏幕截图中的结果显示,单个map块中的链式转换优于多个maps,每个块中只有一个转换,并且任何使用mapout-perform for循环.

我在游乐场使用的代码:

import Foundation
import XCTest

class MapPerfTests: XCTestCase {
	var array =
		[
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString",
			"MyString"
	]

	func testForLoopAllInOnePerf() {
		measure {
			var newArray: [String] = []
			for item in array {
				newArray.append(item.uppercased().lowercased().uppercased().lowercased())
			}
		}
	}

	func testForLoopMultipleStagesPerf() {
		measure {
			var newArray: [String] = []
			for item in array {
				let t1 = item.uppercased()
				let t2 = item.lowercased()
				let t3 = item.uppercased()
				let t4 = item.lowercased()
				newArray.append(t4)
			}
		}
	}

	func testMultipleMapPerf() {
		measure {
			let newArray = array
				.map( { $0.uppercased() } )
				.map( { $0.lowercased() } )
				.map( { $0.uppercased() } )
				.map( { $0.lowercased() } )
		}
	}

	func testSingleMapPerf() {
		measure {
			let newArray = array
				.map( { $0.uppercased().lowercased().uppercased().lowercased() } )
		}
	}
}

MapPerfTests.defaultTestSuite.run()