CODEWITHSUNDEEP
swiftperformancefunctional-programming
akbsteam
akbsteam

Reputation: 253

Improving performance of higher order functions vs loops in Swift (3.0)

import XCTest

class testTests: XCTestCase {
    static func makearray() -> [Int] {
        var array: [Int] = []
        for x in 0..<1000000 {
           array.append(x)
        }
        return array
    }

    let array = testTests.makearray()

    func testPerformanceExample() {
        self.measure {
            var result: [String] = []
            for x in self.array {
            let tmp = "string\(x)"
            if tmp.hasSuffix("1234") {
                result.append(tmp)
            }
        }
        print(result.count)
    }
}

func testPerformanceExample2() {
    self.measure {
        let result = self.array.map { "string\($0)" }
                               .filter { $0.hasSuffix("1234") }
        print(result.count)
    }
}

func testPerformanceExample3() {
    self.measure {
        let result = self.array.flatMap { int -> String? in
            let tmp = "string\(int)"
            return tmp.hasSuffix("1234") ? tmp : nil
        }
        print(result.count)
    }
}
}

In this code I am trying to see how the higher order functions perform with respect to processing a large array.

The 3 tests produce the same results with times of around 0.75s for loop, 1.38s map/filter, 1.21s flatmap.

Assuming HOFs are, more or less, functions wrapping loops, this makes sense as in the map/filter case, it is looping through the first array for map, then looping through the result of that to filter.

In the case of flatmap, is it doing the map first, and then able to do a simpler filter operation?

Is my understanding of what is happening under the hood (roughly) correct?

If so, would it be fair to say that the compiler is not able to do much optimisation of this?

And finally, is there a better way of doing this? The HOF versions are definitely easier for me to understand, but for performance critical areas, it looks like for-loops are the way to go?

Upvotes: 3

Views: 1724

Answers (2)

conhanley
conhanley

Reputation: 1

Technically speaking, these HOF could have better Big O performance if the compiler substituted an implementation that used multiple cores in parallel. However, Swift does not do this at this time. A step further would be using granularity control to use an iterative or parallel implementation appropriately, based on weighing the overhead costs of parallelization vs. the input size:

https://en.wikipedia.org/wiki/Granularity_(parallel_computing)

Upvotes: 0

Daniel Lemire
Daniel Lemire

Reputation: 3618

The flatmap approach is likely to be nearly equivalent to the loop approach. Algorithmically, it is equivalent. I would add that even the map/filter approach, in this instance, should be "nearly" as fast because the bulk of the running time in taken by the operations on strings.

For good performance, one wants to avoid working with temporary strings. We can achieve the desired result as follows...

func fastloopflatmap (_ test_array: [Int]) -> [String] {
   var result: [String] = []
    for x in array {
      if x % 10000 == 1234 {
          result.append("string\(x)")
      }
    }
    return result;
}

Here are my timings :

loop        : 632 ns/element
filter/map  : 650 ns/element
flatmap     : 632 ns/element
fast loop   : 1.2 ns/element

Thus, as you can see, the bulk (99%) of the running time of the slow functions is due to the operation over temporary strings.

Source code : https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/tree/master/extra/swift/flatmap

Upvotes: 3

Related Questions