Deep dive into Swift’s array
Learn how the swift array works under the hood, and how they can be optimized — working with ContiguousArray, their comparison, etc.
_ContiguousArrayStorage- allocating memory for storing elements, providing quick access by index._ArrayBridgeStorage- an abstraction that allows you to use both native storage and NSArray._ArrayBuffer<T>- implementation of copy on write.Array<T>- public interface.
Growing the size of an Array
Each array reserves a specific amount of memory to store its contents. When you add items to an array and that array begins to exceed its reserved capacity, the array allocates a large amount of memory and copies its items to a new vault, where the new vault is many of the sizes of the old vault.
This exponential growth strategy means that appending an element happens in constant time, averaging the performance of many append operations. Append operations that trigger reallocation have a performance cost, but they occur less and less often as the array grows larger.
Example: Create an array with 10 elements.
Swift will allocate enough capacity for this array to store only these 10 elements, so both array.capacity and array.count will be equal to 10.
var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(array.capacity) // 10
print(array.count) // 10Let’s add 11 and 12 elements. Array does not have the capacity for this, so it needs to free up space — it will find memory to store more elements, copy the array there, and then add 11 and 12 elements. The execution time of these inserts is complex — O(n), where n is the number of elements in the array.
array.append(11)
array.append(12)
print(array.capacity) // 20
print(array.count) // 12Thus, when you add 11 and 12 elements to an array with a capacity of 10, swift creates an array with a size of 20. And when we exceed this size, the next capacity will be 40, then 80, sweat 160, and so on.
If you know approximately how many items you want to save, use the reserveCapacity(_:). This will allow you to avoid intermediate redistributions.
Use the capacity and count properties to determine how many elements an array can store without allocating large resources.
var stringArray = Array<String>()
stringArray.reserveCapacity(128) If your array’s Element type is a class or @objc protocol and you do not need to bridge the array to NSArray or pass the array to Objective-C APIs, using ContiguousArray may be more efficient and have more predictable performance than Array. If the array's Element type is a struct or enumeration, Array and ContiguousArray should have similar efficiency.
The ContiguousArray type is a specialized array that always stores its elements in a contiguous region of memory. This contrasts with Array, which can store its elements in either a contiguous region of memory or an NSArrayinstance if its Element type is a class or @objc protocol.
Array will be contiguously stored:
- Arrays created in Swift will always be contiguously stored;
- Arrays of structs and enums will always be contiguously stored;
- Arrays on platforms without an Objective-C runtime (i.e. non-Darwin platforms) are always contiguously stored;
- The only time an array won’t be contiguously stored is if it is of classes and has been bridged from an
NSArray - Even then, in many cases, the
NSArraywill be contiguously stored and can present a pointer at no or amortized cost
Comparison of Array and ContiguousArray
import Foundation
protocol Possibles {
init(repeating: Bool, count: Int)
subscript(index: Int) -> Bool { get set }
var count: Int { get }
}
extension Array: Possibles where Element == Bool {}
extension ContiguousArray: Possibles where Element == Bool {}
func lazySieveOfEratosthenes<Storage: Possibles>(makeStorage: () -> Storage) -> [Int] {
var possibles = makeStorage()
let limit = possibles.count - 1
return (2 ... limit).lazy.filter { i in // Lazy, so that `possibles` is updated before it is used.
possibles[i]
}.map { i in
stride(from: i * i, through: limit, by: i).lazy.forEach { j in
possibles[j] = false
}
return i
}.reduce(into: [Int]()) { (result, next) in
result.append(next)
}
}
func forSieveOfEratosthenes<Storage: Possibles>(makeStorage: () -> Storage) -> [Int] {
var possibles = makeStorage()
let limit = possibles.count - 1
var result = [Int]()
for i in 2 ... limit where possibles[i] {
var j = i * i
while j <= limit {
possibles[j] = false
j += i
}
result.append(i)
}
return result
}
func test(_ name: String, _ storageType: String, _ function: (Int) -> [Int]) {
let start = Date()
let result = function(100_000)
let end = Date()
print("\(name) \(storageType) biggest: \(result.last ?? 0) time: \(end.timeIntervalSince(start))")
}
test("for ", "Array ") { limit in
forSieveOfEratosthenes {
Array(repeating: true, count: limit + 1)
}
}
test("for ", "ContiguousArray") { limit in
forSieveOfEratosthenes {
ContiguousArray(repeating: true, count: limit + 1)
}
}
test("lazy ", "Array ") { limit in
lazySieveOfEratosthenes {
Array(repeating: true, count: limit + 1)
}
}
test("lazy ", "ContiguousArray") { limit in
lazySieveOfEratosthenes {
ContiguousArray(repeating: true, count: limit + 1)
}
}Result:
for Array biggest: 99991 time: 41.016937017440796
for ContiguousArray biggest: 99991 time: 40.648478984832764
lazy Array biggest: 99991 time: 3.3549970388412476
lazy ContiguousArray biggest: 99991 time: 3.5851539373397827Another one:
for Array biggest: 99991 time: 41.801795959472656
for ContiguousArray biggest: 99991 time: 42.37710893154144
lazy Array biggest: 99991 time: 3.438219904899597
lazy ContiguousArray biggest: 99991 time: 3.4085270166397095The launch was done on a laptop with the following configuration:
- macOS Monterey (Version 12.3)
- Processor 2.3 GHz 8-Core Intel core i9
- Memory 16 GB DDR4
- Xcode Version 13.3.1 (13E500a), Playground
An example of the code is taken from here, I advise you to look at the whole thread. As you can see, Array is not always slower than ContiguousArray.
ContiguousArray turned out to be slower than Array, I found only such a small message, but do not take these words as dogma, since the code above turned out to be inaccurate somewhere 🤔Array with classes
If the elements in the Array are instances of the class, the semantics are the same, although they may look different at first. In this case, the values stored in the array are references to objects outside the array. When you change an object reference in a single array, only that array has a reference to the new object. Yet, if two arrays contain references to the same object, you can observe changes in the properties of that object from both arrays.
class MyClass {
var name = "Name"
}
var firstArray = [MyClass(), MyClass()]
var secondArray = firstArray
firstArray[0].name = "Another Name"
print(firstArray[0].name) // "Another name"
print(secondArray[0].name) // "Another name- Replacements, additions, and deletions have scope only for the array to which the actions apply:
firstArray[0] = MyClass()
print(firstArray[0].name) // "Name"
print(secondArray[0].name) // "Another nameBig-O Algorithm Complexity with operations:
- O (1) — Constant time (fastest). Access to an element in an array by its index:
let array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
array[3]- O(n log n) — Logarithmic time (slightly worse than constant time). Sorting in ascending order, standard function:
var people = ["Sandra", "Mike", "James", "Donald"]
people.sort()- O(n) — Linear time (slightly worse than logarithmic complexity). Counting the sum of elements using the standard function forEach:
let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
var sumOfNumbers = 0
numbers.forEach {
sumOfNumbers += $0
}
print(sumOfNumbers) // 55- O(n ²) — Quadratic time (slightly worse than O (n log n). Traversing a 2D array:
var twoDimensionalArray = [["first one", "second one"], ["first two", "second two"], ["first third", "second third"]]
for i in 0..<twoDimensionalArray.count {
for n in 0..<twoDimensionalArray[i].count {
print(twoDimensionalArray[i][n])
}
}Conclusion
Arrays in Swift are a good data type for organizing an ordered collection where you can store a variety of elements, but remember semantics with value and reference types. You can perform a variety of operations (add, delete and etc.), as well as use not only Array but also ContiguousArray, NSArray, ArraySliceand, etc.
Thanks for reading. Make sure to follow me on Medium. Let’s connect on Linkedin too.
Array — is a struct which means it is a value type in Swift. You use arrays to organize your app’s data, Array type to hold elements of a single type, and the array’s Element type.
