[Second review] SE-0453: Vector, a fixed size array

[lorentey (Karoy Lorentey)]

@technogen

Okay, this is news to me! I'm getting confused... Can you please explain why does this type deserve to exist if the planned InlineArray is essentially the same thing, but with a more polished API?

Vector is not the same thing as InlineArray.

Vector<3, Int> consists of precisely 3 integers, like a homogeneous tuple, or the int3 vector type in a shader language, or int[3] in C. This is not an Array type in Swift, because it does not provide the operations we expect a Swift Array type to provide.

InlineArray<3, Int> is an actual Swift array type. It can contain 0, 1, 2, or 3 integer values. You can insert new ones at arbitrary offsets, or remove existing ones from it.

(The C programming language does not provide a built-in implementation of such an abstraction -- out of necessity, people build it from scratch, out of a base pointer, a capacity and a current count. InlineArray packages these up into a proper type.)

Internally, a Vector holds enough room to store the necessary amount of fully initialized elements, and nothing else.

Internally, an InlineArray instance holds partially initialized storage of a certain capacity, along with metadata that describes which of its slots are initialized. The nature of this metadata varies between Inline* types; in the case of InlineArray, it consists of a single count value. In InlineDeque, it consists of a count and startSlot. In InlineSet, it would consist of a full bitmap of occupied slots.

It is fair to argue that you do not care about this distinction, and you've never ever wanted to reach for either Vector or InlineArray. This is a valid point: the existing Array is great, and provides an awesome, uniform model. If you are happy with its performance, please feel fully empowered to continue using it, indefinitely.

Unfortunately though, we need Swift to become usable in contexts where these details matter.

I believe that Vector belongs in the core Standard Library, because it is destined to become a prominent currency type. It is intended that it will play the same role that is currently being played by homogeneous tuples, badly.

InlineArray may or may not make sense to add to the core stdlib; I think it may make more sense to ship it in a module that needs to be explicitly imported. (InlineDeque, InlineDictionary etc. are in the same category.) Some people will want to frequently use it (and SmallArray, SmallDeque etc.) to avoid Array's allocation overhead, but we don't need to shove these down everyone's throats -- there are many contexts where the performance benefits don't matter, or Array is already the optimal solution.

The Swift project is making a concerted effort to push the language into areas it did not adequately serve before. We are working hard to fulfill the aspirations of the first sentence of its README, that "Swift is a high-performance system programming language".

For the language to become a serious contender for use in low-level, high-performance, memory-constrained and/or realtime environments, we need to start making distinctions we intentionally avoided making before. This includes fracturing our existing, comfortable, universal constructs into a myriad highly specialized pieces. My drawing board includes InlineArray, RigidArray, SmallArray and DynamicArray as potential spawns of Array; we will most definitely end up having to eventually productize some or all of these. These types enable exciting new use cases, but they are inherently a major break from our classic guiding principles, so for many existing uses of Swift, they will be nonsensical at best, or a major complication at worst. (For example, think what it will take to enable a noncopyable array variant like RigidArray to serve as the underlying model for a SwiftUI list view.)

We are fundamentally changing the nature of Swift; the challenge is to do it in a way that doesn't overly harm our existing use cases. It must remain possible for a Swift programmer to ignore that InlineArray exists.

Note that Vector is not in this scary category, because it isn't a spinoff of Array; rather, it is a rethinking of homogeneous tuples. Vector is not an array type in the sense that Swift is using this term.

We have plenty of Array types, and lots more are coming; but Vector is not one of them.

Vector is not an Array.

[lorentey (Karoy Lorentey)]

@davedelong

This doesn't make sense to me, because:

// is this not an "Array" because I can't insert, append, remove, nor concat?
let immutable = [1, 2, 3]

// but this is an array because I can insert, append, remove, or concat?
var mutable = [1, 2, 3]

The append operation does exist on immutable; it is part of the shape of Array. The type Array provides a specific set of mutating and nonmutating operations. These operations are part of the type's definition. They establish a direct pattern for other types to follow.

Orderedness and O(1) indexing does not an array make. We are not calling UnsafeBufferPointer or Span "array types" in Swift.

This is not something I'm randomly pulling out of my hat to push my agenda for the day. My job has been to design and name Swift collection types for years. I know the rules Swift follows. I do not wish us to change what we call an array -- that would be incredibly disruptive.

As I mentioned, I'm open to naming Vector something silly like Run or Pack. I do think such a name would be strictly worse than Vector, and I would be filled with a pang of regret every time I saw it. I expect I'd keep rubbing people's nose in it. But calling Vector a Florp would still be orders of magnitude better than calling this thing an array!

[lorentey (Karoy Lorentey)]

@Lua

Really only the fact that it doesn't allocate, so it could be written as a global variable/constant and used with the same API as Image they both inherit from a Drawable protocol.

Alright. If I understand correctly, the inline image form provides the same operations as an allocation-backed image would.

If you want to have separate image types for inline-stored and allocated images, I think Image and InlineImage would be reasonable names for it -- these are variants of the same type family, providing the same operations. (They could also be called SmallImage and BigImage, invoking their intended use.)

The Image and InlineImage distinction works similar to how Array and InlineArray would work; these are good names.

This is not the case with Vector. Vector's API surfaces overlaps with Array the same way Span does. But just like Span, Vector inherently lacks the full set of operations that define Array. It isn't shaped like one.

Vector isn't a variant of Array.

[michelf (Michel Fortin)]

@lorentey

Vector is not an Array.

Quotes from: "SE-0453: Vector, a fixed size array":

We introduce a new top level type, Vector , to the standard library which is a fixed-size contiguously inline allocated array.

the array literal syntax will be used to initialize a value of Vector

Seems like it's hard to describe this vector without explaining that it's an array.

I do sympathise however with this position that it's different enough from Array to not be called one. This "vector" type feels close to a tuple, hence why I added a disclosable aside section to my earlier post floating the idea of adding this as a new kind of tuple with the right padding.

Regardless of whether the name "array" is the right one or not, I don't think the name Vector is appropriate. This type should not be given a name that implies capabilities beyond storing values.

[tera]

Ah, ok, I thought that the-type-being-discussed is the thing I want (e.g. to store 1024 samples in a realtime audio IO callback and do further processing on those), but it turns out it's only a "foundation" type to get to the type I want at some later stage... ok.

• no, I as a user do not view the ability to insert / remove as a defining characteristic of "Array". Even if those operations didn't exist on Array - that would still be "Array" for me (just more cumbersome to use at times and totally ok at other times). FTM NSArray (that don't have any of those operations) is (still) array. Possibly half (if not more) of the future "inline array" use cases would not involve insert/remove operations at all, just create (with initial size/capacity) and then iterate through all elements and set them to some values. Even the "size" property is not too important to have (nice to have but trivial to implement if it's not available).

• please do not hide the future "InlineArray" type in a package, make it readily available in the standard library.

• if there's really a need for some underlying core type with a limited functionality that forms a foundation for higher level types like "InlineArray" please do not spare a precious name "Vector" on it.

[jeremy]

@tera

if there's really a need for some underlying core type with a limited functionality that forms a foundation for higher level types like "InlineArray" please do not spare a precious name "Vector" on it.

Unless I've completely misunderstood what @lorentey was saying, the underlying core type for "InlineArray" is Array, not Vector.

[jeremy]

@michelf

the array literal syntax will be used to initialize a value of Vector

Seems like it's hard to describe this vector without explaining that it's an array.

The array literal syntax is also used to initialise a Set. That doesn't imply that a Set is an Array.

[Dmitriy_Ignatyev]

@michelf

Seems like it's hard to describe this vector without explaining that it's an array.

I suppose it was written in such a way to attract attention and for providing elementary and easy to understand explanation using known terms (but not fully correct though)

[torstenbernhard]

RowVector would be a good name, similar to linear algebra’s term.

[Dmitriy_Ignatyev]

@lorentey

My drawing board includes InlineArray, RigidArray, SmallArray and DynamicArray as potential spawns of Array

It will be very useful to have a vision document describing collection naming principles and what is defining for each of them.
I feel that next reviews will be more productive and less confusing.
Some people think that orderness and random access are defining for array type. Another think it is the ability to add / remove elements and ordered indexing.

While it will be useful to better understand new upcoming kinds and flavors of Array, we already also have Ordered / Sorted collections in SwiftCollections library. And more will come, like LinkedList and different trees.

I feel useful to have an aggregated vision about all these Array-types, Buffers, Span, Ordered|SortedCollections, why their names differ, why it is important and so on.

I can try to write such draft if others also find it useful, but anyway it will need some iterations of review by those who have more deep knowledge.

[lorentey (Karoy Lorentey)]

@tera

Ah, ok, I thought that the-type-being-discussed is the thing I want (e.g. to store 1024 samples in a realtime audio IO callback and do further processing on those), but it turns out it's only a "foundation" type to get to the type I want at some later stage... ok.

To reiterate, InlineArray is not going to be built on top of Vector, nor vice versa. These are independent constructs, each manually built from scratch using separate compiler builtins.

(It is not my goal for Swift to provide a public tool to build custom Inline* types from scratch; although if we're lucky, we may well end up with a usable-but-clumsy construct, in the same sort of role as ManagedBuffer is for heap allocated CoW types.)

[hisekaldma (Jonathan Hise Kaldma)]

@lorentey

Vector is not the same thing as InlineArray.

Neither of these things are, yet. Is there even a vision document describing this wider family of types that your argument hinges on?

[lorentey (Karoy Lorentey)]

Yes, there is a vision; I'll start a thread on it. Stay tuned. (It will take some time; I have another pitch/proposal that needs to go out first.)

Meanwhile, if you're curious about the array variants under consideration, please see my earlier posts on this subject.

[roopekv]

@lorentey

• InlineArray<count, Element> - Future conditionally copyable, fixed-capacity, nonresizable array type with inline storage.

Shouldn't this be InlineArray<capacity, Element>? The capacity is fixed, but the count can change?

@lorentey

• RigidArray<Element> - Future noncopyable, fixed-capacity, manually resizable, dynamically allocated array supporting noncopyable elements.
• DynamicArray<Element> - Future noncopyable, self-resizing, dynamically allocated array supporting noncopyable elements.

What would the differences between RigidArray<Element> and DynamicArray<Element> be? That the program execution stops when trying to append a new element to a RigidArray where count == capacity, but in the case of DynamicArray it reserves more capacity?

---

If InlineArray<capacity, Element> is going to be added in the future, and since the subject of this proposal seems to be an inline array with a fixed count, could the name be something like InlineArrayWithFixedCount<count, Element> instead of Vector<count, Element>?

FixedCountInlineArray similar to FixedWidthInteger?

[Dmitriy_Ignatyev]

One argument against Vector is that in mental model it is a vector when in contains only numbers.

But it is a generic structure with no generic constraints on Numeric-family protocols. It means that Vector can contain String, structs, elephants and any other instances.

From this perspective I imagine the following:

// what is proposed as Vector in this proposal
public struct Slab<let count: Int, Element: ~Copyable>: ~Copyable {}

// an algebraic vector with numeric values
public typealias Vector<let count: Int, Element: Numeric> = Slab<count, Element> 

[ibex10]

@lorentey

"Vector" is an extremely well-established name for an ordered sequence of precisely n items, all of the same type. There is a particularly strong expectation that a type called "vector" would provide an array-like subscript operation.

Then, I wonder how those who don't like the name Vector feel about the name FiniteSequence.

[Dmitriy_Ignatyev]

Developing this idea further, we can say that Vector is a more specialized variant of Slab.

Then if we see a Vector in source code or interface we know what exactly it is – it is math Vector. When we see a Slab we also understand fast that it is something not related to algebraic or vector computations.
(Of course nobody will restrict you to make a Slab of integers which effectively is a vector, but it is the responsibility of code author to pick appropriate data type and make right design)

We already have such similar type aliases in standard library:

public typealias CountableRange<Bound> = Range<Bound> where Bound : Strideable, Bound.Stride : SignedInteger

public typealias CountableClosedRange<Bound> = ClosedRange<Bound> where Bound : Strideable, Bound.Stride : SignedInteger

public typealias UnfoldFirstSequence<T> = UnfoldSequence<T, (T?, Bool)>

public typealias UnboundedRange = (UnboundedRange_) -> ()

Overall I feel this design better fine grained and coherent with Span. Both Span and Slab names are:

• short enough
• do not have mental burden about what they are as different kinds of array or vector have. After introduction folks will learn what they exactly are instead of projecting past experience and existing knowledge based on naming (instead of real semantic and contract).

What do you think? @jberry @lorentey

[tera]

"Vec" as a compromise?

• those who like name "Vector" could perhaps stomach "Vec".
• those who hate "Vector" name usage for anything but "math's vector" could perhaps stomach "Vec".

---

On "Elements":

A few examples of using something that's not a singular noun for types

Float, Double, URLComponents, UIControlEvents, UserDefaults, Optional

---

Edit: How about "Deck" ?

[Nobody1707]

@Dmitriy_Ignatyev

One argument against Vector is that in mental model it is a vector when in contains only numbers.

But it is a generic structure with no generic constraints on Numeric-family protocols. It means that Vector can contain String, structs, elephants and any other instances.

I don't really see this as a problem, as long as a Vector where T: Numeric is actually a mathematical Vector (which it would be).

[JanWillemBrands]

Alright, Alright, Alright.

It's not an Array and all names containing array are verboten. Haven't seen many attractive names being proposed other than Vector.

I love Vector.

But it seems generate an allergic reaction in a section of the Swift fanclub. Soooo, how about Bunch? As in bunch of grapes or a bunch of people. It's like a Tuple, but for one kind of thing.