Does Swift have quadratic string concatenation when using var?

Question

In the Swift Language reference, the String Mutability section says:

You indicate whether a particular line can be changed (or mutated) by assigning it to a variable (in this case it can be changed) or a constant (in this case it cannot be changed)

It is not clear to me whether the variable or the value of the variable it it itable is.

For example, if I write:

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

Is this like creating an NSMutableString and calling appendString 100 times (i.e. linear cost)?

Or is it like creating a series of instances with a higher NSString and combining them with stringByAppendingString (i.e. squared value)?

Or maybe he creates some kind of rope structure behind the scenes, so it is immutable and linear in the aggregate?

Answer 1

Adding to a collection like this (unless String is the collection itself, you essentially add its characters representation with this code) is linear, not quadratic. A line in Swift has an internal buffer, the size of which doubles each time it is filled, which means that you will see fewer and fewer redistributions as you add. The documentation describes the addition in this way as an “amortized” operation O (1): most of the time O (1) is added, but sometimes it needs to reallocate the row storage.

Arrays, sets, and dictionaries have the same behavior, although you can also reserve a specific capacity for the array (using reserveCapacity(_:) ) if you know that you will add many times.

---

All of these collections use copy-on-write to guarantee the semantics of the value. 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 will not require a copy.

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