Does Swift have quadratic string concatenation when using var?

Question

In the Swift Language Reference, under String Mutability it says:

You indicate whether a particular String can be modified (or mutated) by assigning it to a variable (in which case it can be modified), or to a constant (in which case it cannot be modified)

It's unclear to me if the "it" that is mutable is the variable or the value.

For example, if I write:

var s = ""
for i in 0...100 {
  s += "a"
}

Is it akin to creating an NSMutableString and calling appendString 100 times (i.e. linear cost)?

Or is it akin to creating a series of ever-larger NSString instances and combining them with stringByAppendingString (i.e. quadratic cost)?

Or perhaps it creates some kind of rope structure behind the scenes, so it's immutable and linear in aggregate?

Answer 1

Appending to a collection like this (while String is not itself a collection, you're essentially appending to its characters view with that code) is linear, not quadratic. A string in Swift has an internal buffer whose size is doubled whenever it fills up, which means you will see fewer and fewer reallocations as you repeatedly append. The documentation describes appending in this way as an "amortized" O(1) operation: most of the time appending is O(1), but occasionally it will need to reallocate the string's storage.

Arrays, sets, and dictionaries have the same behavior, although you can also reserve a specific capacity for an array (using reserveCapacity(_:)) if you know you'll be appending many times.

---

All these collections use "copy-on-write" to guarantee value semantics. Here, x and y share a buffer:

let x = "a"
let y = x

If you mutate x, it gets a new, unique copy of the buffer:

x += "b"
// x == "ab"
// y == "a"

After that, x has its own buffer, so subsequent mutations won't require a copy.

x += "c"   // no copy unless buffer is full