A nice little optimization trick for Swift arrays

Swift arrays are value types that allow dynamically storing the arbitrary numbers of values without knowing the exact count at the beginning. Although this is great when you don't know the exact number of elements you're going to store in advance, you can use a nice optimization technique when you already know how many elements you are going to store in the array.

Consider an example of map function on Array where you take an array of integers as input, apply transformation and return the array of transformed elements as the output.

extension Array {
    func myMap<T>(_ transformation: (Element) -> T) -> [T] {
        var output: [T] = []
        
        for element in self {
            output.append(transformation(element))
        }
        return output
    }
}

Here, the transformation could be anything that client wants. For example, if I want to increment every value in the array by 1, I can use myMap as follows,

var input = [100, 200, 300]

var output = input.myMap { $0 + 1 }

// Outputs - [101, 201, 301]

However, when we create an empty array and start adding elements to it, the array grows, and as it grows, it needs to re-allocate its internal storage in order to make a room for accommodating new elements. In a loop like this, we might need to do it multiple times depending on how many elements we need to process. As the number of elements grows, so does the memory operation to re-allocate memory for new elements.

Using reserved capacity

Since we already know that size of input and output arrays are identical, we can reserve the fixed capacity for the output array exactly equal to the size of the input array.  Since we already allocated size, the array doesn't need to re-allocate its internal storage every time it needs to add a new element to the output array. This optimization trick will speed up the operation in the for loop and even significantly for arrays with a large number of elements.

Using ContiguousArray as a storage

The regular array will store elements at non-sequential locations as we keep adding. This is inefficient, as memory access has to jump across addresses that may be far from each other. We can make it even better by using ContiguousArray as a storage unit and later converting it to regular Array before returning it back to the caller

extension Array {
    func myMap<T>(_ transformation: (Element) -> T) -> [T] {
        var output = ContiguousArray<T>()
        output.reserveCapacity(self.count)
        
        for element in self {
            output.append(transformation(element))
        }
        return Array<T>(output)
    }
}

Measuring Performance Win

Now that we have refactor in place, let's measure how much performance win we achieved with this change,

First, let's write a small measure function which will measure how much time is spent in the operation and print it in the console. Second, we will pass both implementations to it to see how much difference do we observe.

| Array size | Naive Implementation  | Improved Implementation  | Difference |
|			 | Avg. time             | Avg. time				| (Seconds)  |
|------------|---------------------------------------------------------------|
| 100000     | 0.02723               | 0.02249                  | 0.00474    |
| 1000000    | 0.21770               | 0.18902                  | 0.02868    |
| 10000000   | 2.20872               | 1.87680                  | 0.33191    |
| 100000000  | 22.63831              | 19.43377                 | 3.20454    |
|------------|---------------------------------------------------------------|

Interestingly, if you look at lower ranges, there isn't much difference, but if we move up with a number of array elements, the processing time grows exponentially and is more pronounced.

I hope it gave you some idea about the benefits of using relatively obscure Swift features to boost the performance of apps at scale. If you have follow-up comments, questions or feedback, please share it on Twitter @jayeshkawli.

Analysis done on Apple Macbook pro with following configuration:
macOS Big sur (Version 11.4)
Processor 2.6 GHz 6-Core Intel core i7
Memory 16 GB DDR4