How to efficiently append items to large arrays in Swift?

user_13149109 0
Viewed 478

I am working on a Swift project the involves very large dynamically changing arrays. I am running into a problem where each successive operation take longer than the former. I am reasonably sure this problem is caused by appending to the arrays, as I get the same problem with a simple test that just appends to a large array.

My Test Code:

import Foundation

func measureExecution(elements: Int, appendedValue: Int) -> Void {
    var array = Array(0...elements)
    //array.reserveCapacity(elements)
    
    let start = DispatchTime.now()
    array.append(appendedValue)
    let end = DispatchTime.now()
    print(Double(end.uptimeNanoseconds - start.uptimeNanoseconds) / 1_000_000_000)
}

for i in 0...100 {
    measureExecution(elements: i*10000, appendedValue: 1)
}

This tries for a 100 different array sizes between 10000 and 1000000, timing how long it take to append one item to the end of the array. As I understand it, Swift arrays are dynamic arrays that will reallocate memory geometrically (it allocates more and more memory each time it needs to reallocate), which Apple's documentation says should mean appending a single element to an array is an O(1) operation when averaged over many calls to the append(_:) method (source). As such, I don't think memory allocation is causing the issue.

However, there is a linear relationship between the length of the array and the time it takes to append an element. I graphed the times for a bunch of array lengths, and baring some outliers it is pretty clearly O(n). I also ran the same test with reserved capacity (commented out in the code block) to confirm that memory allocation was not the issue, and I got nearly identical results: Graph of array length and append time

How do I efficiently append to the end of massive arrays (preferably without using reserveCapacity)?

dynamic-arrays swift arrays
1 Answers

From what I've read, Swift arrays pre-allocate storage. Each time you fill an Array's allocated storage, it doubles the space allocated. That way you don't do a new memory allocation that often, and also don't allocate a bunch of space you don't need.

The Array class does have a reserveCapacity(_:). If you know how many elements you are going to store you might want to try that.

user_2051850
Related