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

Question

As an exercise I've rewritten a few of Swift's higher order functions, one being .filter. I decided to measure my version of .filter against Swift's using instruments and I'm rather confused about the results.

Here's what my version of filter looks like, which I admit may be incorrect.

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

        return filteredArray
    }
}

What Happened

My Filter

• Overall CPU consumption: 85.7%
• My Filter's consumption: 67.9%

Swift's Filter

• Overall CPU consumption: 57.7%
• My Filter's consumption: 70.9%

What I expected

I expected similar performance. I'm confused why my filter function call itself would consume less CPU yet my overall application CPU is nearly 30% higher.

My Question

If I've written filter wrong, please help me to understand my error(s). Otherwise please point out why Swift's filter reduces CPU load by 30% over mine.

Answer 1

Ok, so after reading all posted comments, I decided to also benchmark, and here are my results. Oddly enough, the built-in filter seems to perform worse than a custom implementation.

TL;DR; Because your function is short, and the compiler has access to it source code, the compiler inlines the function call, which enables more optimisations.

Another consideration is as your myFilter declaration doesn't take into consideration exception throwing closures, thing that the built-in filter does.

Add @inline(never), throws and rethrows to your myFilter declaration and you'll get similar results as for the built-in filter

Research results

I used mach_absolute_time() to obtain accurate times. I didn't converted the results to seconds as I was merely interested in comparison. Tests were run on Yosemite 10.10.5 with 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{ $0 % 2 == 0}
var end = mach_absolute_time()
print("filter:         \(end-start)")

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

In debug mode, filter is faster than myFilter:

filter:         370930078
myFilter:       479532958

In release, however, myFilter is much better than filter:

filter:         15966626
myFilter:       4013645

What's even more strange is that an exact copy of the built-in filter (taken from Marc's comment) behaves better than the built-in one.

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{ $0 % 2 == 0}
end = mach_absolute_time()
print("originalFilter: \(end-start)")

With the above code, my benchmark app gives the following output:

filter:         13255199
myFilter:       3285821
originalFilter: 3309898

Back to debug mode, the 3 flavours of filter give this output:

filter:         343038057
myFilter:       429109866
originalFilter: 345482809

filter and originalFilter give very close results. Which makes me think that Xcode is linking against the debug version of Swifts stdlib. However when build in release, Swifts stdlib performs 3 times better than in debug, and this confused me.

So the next step was profiling. I hit Cmd+I, set the sample interval to 40us, and profiled the app two times: one when only the filter call was enabled, and one with myFilter enabled. I removed the printing code in order to have a stack-trace as clean as possible.

Built-in filter profiling:
_{(source: cristik-test.info)}

myFilter:

Eureka!, I found the answer. There's no track of the myFilter call, meaning that the compiler inlined the function call, thus enabling extra optimizations that give a performance boost.

I added the @inline(never) attribute to myFilter, and it's performance degraded.

Next, to make it closer to the built-in filter was to add the throws and rethrows declaration, as the built-in filter allows passing closures that throw exceptions.

And surprise (or not), this is what I got:

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

Final conclusion: the fact that the compiler can inline the function call, combined with lack of support for exceptions was responsible for the better performance of your custom filtering method.

The following code gives results very similar to the 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
    }
}

Original answer:

Swift's filter should perform better, because:

1. it has access to the internal state of the array and is not forced to go through the enumeration, which means at least one less function call
2. it might optimize the way it builds the result array

#1 might not give much difference, as function calls are not very expensive

#2 on the other hand might make a big difference for large arrays. Appending a new element to the array might result in the array needing to increase its capacity, which implies allocating new memory and copying the contents of the current state.