NEW! Pre-order my latest book, Testing Swift! >>

Array performance: append() vs reserveCapacity()

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.

 

MASTER SWIFT NOW
Buy Practical iOS 12 Buy Pro Swift Buy Swift Design Patterns Buy Practical iOS 11 Buy Swift Coding Challenges Buy Server-Side Swift (Vapor Edition) Buy Server-Side Swift (Kitura Edition) Buy Hacking with macOS Buy Advanced iOS Volume One Buy Hacking with watchOS Buy Hacking with tvOS Buy Hacking with Swift Buy Dive Into SpriteKit Buy Swift in Sixty Seconds Buy Objective-C for Swift Developers Buy Beyond Code

About the author

Paul Hudson is the creator of Hacking with Swift, the most comprehensive series of Swift books in the world. He's also the editor of Swift Developer News, the maintainer of the Swift Knowledge Base, and Mario Kart world champion. OK, so that last part isn't true. If you're curious you can learn more here.

Was this page useful? Let me know!

Average rating: 5.0/5

Click here to visit the Hacking with Swift store >>