Craig Gidney Craig Gidney - 1 year ago 63
Swift Question

Does Swift have quadratic string concatenation when using var?

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
and calling
100 times (i.e. linear cost)?

Or is it akin to creating a series of ever-larger
instances and combining them with
(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 Source

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