Vector, a fixed-size array

[Lucca-mito (Lucca de Mello)]

+1 on the pitch; personally, I’m most excited to use the proposed type (alongside a similar one for matrices) for type-safe linear algebra.

The naming has been suficiently discussed, but I’ll add that the similarity between it and C++’s std::vector (or Rust’s std::vec) may not be a bad thing; hear me out. Swift arrays, being dynamically sized, are analogous to vectors in C++/Rust. So let’s imagine that we now do the opposite, naming the proposed Swift collection — which, being fixed-size, is analogous to C++/Rust arrays — Vector. Then it would be easy to explain to people coming from C++ or Rust, and for anyone to remember, that the meanings of “array” and “vector” are simply flipped between Swift and C++/Rust. But if we name the proposed type FixedSizeArray, then the explanation is that a Swift Array is a C++/Rust vector but a C++/Rust array is a Swift FixedSizeArray… awkward and less memorable.

As for whether the name Vector is “correct” from a math perspective: I think it absolutely is, and in fact is more appropriate for fixed-size collections than for dynamically-sized ones. In linear algebra, vectors of a given vector space do have a fixed number of dimensions/components: you can’t have a vector space containing both the 2D vector (2, 3) and the 3D vector (2, 3, 5). So the Swift type Vector<3, Double> would correspond to the 3-dimensional vector space over Double, while the dynamically-sized vector types of other languages don’t map to mathematical vectors at all.

And I can’t help but chime in on an even less important aspect, the name of the integer parameter. I wouldn’t want to spam the same bikeshedding on every pitch related to integer generic parameters, but the points here are especially relevant to the proposed type’s Count parameter.

[dimi (Dimitri Bouniol)]

@jcarrillo7

In some cases the term "vector" is used in computing to refer to an array, although tuples rather than vectors are the more mathematically correct equivalent.

For the most part, this type is primarily intended to replace tuple usage while extending their capabilities as a generic collection type — I'd therefore like to propose HomogenousTuple as a potential name here that would be universally unambiguous given what is trying to be achieved. For instance, if it held Strings: HomogenousTuple<16, String>

[tera]

+1

A minor thing:

@Alejandro

 // This is a stack allocation, no 'malloc's or reference counting here!
  let elements: Vector<4, Int> = [1, 2, 3, 4]

This type also serves as a safer replacement to withUnsafeTemporaryAllocation
when the amount of things to reserve is known statically:

Note that withUnsafeTemporaryAllocation could allocate heap memory after a certain threshold. This is minor technicality that could be worked around by using some new "allocate on stack or nil / fail" function.

[beccadax (Becca Royal-Gordon)]

Like a lot of people here, I'm pretty excited about this one.

General comments:

• As far as I can tell, this proposal never even mentions copy-on-write, let alone discusses it as a difference between Array and Vector. That's not great because it's an enormous difference with major performance impact when you use Vector with a copyable type.

• I'd like to see a use site example for each API you propose. It doesn't have to be in the same place—in fact, it might be best to put all of these examples in "Proposed solution" and leave the definitions until "Detailed design"—but if we're to stay true to our ABI guidelines, we need to be able to evaluate clarity at the point of use.

@Alejandro

We introduce a new top level type, Vector, to the standard library which is a
fixed-size contiguously inline allocated array. We're defining "inline" as using
the most natural allocation pattern depending on the context of where this is
used. It will be stack allocated most of the time, but as a class property
member it will be inline allocated on the heap with the rest of the properties.
Vector will never introduce an implicit heap allocation just for its storage
alone.

A simpler way to put this might be, "The elements in a Vector are stored inline in the instance, as though they were stored properties, rather than in a separate copy-on-write allocation." That way you don't need this confusing language about how it's sometimes on the stack and sometimes on the heap.

(Maybe "in the space typically used by stored properties" instead? Up to you.)

@Alejandro

While naively we could
conform to ExpressibleByArrayLiteral, the shape of the initializer always
takes an actual Array value. This could be optimized away in the simple cases,
but fundamentally it doesn't make sense to have to do an array allocation to
initialize a stack allocated Vector. Therefore, the array literal
initialization for Vector will be a special case, at least to start out with.

This is pretty weird—weird enough to make me wonder whether we should support the array literal syntax for this type. Are there other viable options, like overloading the N-tuple syntax or using a parameter-pack-taking Vector.init(_:)?

@Alejandro

In addition to literal initialization, Vector offers two other forms of
initialization; a closure based one for all element types and a repeating based
one for copyable elements.

Is there a way—even a failable way—to convert an Array to a Vector other than by using the closure-based initializer?

@Alejandro

  public init<E: Error>(_ body: (Int) throws(E) -> Element) throws(E)

I'm imagining a call site for this initializer and it seems…strange.

let evens = Vector<8, Int> { i in i * 2 }

Would it be possible for this to have a "size-pinning parameter" in the same way that many type conversion APIs have a "type-pinning parameter"? If it is possible, do we think that would be a good idea?

// Feels a little more comfy if we can pull it off
let evens = Vector(count: 8) { i in i * 2 }

@Alejandro

extension Vector where Element: ~Copyable {
  /// Consumes the vector by running the given closure value over each element
  /// passing in the element's index as well as the owned element value.
  ///
  /// This will call the closure `Count` times, where `Count` is the static
  /// count of the vector, to deinitialize every element by passing the closure
  /// the index of the current element being deinitialized and the owned element
  /// value. The closure is allowed to throw an error at any point during
  /// deinitialization at which point the vector will eagerly deinitialize the
  /// remaining elements and throw the given error back out to the caller.
  ///
  /// - Parameter body: A closure given the current deinitialized element's
  ///                   index and the owned element value.
  /// - Returns: The return value, if any, of the `body` closure parameter.
  public consuming func consume<Result: ~Copyable, E: Error>(
    _ body: (Int, consuming Element) throws(E) -> Result
  ) throws(E) -> Result
}

Er…body is called Count times, right? So which of the Count Results is returned by this method?

@Alejandro

Collection conformances for copyable elements

Here, we define our basic collection conformances to RandomAccessCollection,
MutableCollection, and BidirectionalCollection but only when the element is
known to be copyable. This is an unfortunate limitation, but the current
collection protocols make a deep assumption about element copyability as well
as the copyability of the collection itself. I discuss about this more in depth
in Future Directions.

If I understand correctly, Span is leaving out conformance to the collection protocols until the copyability issue is resolved. Why is Vector different? Is one of these proposals doing the wrong thing here?

@Alejandro

We plan to introduce a new upcoming feature that folks can enable whenever
they'd like to via -enable-upcoming-feature CArrayVector. This will change the
current behavior of importing C arrays as tuples, to instead import them as
Vector.

Fantastic.

@Alejandro

To prevent the
headache of this and any potential new availability feature, we're holding off on
these conformances until they are fully generalized.

Experience has shown that until we provide these conformances, people will conform the type retroactively, and that will create a bit of a mess once we release them.

• What features are needed to be able to provide these conformances? Are they close enough that this doesn't really matter?
• What is our plan for types like Optional that currently support non-copyability but already conform to these protocols? Could we do the same thing for Vector, or would the engineering complexity be too high?

@Alejandro

public protocol ExpressibleByVectorLiteral: ~Copyable {
  associatedtype Element: ~Copyable
  associatedvalue Count: Int

  init(vectorLiteral: consuming Vector<Count, Element>)
}

extension Vector: ExpressibleByVectorLiteral {
  init(vectorLiteral: consuming Vector<Count, Element>) { ... }
}

extension Pair: ExpressibleByVectorLiteral {
  init(vectorLiteral: consuming Vector<2, Element>) { ... }
}

But even with this design it's unsuitable for Array itself because it doesn't
want a static count for the literal, it still wants it to be generic.

I think you're confusing yourself by trying to design something that would support both Array and Vector. Array and other variable-sized types are already well-served by ExpressibleByArrayLiteral; the difference between that protocol and ExpressibleByVectorLiteral is precisely that the latter design permits the type to control the size.

@Alejandro

• [N x T] or [T x N]
• [N * T] or [T * N]
• T[N] (from C)
• [T; N] (from Rust)

I could be talked out of this, but I think this proposal probably ought to make a call on sugar. It would be extremely confusing for the order of the two generic parameters in the non-sugar syntax to be different from their order in the sugar syntax, so this proposal will constrain any future sugar proposal; also, it just seems strange to devote a proposal to an issue so small.

Another possibility not suggested here is [T, N] or [N, T]. But ultimately I think I prefer the * syntax because * is an operator character.

@Alejandro

A name other than Vector

Um. Please. This is subjective, but Vector as an arbitrarily-sized, arbitrarily-typed container has always felt really weird to me. In my mind, a vector is an arrow in an N-dimensional plane that you can add to some things and multiply with others, and although I do understand that said arrow is actually defined by a small list of N numbers and the concept further generalizes to a small list of N Ts, it never stops feeling poorly named.

Relatedly, the fact that the mathematical meaning of "vector" suggests fixed-size while the C++/Rust meaning of "vector" is variable-sized does not mean that we should discard the C++/Rust meaning and use the mathematical meaning instead; it means we should avoid this semantic labyrinth of a noun entirely. Leave Vector for geometry libraries to use.

FixedSizeArray/FixedCountArray are straightforward and obvious; maybe your InlineArray could become FixedCapacityArray to fit into this scheme. Those names aren't snappy like Vector is, but this is a relatively specialized type—it doesn't need a snappy name. (Especially not a confusing snappy name!)

If we do want a snappy name, I notice that we still have not decided what exactly a Buffer is. Its use in UnsafeBufferPointer and friends seems compatible—they are also fixed-size collections of data stored inline at the base address.

[clark (Clark Dobson)]

The distinction with a mathematical vector is not about a list having a fixed length.

A mathematical vector is a much more general object. A vector is an member of a vector space (over an algebraic field), whose elements can be numbers, tuples, matrices, functions, almost whatever you like. So for example, in the right context we might consider a Swift closure to be a mathematical vector. The only requirement is that an algebraic structure is imposed such that the operations of vector addition and scalar multiplication are defined.

The type defined in the proposal could be made into a mathematical vector if addition and scalar multiplication operations were required to be implemented (which would require restrictions on the element type). Otherwise it's just a list of things.

[Pippin (Ethan Pippin)]

To be fair, there isn't much that would stop a Vector to represent a geometric vector. In a future where this is merged, I expect a lot of new components in swift-numerics like:

extension Vector where Count == 2, Element: SignedNumeric /*or whatever*/ {
  var direction: Double /*or whatever*/ { }
}

// all other mathemetical vector extensions of
// arbitrary n and Element types

[QuinceyMorris]

@beccadax

FixedSizeArray/FixedCountArray are straightforward and obvious; maybe your InlineArray could become FixedCapacityArray to fit into this scheme. Those names aren't snappy like Vector is, but this is a relatively specialized type—it doesn't need a snappy name. (Especially not a confusing snappy name!)

Let's look at the world through some psychedelic spectacles…

You got me thinking laterally about snappy names. "How about List?", my brain suggested cheerily, since it's just … a list of things. Well, OK, that wouldn't work out well, so forget that.

So, what about Tuple? After all, in some ways, this proposal is "just" filling out the missing API for current Swift tuples.

That would also suggest a solution to the literal problem: Tuple literals would be just old-style Swift tuples with constant values between parentheses. Tuple initialization values would be the same thing, with potentially non-constant values between parentheses. No Array construction necessary.

Let's get crazier. Is the type being proposed here actually the nominal type that sorta could replace current non-nominal tuple types?

OK, dash it all, I forgot for a moment that current tuples do not require homogenous element types. But we do have generic type packs, which is sort of a handle onto collections of non-homogenous types. Is what we're reaching for here actually a generalization of both tuples and fixed size arrays??

Feel free to take the psychedelic spectacles off now.

[1-877-547-7272]

@Pippin

there isn't much that would stop a Vector to represent a geometric vector

It’s worth noting that in Swift, + is used both for addition and for concatenation. That means that if we were to add a + operator to Vector, then it would likely be pretty confusing.

People who use Vector as a mathematical vector would expect

([1, 2] as Vector<2, Int>) + ([3, 4] as Vector<2, Int>)

to result in

[4, 6] as Vector<2, Int>

, whereas people who treat Vector as a fixed-size array (which would be a very common interpretation) would expect it to result in

[1, 2, 3, 4] as Vector<4, Int>

.

[jcarrillo7 (Jose)]

@1-877-547-7272

People who use Vector as a mathematical vector would expect

([1, 2] as Vector<2, Int>) + ([3, 4] as Vector<2, Int>)

to result in

[4, 6] as Vector<2, Int>

, whereas people who treat Vector as a fixed-size array (which would be a very common interpretation) would expect it to result in

[1, 2, 3, 4] as Vector<4, Int>

.

To me this is the more convincing argument for not using Vector as the name (and leaving that for the pure mathematical concept that requires addition and multiplication for the element types).

@beccadax

If we do want a snappy name, I notice that we still have not decided what exactly a Buffer is. Its use in UnsafeBufferPointer and friends seems compatible—they are also fixed-size collections of data stored inline at the base address.

And I think this is the best alternative mentioned so far.

[ksluder (Kyle Sluder)]

@jcarrillo7

To me this is the more convincing argument for not using Vector as the name (and leaving that for the pure mathematical concept that requires addition and multiplication for the element types).

In fact, in code that deals with 3D graphics, it would be extremely common to create a Swift.Vector of mathematical vectors! For example, a buffer may consist of 3 vectors for each vertex, each of which contains 3 coordinates. Today, this would be modeled as tuple of vectors, but under this proposal it would be a Vector<3, Vector3>>!

This doesn’t seem to be a big problem in C++ because code that touches vectors is usually in the hot path, so it’s manipulating them as blocks of contiguous memory rather than putting them in a std::vector.

[ibex10]

Row or Store could be alternative type names to consider instead of Vector.

[Sajjon (Alexander Cyon)]

This is fantastic! Great proposal. As someone who has mostly coded Rust the last year I'm very happy about the addition of a fixed size stack allocated type.

We fully acknowledge that the Swift types, Swift.Array and Swift.Vector , are
complete opposites of the C++ ones, std::vector and std::array . While it may
be confusing at first, ultimately we feel that our names are more in line with
the mathematical term of art.

I just now watch saw this scene in Dispicable Me with my daughter, so fun that I read this proposal just seconds after

Sure the switchero between Rust and Swift with [T; n]; / Vector<n, T> and Vec<T>; / Array<T> is slightly unfortunate, but it is a non-issue, for programmers like me who master both languages there are other more challenging differences in the languages to juggle. And actually, one can tell just by the shape of the type that [T; n]; in Rust is akin to Vector<n, T> in Swift and Vec<T> is Array<T> in Swift.

I hope making Sequence and Collection support non-copyable types is a high priority for the team, while for i in ints.indices { ints[i] = .. } is OK, it is still such a big step back from the ergonomics of Swift we almost take for granted. So I'm in favour of getting Vector out sooner, without generalized Sequence and Collection but I hope augmenting Vector with conformance to those protocols can be prioritized.

Anyway, great job, super excited about this!

[mickeyl (Dr. Mickey Lauer)]

(wrong reply id)

[mickeyl (Dr. Mickey Lauer)]

I like that. Will I be able to change the C mapping of arrays to Swift tuples with that?

[dimi (Dimitri Bouniol)]

@QuinceyMorris

So, what about Tuple? After all, in some ways, this proposal is "just" filling out the missing API for current Swift tuples.

I initially also reached for Tuple in earlier suggestion, but was afraid this would cause confusion to newcomers of the language learning about anonymous () tuples vs capital-T Tuples, and being confused that they were not actually interchangeable, especially with regard to their collection conformances. I therefore suggested HomogenousTuple, as the most common case would have it represent a repeating single type (or I assume Any if the type was inferred from an array or tuple literal?).

The more I think about this, the more I really like it actually. Because at the end of the day, this type is not really an array type at all, as you cannot append or remove from it as stated. Instead of ExpressibleByArrayLiteral, we could instead have a ExpressibleByTupleLiteral, which could enable generic inference as well:

let hexLookup: HomogenousTuple = ("0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F")
/// Inferred to be HomogenousTuple<16, String>

ExpressibleByTupleLiteral could probably just use a HomogenousTuple itself:

protocol ExpressibleByTupleLiteral {
    /// The size of a tuple literal.
    associatedtype TupleLiteralSize: Int

    /// The type of the elements of a tuple literal.
    associatedtype TupleLiteralElement

    /// Creates an instance initialized with the given elements.
    init(tupleLiteral elements: HomogenousTuple<Self.TupleLiteralSize, Self.TupleLiteralElement>)
}

(I'm sure we could do better if we wanted it to use parameter packs in some way to represent it as a proper anonymous tuple, with every element conforming to a single type, though such a solution is not immediately obvious to me as I type this.)

One final benefit of this line of thinking, HomogenousTuple could also be a regular tuple, so long as all the elements match. For instance, the following could become allowable:

// In some existing library
func lookup(id: (Int, Int, Int, Int)) {...}

...

let itemID: HomogenousTuple = (1, 2, 3, 4) // let id: HomogenousTuple<4, Int>
lookup(id: itemID)

This could simplify the compatibility story. uuid_t could be re-defined as HomogenousTuple<16, UInt8> in a potentially non-breaking way, along with the rest of the C APIs, potentially simplifying the requirement of waiting for a future swift language mode.

[mgriebling (Mike Griebling)]

As someone keen on optimizing code, Vectors sound ideal. Most of us have been struggling with optimizing array-based code and this seems like the perfect solution. Please implement right away. Less talk and more action . In this regard, languages with fixed-size array-like types have an unfair speed advantage. Vector would finally bring Swift into the same performance range.

[Datagram]

This is my understanding reading this section of the proposal:

@Alejandro

C Interop changes

With the introduction of Vector, we have a unique opportunity to fix another
pain point within the language with regards to C interop....

@Alejandro

We plan to introduce a new upcoming feature that folks can enable whenever
they'd like to via -enable-upcoming-feature CArrayVector. This will change the
current behavior of importing C arrays as tuples, to instead import them as
Vector. For the previous example, we'd instead generate the following:

struct section_64 {
  let sectname: Vector<16, CChar>
  let segname: Vector<16, CChar>
  let addr: UInt64
  let size: UInt64
  let offset: UInt32
  let align: UInt32
  ...
}

And I am very happy about this.

[bbrk24]

@ChrisPls

Vector is pretty consistent within software. It means resizable.

Since I haven't seen this mentioned yet in the thread, C# uses Vector for its SIMD type, which has a fixed, hardware-dependent capacity.

[j-f1 (Jed Fox)]

@Alejandro

a fixed-size contiguously inline allocated array. We're defining "inline" as using the most natural allocation pattern depending on the context of where this is used. It will be stack allocated most of the time, but as a class property member it will be inline allocated on the heap with the rest of the properties. Vector will never introduce an implicit heap allocation just for its storage
alone.

How would this interact with stack size limits? Especially if the count parameter can be controlled at runtime, I can imagine it being very easy for an attacker to pass in a large number, overflow the stack, and crash the process. withUnsafeTemporaryAllocation handles this today by allowing its storage to be backed by the heap or the stack, and tuples handle it by breaking the type checker if they’re too long. But this type is committing to being stored inline and easily admits arbitrary sizes. Could the language itself be amended to set a maximum size for local variables and then dynamically move them to a heap region when they grow too large? Or is there some other way you can see this being addressed?

[FranzBusch]

I can’t wait to use this. This unlocks a swath of performance optimizations all around the server ecosystem.

@rauhul

I don't have a specific issue with the name Vector but I am curious what a future Fixed Capacity Array might be named, and similarly what names we might give other fixed collections, like {Stack|Queue|RingBuffer}<let Capacity: Int, Element> etc...

I want to echo this feedback. While I think Vector is an acceptable name how does this scale across other data structures that want to offer fixed size variants? I often wanted to reach for a fixed size deque.