Collection Data Structures in Swift

Common iOS Data Structures

The three most common data structures in iOS are arrays, dictionaries and sets, each of which deserves your attention. In this section, you’ll:

1. Consider how they differ in ideal terms as fundamental abstractions
2. Examine the performance of the actual concrete classes that iOS offers for representing those abstractions.

For the three types, iOS offers multiple concrete classes that work for the same abstraction. In addition to the old Foundation data structures available in Swift and Objective-C, there are new Swift-only versions of data structures that integrate tightly with the language.

Since its introduction, Swift has brought many performance improvements to Swift data structures and now outperforms Foundation data structures in the majority of cases. However, the “best” one to use still depends on the operation you want to perform.

Arrays

An array is a group of items placed in a specific order, and you can access each item via an index — a number that indicates its position in the order. When you write the index in brackets after the name of the array variable, this is subscripting.

Swift arrays are immutable if you define them as constants with let, and mutable if you define them as variables with var.

In contrast, a Foundation NSArray is immutable by default. If you want to add, remove or modify items after creating the array, you must use the mutable variant class NSMutableArray.

An NSArray is heterogeneous, meaning it can contain Cocoa objects of different types. Swift arrays are homogeneous, meaning that each Array is guaranteed to contain only one type of object.

However, you can still define a single Swift Array so it stores various types of Cocoa objects by specifying that the one type is AnyObject, since every Cocoa type is also a subtype of this.

Expected Performance and When to Use Arrays

The primary reason to use an array is when the order of variables matters. Think about those times when you sort contacts by first or last name, a to-do list by date, or any other situation when it’s critical to find or display data in a specific order.

Apple’s documentation includes three key expectations for Array performance in the CFArray header:

1. Accessing any value at a particular index in an array is at worst O(log n), but should usually be O(1).
2. Searching for an object at an unknown index is at worst O(n (log n)), but will generally be O(n).
3. Inserting or deleting an object is at worst O(n (log n)) but will often be O(1).

These guarantees subtly deviate from the simple “ideal” array that you might expect from a computer science textbook or the C language, where an array is always a sequence of items laid out contiguously in memory.

Consider it a useful reminder to check the documentation!

In practice, these expectations make sense when you think about them:

1. If you already know where an item is, then looking it up in the array should be fast.
2. If you don’t know where a particular item is, you’ll need to look through the array from beginning to end. Your search will be slower.
3. If you know where you’re adding or removing an object it’s not too difficult. Although, you may need to adjust the rest of the array afterwards, and that’s more time-consuming.

How well do these expectations align with reality? Keep reading to find out!

Note: Swift officially became open source in December of 2015. You can look through the Swift source code yourself to see how these data structures are implemented under the hood!

Sample App Testing Results

Download the sample project and open it in Xcode. It’s time to play around with testing methods that will create and/or test an array and show how long it took to perform each task.

Note: In the app, the Debug configuration automatically sets optimization to a level equal to the release configuration — this is so that when you test the application you get the same level of optimization you’d see in the real world.

You need a minimum of 1000 items to run tests with the sample app, so that results are large enough to detect. When you build and run, the slider will be set to 1000. Press the Create Array and Test button, and you’ll be testing in no time:

Drag the slider over to the right side until it hits 10,000,000, and press Create Array and Test again to see the difference in creation time with a significantly larger array:

These tests were run against an iPhone 7 running iOS 10.0 from Xcode 8.0, which includes Swift 3.0. With 10,000 times as many items, creating the array only takes about 1,537 times as much time.

In this case, for around 106.5 times the number of items, it took roughly 1,649 times as much time to create the array. Any more than a few dozen items, and this was unusable.

Since the dark days of old, Swift has made tremendous performance improvements and you can now easily make huge arrays with few problems!

What about NSMutableArray? You can still call Foundation classes from Swift without having to drop back down to Objective-C.

Take a look inside the DataManipulators folder in Xode. Here you’ll find the various objects that handle the work of setting up the array and performing the various tasks that are then timed. You’ll notice there is a class called SwiftArrayManipulator. This conforms to ArrayManipulator which is where the methods are defined that the timing code uses.

There is also a class called NSArrayManipulator that also conforms to ArrayManipulator. Because of this, you can easily swap in an NSMutableArray for a Swift Array. The project code is simple enough that you can try an NSMutableArray with a single line change to compare the performance.

Open ArrayViewController.swift and change line 27 from:

let arrayManipulator: ArrayManipulator = SwiftArrayManipulator()

To:

let arrayManipulator: ArrayManipulator = NSArrayManipulator()

Build and run again, and press Create Array and Test to test the creation of an NSMutableArray with 1000 items:

…and then again with 10,000,000 items:

Raw performance for creation is 30 times slower than Swift. Some of that may come from the need to jockey between objects that can be stored in an NSArray and its Swift counterparts. This is a substantial improvement since Swift 2.3 when they were roughly the same.

However, you only create an array once, and you perform other operations on it far more often, such as finding, adding, or removing objects.

In more exhaustive testing, such as when you’re using some of Xcode 8’s performance testing methods to call each of these methods 50 times, patterns begin to emerge:

• Creating a Swift Array and an NSArray degrade at roughly the same rate between O(log n) and O(n). Swift is faster than Foundation by roughly 30 times. This is a significant improvement over Swift 2.3, where it was roughly the same as Foundation!
• Adding items to the beginning of an array is considerably slower in a Swift Array than in an NSArray, which is around O(1). Adding items to the middle of an array takes half the time in Swift Array than in an NSArray. Adding items to the end of a Swift Array, which is less than O(1), is roughly 6 times faster than adding items to the end of an NSArray, which comes in just over O(1).
• Removing objects is faster in a Swift Array than a NSArray. From the beginning, middle or end, removing an object degrades between O(log n) and O(n). Raw time is better in Swift when you remove from the beginning of an Array, but the distinction is a matter of milliseconds.
• Looking up items in Swift is faster for the first time since its inception. Look ups by index grow at very close rates for both Swift arrays and NSArray while lookup by object is roughly 80 times faster in Swift.