Initializing arrays quickly in Swift: be wary of Sadun’s initializers

Swift is Apple’s go-to programming language. It is the new default to build applications for iPhones. It also runs well on Linux.

It is not as low-level as C or C++, but it has characteristics that I like. For example, it does not use a “fancy” garbage collector, relying instead on deterministic reference counting. It is also a compiled language. It also benefits from a clean syntax.

Suppose you want to initialize an array in Swift with the values 0, 100, 200… Let us pick a sizeable array (containing 1000 elements). The fastest way to initialize the array in my tests is as follows:

Array((0..<1000).lazy.map { 100 * $0 })

The “lazy” call is important for performance… I suspect that without it, some kind of container is created with the desired values, and then it gets copied back to the Array.

One of the worse approaches, from a performance point of view, is to repeatedly append elements to the Array:

var b = [Int]()
for i in stride(from: 0, to: maxval, by: skip) {
     b.append(i)
}

It is more than 5 times slower! Something similar is true with vectors in C++. In effect, constructing an array by repeatedly adding elements to it is not ideal performance-wise.

One nice thing about Swift is that it is extensible. So while Arrays can be initialized by sequences, as in my code example… they cannot be initialized by “generators” by default (a generator is a function with a state that you can call repeatedly)… we can fix that in a few lines of code.

Erica Sadun proposed to extend Swift arrays so that they can be initialized by generators… Her code is elegant:

public extension Array {
  public init(count: Int, generator: @escaping() -> Element) {
    precondition(count >= 0, "arrays must have non-negative size")
    self.init(AnyIterator(generator).prefix(count))
  }
}

I can use Erica Sadun’s initializer to solve my little problem:

var runningTotal : Int = 0
let b = Array(count: 1000) {() -> Int in
           runningTotal += 100
           return runningTotal
}

How fast is Erica’s initializer?

$ swift build    --configuration release && ./.build/release/arrayinit
append                           6.091  ns
lazymap                          1.097  ns
Erica Sadun                      167.311  ns

So over 100 times slower. Not good.

Performance-wise, Swift is a rather opinionated language: it really wants you to initialize arrays from sequences.

We can fix Erica’s implementation to get back to the best performance:

public extension Array {
  public init(count: Int, generator: @escaping() -> Element) {
    precondition(count >= 0, "arrays must have non-negative size")
    self.init((0..<count).lazy.map { Element in generator() })
  }
}

My source code is available.

2 thoughts on “Initializing arrays quickly in Swift: be wary of Sadun’s initializers”

  1. Hey Daniel, great tips for initializing arrays with Swift. I am just getting started with programming collaboration tools for the iPhone. It’s great to know that you can optimize performance by avoiding appended elements. Your source code is very helpful.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax