为什么我的过滤器版本与 Swifts 的表现如此不同？

Question

作为练习，我重写了一些 Swift 的高阶函数，其中一个是 .filter。我决定用仪器来衡量我的 .filter 版本与 Swift 的版本，但我对结果感到很困惑。

这是我的过滤器版本，我承认这可能不正确。

extension Array {
    func myFilter(predicate: Element -> Bool) -> [Element] {
        var filteredArray = [Element]()
        for x in self where predicate(x) {
            filteredArray.append(x)
        }

        return filteredArray
    }
}

发生了什么

我的过滤器

总体CPU消费：85.7%
我的过滤器消耗：67.9%

Swift的过滤器

总体CPU消费：57.7%
我的过滤器消耗：70.9%

如我所料

我预计会有类似的表现。我很困惑为什么我的过滤器函数调用本身会消耗更少 CPU 而我的整体应用程序 CPU 却高出近 30%。

我的问题

如果我 filter 写错了，请帮助我理解我的错误。否则请指出为什么 Swift 的 filter 比我的 CPU 减少了 30% 的负载。

Answer 1

好的，所以在阅读了所有发表的评论后，我决定也进行基准测试，这是我的结果。奇怪的是，built-in filter 的性能似乎比自定义实现更差。

TL;DR; 因为你的函数很短，编译器可以访问它的源代码，所以编译器内联函数调用，从而实现更多优化。

另一个考虑因素是您的 myFilter 声明没有考虑异常抛出闭包，而 built-in filter 会考虑。

将 @inline(never)、throws 和 rethrows 添加到您的 myFilter 声明中，您将获得与 built-in [=18= 类似的结果]

研究成果

我用mach_absolute_time()来获得准确的时间。我没有将结果转换为秒数，因为我只是对比较感兴趣。测试是运行 Yosemite 10.10.5 和 Xcode 7.2.

import Darwin

extension Array {
    func myFilter(@noescape predicate: Element -> Bool) -> [Element] {
        var filteredArray = [Element]()
        for x in self where predicate(x) {
            filteredArray.append(x)
        }

        return filteredArray
    }
}

let arr = [Int](1...1000000)

var start = mach_absolute_time()
let _ = arr.filter{ [=10=] % 2 == 0}
var end = mach_absolute_time()
print("filter:         \(end-start)")

start = mach_absolute_time()
let _ = arr.myFilter{ [=10=] % 2 == 0}
end = mach_absolute_time()
print("myFilter:       \(end-start)")

在debug模式下，filter比myFilter快：

filter:         370930078
myFilter:       479532958

在release中，然而，myFilter比filter好很多：

filter:         15966626
myFilter:       4013645

更奇怪的是 built-in filter 的精确副本（摘自 Marc 的评论）比 built-in 的表现更好。

extension Array {
    func originalFilter(
        @noescape includeElement: (Generator.Element) throws -> Bool
        ) rethrows -> [Generator.Element] {

            var result = ContiguousArray<Generator.Element>()

            var generator = generate()

            while let element = generator.next() {
                if try includeElement(element) {
                    result.append(element)
                }
            }

            return Array(result)
    }

}

start = mach_absolute_time()
let _ = arr.originalFilter{ [=13=] % 2 == 0}
end = mach_absolute_time()
print("originalFilter: \(end-start)")

使用上面的代码，我的基准应用程序给出了以下输出：

filter:         13255199
myFilter:       3285821
originalFilter: 3309898

回到 debug 模式，filter 的 3 种风格给出了这个输出：

filter:         343038057
myFilter:       429109866
originalFilter: 345482809

filter 和 originalFilter 给出了非常接近的结果。这让我认为 Xcode 链接到 Swifts stdlib 的调试版本。然而，当在 release 中构建时，Swifts stdlib 的性能比 debug 中的要好 3 倍，这让我很困惑。

所以下一步是分析。我点击 Cmd+I，将采样间隔设置为 40us，并对应用程序进行了两次分析：一次仅启用了 filter 调用，另一次启用了 myFilter。我删除了打印代码以使 stack-trace 尽可能干净。

Built-in filter 分析：
_{（来源：cristik-test.info）}

myFilter:

尤里卡！，我找到了答案。没有 myFilter 调用的轨迹，这意味着编译器内联了函数调用，从而实现了额外的优化，从而提高了性能。

我将 @inline(never) 属性添加到 myFilter，但它的性能下降了。

接下来，为了使其更接近 built-in 过滤器，添加了 throws 和 rethrows 声明，因为 built-in 过滤器允许传递抛出异常的闭包.

惊喜（或意外），这就是我得到的：

filter: 11489238
myFilter: 6923719
myFilter not inlined: 9275967
my filter not inlined, with throws: 11956755

最终结论：编译器可以内联函数调用这一事实，加上不支持异常，是您自定义过滤方法性能更好的原因。

以下代码给出的结果与 build-in filter:

非常相似

extension Array {
    @inline(never)
    func myFilter(predicate: Element throws -> Bool) rethrows -> [Element] {
        var filteredArray = [Element]()
        for x in self where try predicate(x) {
            filteredArray.append(x)
        }

        return filteredArray
    }
}

原回答：

Swift 的 filter 应该表现更好，因为：

它可以访问数组的内部状态，而不是强制通过枚举，这意味着至少少了一个函数调用
它可能会优化构建结果数组的方式

#1 可能不会有太大区别，因为函数调用不是很昂贵

#2 另一方面，对于大型数组可能会有很大的不同。向数组追加新元素可能会导致数组需要增加其容量，这意味着分配新内存并复制当前状态的内容。

为什么我的过滤器版本与 Swifts 的表现如此不同？

Why does my version of filter perform so differently than Swifts?

filter

instruments

higher-order-functions

swift

发生了什么

如我所料

我的问题

研究成果

原回答：