Higher-Order Inline Function Performance vs Swift For-In Loop

The most popular higher order functions are map, filter and reduce. We all use them because we think the syntax is much better and it’s even faster to write than the old for-in loop way. But is it really so? Have you ever thought about the performance of these built-in functions? They are built-in, so naturally they should be better, right? Let’s dive into these features together to find out if that’s really the case.

Prerequisites

• Data size 10,000,000 elements

• Each test case was executed 30 times

• The median rather than the mean was used to represent each test case to ensure that the result is not affected by outliers.

Data

Here’s what the data looks like: there are two arrays. One is an array fahrenheitwhich represents 1D an array of uniformly distributed random numbers from the range <32.0;113.0> and the following array, fahrenheitswhich represents 2D array of arrays of uniformly distributed random numbers from the range <32.0;113.0>.

let elementsCount = 10_000_000
let fahrenheit = Array(repeating: 0.0, count: elementsCount).map { _ -> Double in
    return Double.random(in: 32.0 ... 113.0)
}

var fahrenheits = [[Double]]()
for _ in 0 ..< totalElements {
    fahrenheits.append(Array(repeating: 0.0, count: 1).map { _ -> Double in
        return Double.random(in: 32.0 ... 113.0)
    })
}

Function: Map

Let’s start with a simple example. We have an array fahrenheit, and we want to convert each of its elements to degrees Celsius. Therefore, we are going to compare the performance of the function map with cycle for-in.

// Swift
let celsius = fahrenheit.map { (degreesFahrenheit) -> Double in
	return (degreesFahrenheit - 32.0) / 1.8
}

// For-in loop
var celsius = [Double]()
for degreesFahrenheit in fahrenheit {
	celsius.append((degreesFahrenheit - 32.0) / 1.8)
}

Performance

As can be seen from the figure, the built-in map function is much faster than a for-in loop. To be precise, 1.63 times faster. Of course, we should use the built-in map function.

Static and dynamic array.

I didn’t choose to allocate an array with a predefined size because there is no performance difference between a static and dynamic allocated array. I did a quick test and here is the result. It’s a little surprising.

Function: Filter

The next function is filter. So let’s filter out “cold degrees”.

Why do I call them cold? I consider temperatures less than or equal to 20 degrees Celsius (68 degrees Fahrenheit) to be cold, and that’s the reason I named the variable colds.

// Swift
let colds = fahrenheit.filter { (degreesFahrenheit) -> Bool in
    return degreesFahrenheit <= 68.0
}

// For-in loop
var colds = [Double]()     
for degreesFahrenheit in fahrenheit {
    if degreesFahrenheit <= 68.0 {
        colds.append(degreesFahrenheit)
    }
}

Performance

The difference between the built-in filter function and the for-in loop is not so obvious in this case. The inline function is slightly faster (1.11x) than the for-in loop. In any case, it is still faster, so it makes sense to use it.

Function: Reduce

Last function – reduce. To do this, add all the numbers together. For example, we can use the result to calculate the average temperature.

// Swift
let sum = fahrenheit.reduce(0.0) { (result, degreesFahrenheit) -> Double in
    return result + degreesFahrenheit
}

// For-in loop
var sum: Double = 0.0
        
for degreesFahrenheit in fahrenheit {
    sum += degreesFahrenheit
}

Performance

The result is a bit surprising. The built-in reduce function is slightly slower than the for-in loop. The built-in reduce function in a for-in loop is 1.05 times faster.

Feature: FlatMap

Before we look at the chain of functions, let’s compare the function flatMap with a for-in loop. We have an array fahrenheits from double arrays and we want to make a double array.

// Swift
let fahrenheit = fahrenheits.flatMap({ (fahrenheit) -> [Double] in
    return fahrenheit
})

// For-in loop
var fahrenheit = [Double]()
        
for lFahrenheit in fahrenheits {
    fahrenheit.append(contentsOf: lFahrenheit)
}

Performance

The result is very similar to the reduce function. The built-in flatMap function is slightly slower than the for-in loop. The built-in flatMap function in a for-in loop is 1.06 times faster.

Chain (map+filter+reduce)

It’s time for more fun. As we have seen so far, built-in functions are faster or slightly slower than a custom for-in loop. Let’s say we want to convert Fahrenheit to Celsius, then filter the cold temperature, then add up all the filtered numbers.

This means that at the beginning we have an array of numbers fahrenheitthen the function is called mapthen the function is called filterthen the function is called reduce.

// Swift
let sum = fahrenheit.map({ (degreesFahrenheit) -> Double in
    return (degreesFahrenheit - 32.0) / 1.8
}).filter({ (degreesCelsius) -> Bool in
    return degreesCelsius <= 20.0
}).reduce(0.0) { (result, degreesCelsius) -> Double in
    return result + degreesCelsius
}

// For-in loop
var sum: Double = 0.0
        
for degreesFahrenheit in fahrenheit {
    let degreesCelsius = (degreesFahrenheit - 32.0) / 1.8
    if degreesCelsius <= 20.0 {
        sum += degreesCelsius
    }
}

Performance

Oops, as we can see in the photo, there is a problem.

The custom for-in loop is 2.37 times faster. When we use chaining, we should avoid built-in functions and write a custom solution with a for-in loop.

We may ask: “Why is this happening?”, “What’s wrong with the chain of functions?”.

I think it’s obvious what’s going on. When we chain functions, we have to iterate over each result of the previous function. In computer science there is time complexitywhich describes the amount of time required to execute the algorithm.

In our case, at the beginning we have an array fahrenheitand we call the function map. At this point, the complexity is O(n), linear time, where n – array size fahrenheit. We then apply the result of the function map to function filter. Function Complexity filter is also equal to O(n). At the moment, the total time complexity is O(2n). The last step is the function reduce. We apply the result of the function filter to function reduce. The complexity of the reduce function is again O(n), because the notation O is an upper bound on the growth rate of the function. In other words, at worst case function result filter may be O(n) which means that nothing was filtered and this result is used as the input of the function reduce. As a result, the time complexity is O(3n).

However, if we use a loop for-in, then we can perform all the necessary actions (map. filter, reduce) in one for-in loop. Due to this fact, the complexity of the for-in loop ends up being O(n).

Map, Filter and Reduce in RxSwift

For comparison, consider the same example in RxSwift. We will use the functions map, filter and reduceas in the previous example.

Observable.from(fahrenheit)
    .map({ (degreesFahrenheit) -> Double in
        return (degreesFahrenheit - 32.0) / 1.8
    })
    .filter({ (degreesCelsius) -> Bool in
        return degreesCelsius <= 20.0
    })
    .reduce(0.0, accumulator: ({ (result, degreesCelsius) -> Double in
        return result + degreesCelsius
    }))
    .subscribe(onNext: { sum in
        print(sum)
    })
    .disposed(by: disposeBag)

performance

Oh, that’s not good at all!

As you can see from the figure, RxSwift is much slower than the built-in functions and the for-in loop. Inline function solving is 5.14 times faster than RxSwift and for-in loop solving is 12.21 times faster than RxSwift.

You are welcomedon’t use RxSwift if you need to work with a huge amount of data!

Conclusion

According to test cases, there is nothing wrong with using high order functions as long as we do NOT need to chain them. Performance is much better (1.63x faster) when using the built-in map function, or slightly better/worse when using the built-in filter/reduce.

If we need chains of high-order functions, we should consider not using them and implementing them as a for-in solution. The performance is much better, 2.37 times (in the examples in this article) than the built-in functions.

There is no need to always use modern elements, structures, or features of a modern language just because the syntax looks better or everyone uses it. Time and space complexity is much more important than modern syntax, and in the end, fashionable syntax does not make us better developers, although it may seem so to us.

More stories, implementation approaches, and tools for the iOS developer can be found at author’s channel about iOS development.