UPGRADE YOUR SKILLS: Learn advanced Swift and SwiftUI on Hacking with Swift+! >>

Array performance: append() vs reserveCapacity()

Sometimes its faster to let Swift figure things out for you

Paul Hudson       @twostraws

If you’re adding lots of items to an array, you might find it more efficient to tell Swift ahead of time how much capacity you need by using the reserveCapacity() method on your collection. However, while this method can indeed make your code faster, if you’re not careful it can also make it a lot, lot slower, so be careful.

First, let’s take a look at how array storage works. If you create an array with four items, Swift will allocate enough capacity for that array to hold only those four items. So, both yourArray.count and yourArray.capacity will be equal to 4.

Now let’s say you want to append a fifth item. The array doesn’t have capacity for that, so it needs to make some space – it will find memory to hold more items, copy the array there, then append the fifth item. This has an O(n) run time, where n is the number of items in the array.

To avoid constant reallocations, Swift uses a geometric growth pattern for array capacities – a fancy way of saying that it increases array capacity exponentially rather than in fixed amounts. So, when you add a fifth item to an array with capacity 4, Swift will create the resized array so that it has a capacity of 8. And when you exceed that you’ll get a capacity of 16, then 32, then 64, and so on – it doubles each time.

Now, if you know ahead of time that you’ll be storing 512 items, you can inform Swift by using the reserveCapacity() method. This allows Swift to immediately allocate an array capable of holding 512 items, as opposed to creating a small array then re-allocating multiple times.

For example:

var randomNumbers = [Int]()
randomNumbers.reserveCapacity(512)

for _ in 1...512 {
    randomNumbers.append(Int.random(in: 1...10))
}

reserveCapacity() also has an O(n) run time based on the number of elements in the array, so you should definitely call it when the array is still empty.

But there’s a catch, and it’s an important one: you need to be sure that your array growth strategy is better than Swift’s. Remember, Swift uses a geometric growth pattern so the need to resize the array decreases as its capacity grows, which means that it has an amortized run time of O(1).

Tip: If you haven’t seen it before, amortization is an accounting term that programmers co-opted to describe how algorithms behave over time. Although append() has a O(n) run time when it has to expand the array capacity, it is O(1) when you already have enough storage. As the array capacity grows the O(1) operations massively outnumber the O(n) operations, so we can say that over time append() is effectively O(1).

So, while append() amortizes to a constant run time, the same is not true of reserveCapacity() – naïve uses will actually make your code slower rather than faster.

For example, let’s say we want track lucky numbers for a lottery. We might start with an empty array:

var allLuckyNumbers = [Int]()

Next, we could write a function that picks 10 numbers so we can play in this week’s lottery. This function knows we’re going to generate 10 numbers, so it’s going to use reserveCapacity() to make sure we have space for 10 new numbers. Finally, it will use Int.random(in:) to generate and append 10 new random numbers.

Here’s that in code:

func pickLuckyNumbers() {
    let newSize = allLuckyNumbers.count + 10
    allLuckyNumbers.reserveCapacity(newSize)

    for _ in 1...10 {
        allLuckyNumbers.append(Int.random(in: 0...50))
    }
}

So far, so good: reserveCapacity() is an O(n) call, and pre-allocating the space makes sense.

However, let’s say you’re really superstitious and wanted to generate a whole year of lucky numbers up front. Here’s that in code:

for _ in 1...52 {
    pickLuckyNumbers()
}

That loop is also O(n), so now we have a problem: the O(n) from reserveCapacity() and the O(n) of our loop combine to make a quadratic run time: O().

Even though using reserveCapacity() can help speed up your code, in this case it will slow you down: Swift will repeatedly resize the array to add 10 more items. On the other hand, if you removed the call to reserveCapacity() Swift would revert to its geometric growth strategy and eventually allocate far more capacity than is needed – it will be much, much quicker than repeatedly adding space for 10 more.

So, the moral of the story is pretty simple: if you’re calling reserveCapacity() once you’re probably doing it right, but if you’re calling it repeatedly then you should either implement your own growth strategy or leave that hard work to Swift.

Hacking with Swift is sponsored by RevenueCat

SPONSORED Take the pain out of configuring and testing your paywalls. RevenueCat's Paywalls allow you to remotely configure your entire paywall view without any code changes or app updates.

Learn more here

Sponsor Hacking with Swift and reach the world's largest Swift community!

BUY OUR BOOKS
Buy Pro Swift Buy Pro SwiftUI Buy Swift Design Patterns Buy Testing Swift Buy Hacking with iOS Buy Swift Coding Challenges Buy Swift on Sundays Volume One Buy Server-Side Swift Buy Advanced iOS Volume One Buy Advanced iOS Volume Two Buy Advanced iOS Volume Three Buy Hacking with watchOS Buy Hacking with tvOS Buy Hacking with macOS Buy Dive Into SpriteKit Buy Swift in Sixty Seconds Buy Objective-C for Swift Developers Buy Beyond Code

Was this page useful? Let us know!

 
Unknown user

You are not logged in

Log in or create account
 

Link copied to your pasteboard.