Vector, a fixed-size array

Evolution Pitches
158

Just to add to this - you can already avoid array copies by using borrow parameters to suppress implicit copying.

Unfortunately, lots of operations require copies when they really shouldn't (like for loops):

// Why do I have to copy an Array to iterate over its contents?

func foo(_ input: borrowing [Float]) {
           `- error: 'input' is borrowed and cannot be consumed

  for _ in input {
           `- note: consumed here
  }
}

For a Vector, this implicit copy (made visible by the explicit borrowing modifier) would create an entirely new buffer and initialise it from the original Vector. So if the vector is very large, the very act of writing a for loop could have a significant implicit performance cost, regardless of what you do in the loop. This is an artefact of the Collection design that will hopefully be remedied by a new protocol. (Actually, this is also a good argument against having Vector conform to Sequence/Collection at all)

The ability to have borrow var variables which we can store and write abstractions around (using lifetime dependencies) will also help avoid copies.

Vector and Array can both benefit from these improvements.

EDIT: To phrase the point on copying another way - currently for loops use consuming iteration, via Sequence's consuming func makeIterator() method.

That works for single-pass sequences, and until now we've been using it for multi-pass collections because we can just copy them and consume the copy. For copy-on-write collections, this is cheap (just a retain/release).

We already know this is insufficient for non-copyable collections, and so we will need to introduce borrowing iteration for them (all collections can already do this via their indexes). The part that is interesting with regards to Vector is that even though it is copyable, because its elements are stored inline the implicit copies necessary for consuming iteration may be surprisingly expensive.

It means every for loop involving a vector will have linear complexity with respect to the length of the vector from that initial copy, even if they break out of the loop body early.

18 Likes