Why Does My Version of Filter Perform So Differently Than Swifts

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

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.

Is Array.filter cheaper than loop?

to put it simply, it is a loop, it's really just syntactic sugar to make your code cleaner

let stuff = ["asdf", "asdf", ""]

var things: [String] = []

for item in stuff {
    if(!item.isEmpty) {
        things.append(item)
    }
}

is functionally identical to:

let stuff = ["asdf", "asdf", ""]
var things = stuff.filter{!$0.isEmpty}

6 lines down to 1.

It's possible that there may be some compiler optimizations that are done due to the type safety and predictability, though according to this: depending on your implementation your performance can vary:

enter link description here

Multiple filters for the same searchBar and ignoring the oder in Swift 5

You can use a recursive search, where the matches from the first search are passed to the next search which searches only those matches for the next search term. This continues for each search term and then return only the remaining matches.

I've put it into an example which can be run from a playground so you can have a play and see how it works.

You can (and should) add an optimisation to it so the search terminates early if there are no remaining matches, but I'll leave that as an exercise for you as it will help you understand how the recursive search is working. Discuss in comments if you need help.

I also removed some temporary variables (the lowercased versions) which weren't needed, and the use of recursion means only one filter is used.

import UIKit

class Clinic: CustomStringConvertible {
    var id = ""
    var name = ""
    var address = ""
    var specialty1 = ""
    var specialty2 = ""
    var description: String {
        get { return "Name: \(name) Sp1: \(specialty1) Sp2: \(specialty2)"}
    }
    init(data: [String]) {
        id = data[0]
        name = data[1]
        address = data[2]
        specialty1 = data[3]
        specialty2 = data[4]
    }
}
var clinics = [
    Clinic(data: ["1","First Clinic","First Street","head","feet"]),
    Clinic(data: ["2","Second Clinic","Second Street","legs","feet"]),
    Clinic(data: ["3","Third Clinic","Third Street","head","legs"])
]

// recursive search: search remaining clinics with remaining searches
func search(searchClinics: [Clinic], searchArr: [String]) -> [Clinic] {
    var searchArr = searchArr
    // base case - no more searches - return clinics found
    if searchArr.count == 0 {
        return searchClinics
    }
    // itterative case - search clinic with next search term and pass results to next search
    let foundClinics = searchClinics.filter { item in
        item.name.lowercased().contains(searchArr[0]) ||
        item.specialty1.lowercased().contains(searchArr[0]) ||
        item.specialty2.lowercased().contains(searchArr[0])
    }
    // remove completed search and call next search
    searchArr.remove(at: 0)
    return search(searchClinics: foundClinics, searchArr: searchArr)
}

let searchArr = "cli le".lowercased().components(separatedBy: " ")
let foundClinics = search(searchClinics: clinics, searchArr: searchArr)
foundClinics.map() {print($0)}
// Outputs:
// Name: Second Clinic Sp1: legs Sp2: feet
// Name: Third Clinic Sp1: head Sp2: legs

Limit the results of a Swift array filter to X for performance

The fastest solution in terms of execution time seems to be an
explicit loop which adds matching elements until the limit is reached:

extension Sequence {
    public func filter(where isIncluded: (Iterator.Element) -> Bool, limit: Int) -> [Iterator.Element] {
        var result : [Iterator.Element] = []
        result.reserveCapacity(limit)
        var count = 0
        var it = makeIterator()

        // While limit not reached and there are more elements ...
        while count < limit, let element = it.next() {
            if isIncluded(element) {
                result.append(element)
                count += 1
            }
        }
        return result
    }
}

Example usage:

let numbers = Array(0 ..< 2000)
let result = numbers.filter(where: { $0 % 3 == 0 }, limit: 5)
print(result) // [0, 3, 6, 9, 12]

Swift 3 - filter tableview from different view controller

You can do this with an unwind segue from your second view controller's buttons back to your table view controller.

In your table view controller, say,

func unwindToTableView(_ segue: UIStoryboardSegue) {

    switch segue.identifier {
        case "FilterNames":
            filterByName()
        etc…
    }    
}

or you could have different unwind funcs for each filter…

func unwindAndFilterName(_ segue: UIStoryboardSegue) {
    filterByName()
}

etc

To hook up an unwind segue, just add the method to your table view controller, then in your storyboard, drag from the button on the second view controller to it's Exit icon. The segue func should appear in the list

Applying Filters to image swap height and width in swift

This is likely happening because your input image has a different orientation (portrait) then the natural orientation of your camera (landscape).

If you ask an UIImage for its size, it already factors in its orientation. Under the hood, though, the image data is stored as it came from the camera, and that's also what Core Image is operating on. So in your filter chain, the image is loosing its orientation information.

I think you can fix that by passing that information to the output image on creation:

let inputImage = AppDelegate.captured_iamge!
//...
let img = UIImage(cgImage: filtered_img_ref!, scale: inputImage.scale, orientation: inputImage.orientation)

Creating the most efficient custom filter function (for my use case)

If the types to check are only String or Int create a custom protocol to constrain the value type to String or Int

protocol StringOrInt {}
extension Int : StringOrInt {}
extension String : StringOrInt {}

Then create a Filter struct with a keyPath, a value of StringOrInt and a ComparisonResult which is a common type for <, > and ==

struct Filter {
    let value : StringOrInt
    let keyPath : PartialKeyPath<Movie>
    let ordered : ComparisonResult
}

To filter items create an array of Filter

let filters = [Filter(value: 10, keyPath: \Movie.price, ordered: .orderedAscending),
               Filter(value: "Action", keyPath: \Movie.genre, ordered: .orderedSame)]

This will filter all movies with a price < 10 and genre == "Action"

---

Finally create a filterMovies function which applies the filters to the Movie items in the filter function of Standard Library. The Int values are converted to NSNumber to be able to use compare and compare against the given ComparisonResult

func filterMovies(_ movies : [Movie], by criteria : [Filter]) -> [Movie] {
    return movies.filter { movie -> Bool in
        for filter in criteria {
            let value = filter.value
            if let stringValue = value as? String {
                if (movie[keyPath: filter.keyPath] as! String).compare(stringValue) != filter.ordered { return false }
            } else if let intValue = value as? Int {
                let numValue = NSNumber(value: intValue)
                let movieInt = movie[keyPath: filter.keyPath] as! Int
                if (NSNumber(value: movieInt)).compare(numValue) != filter.ordered { return false }
            } else { return false }
        }
        return true
    }
}

---

Related Topics