Vector manifesto

[Nobody1707]

You could always write a thin wrapper type that has 1-based subscripting.

public struct OneBasedArray<T: RandomAccessCollection & MutableCollection>:  RandomAccessCollection, MutableCollection where T.Index: FixedWidthInteger {
    var backingStore: T
    public typealias Index = T.Index
    public typealias Element = T.Element
    public init(_ collection: T) { backingStore = collection }
    public subscript(index: Index) -> Element {
        get { return backingStore[index - 1] }
        set { backingStore[index - 1] = newValue }
    }
    public var count: Int { return backingStore.count }
    public var isEmpty: Bool { return backingStore.isEmpty }
    public var startIndex: Index { return 1 }
    public var endIndex: Index { return backingStore.endIndex + 1 }
    public func index(after i: Index) -> Index { return i + 1 }
    public func index(before i: Index) -> Index { return i - 1 }
    public var indices: Range<Index> { return startIndex..<endIndex }
}

[Andrew_Trick]

Regarding getting an UnsafeBufferPointer, I think the example should be:

let matrix:Vector<4, Vector4<Float>>
withUnsafeBytes(of: matrix) {
  glUniformMatrix4fv(location, 1, false,
    $0.baseAddress.assumingMemoryBound(to: Float.self))
}

See also "Implicitly convert &Tuple to UnsafePointer<Tuple.Element>" [SR-3590] Implicitly convert &Tuple to UnsafePointer<Tuple.Element> · Issue #46175 · apple/swift · GitHub

The only reason to call bindMemory is if you need to reuse a chunk of memory that you allocated earlier for other objects to now hold a different underlying type.

[taylorswift]

how would a withUnsafeBufferPointer(to:) method work in this case? also, Vector<N:Int, T> wouldn’t be a tuple type, it would wrap one as storage. And the elements of a matrix would be Vector4<Float>, not Float

[Andrew_Trick]

Under the hood, you could do safely do something like this:

return try withUnsafePointer(to: tuple) {
  let base = UnsafeRawPointer($0).assumingMemoryBound(to: T.self)
  return try body(UnsafeBufferPointer(base, N))
}

It would be nice to have compiler support so you never need to drop down to a raw pointer.

[taylorswift]

well the problem is that wouldn’t take you all the way down to the scalar type if you have a nested array, like a matrix. the unsafebufferpointer you’d get would have Vector4<Float> elements, not Float elements.

[Andrew_Trick]

Yeah, I entirely missed your point. I think the goal of the example in your proposal is just to show the layout guarantee. In that case you can recast the pointer with assumingMemoryBound and it's up to the user to compute the new element count.

You certainly could provide a withUnsafeFlatBuffer API that computes the total number of elements and hides the pointer type casting. But that's additive.

[taylorswift]

@Andrew_Trick

Yeah, I entirely missed your point. I think the goal of the example in your proposal is just to show the layout guarantee. In that case you can recast the pointer with assumingMemoryBound and it's up to the user to compute the new element count.

wait can you explain why we should use assumingMemoryBound and not bindMemory? because i thought the FSA’s storage would be bound to Vector<4, Vector4<Float>>, not Float, so a rebind would be needed to make it Float

[ladislas (Ladislas de Toldi)]

Fair enough! I agree with you! let's stick curly braces to blocks of code.

[Andrew_Trick]

@taylorswift

wait can you explain why we should use assumingMemoryBound and not bindMemory ? because i thought the FSA’s storage would be bound to Vector<4, Vector4<Float>> , not Float , so a rebind would be needed to make it Float

Yes of course! Memory can only be bound to one type at a time. But, when it's bound to an aggregate, it's also bound to the aggregate's element types. Since your Vector is a homogenous aggregate of Floats, all the bytes in that Vector are bound to Floats. You just have to be careful with alignment, but the whole point of your example is that Vector must have the same alignment as its constituents.

For more than you wanted to know, see the unofficial-but-probably-valid-in-practice Type Safety.

Using bindMemory implies that you want to reuse the memory for an "unrelated" type. If Vector<Float> and Float were unrelated, that would actually be a problem. First you bindMemory to Float, which is like reinterpreting all the bits in that memory. That's ok. But you never call bindMemory to make it a Vector again. So all subsequent accesses to that Vector would be undefined.

This is the conventional way to call out to C when the imported type doesn't match, which is also perfectly fine in your case:

let matrix:Vector<4, Vector<4, Float>> = ...
withUnsafePointer(to: matrix) { matrixPointer in
  let count = MemoryLayout.size(ofValue: matrix) / MemoryLayout<Float>.stride
  matrixPointer.withMemoryRebound(to: Float.self, capacity: count) {
    glUniformMatrix4fv(location, 1, false, $0)
  }
}

[Nevin]

@taylorswift

I like the general direction. One specific question: you mention that fixed size arrays cannot conform to RandomAccessCollection . It’s not immediately obvious to me why that’s the case; a fixed size array can easily produce a slice (albeit one without a fixed size) that provides access to its contents. Could you elaborate on your reasoning here?

It certainly could, but it would be very inefficient because a slice would copy the entire fixed-size array into its self.base property. makeIterator() on Sequence has the same problem though, which violates this requirement

Expected Performance

A sequence should provide its iterator in O(1). The Sequence protocol makes no other requirements about element access, so routines that traverse a sequence should be considered O( n ) unless documented otherwise.

In the end it might not even be appropriate to give Vector<N:Int, T> Sequence conformance at all, and make self.withUnsafeBufferPointer the canonical way to do “sequence”/“collection” things to a fixed-sized array. But that would mean giving up the ability to use them with for _ in loops at all.

It is almost trivial to make fixed-size arrays conform to Collection. The standard library even has a default Slice type if we wanted to use it.

The idea that we wouldn’t make fixed-size arrays conform to RandomAccessCollection strikes me as, quite frankly, preposterous. A fixed-size array is pretty much the poster-child for random-access collections.

[taylorswift]

these slices wouldn’t be efficient though, slicing a fixed-size array would be an O(n) operation

[taylorswift]

@Andrew_Trick

This is the conventional way to call out to C when the imported type doesn't match, which is also perfectly fine in your case:

let matrix:Vector<4, Vector<4, Float>> = ...
withUnsafePointer(to: matrix) { matrixPointer in
  let count = MemoryLayout.size(ofValue: matrix) / MemoryLayout<Float>.stride
  matrixPointer.withMemoryRebound(to: Float.self, capacity: count) {
    glUniformMatrix4fv(location, 1, false, $0)
  }
}

doesn’t withMemoryRebound only work between types of the same size?

[TellowKrinkle]

One drawback to fixed-size arrays not conforming to RandomAccessCollection is that such a conformance is required for significant compiler optimizations for operations like flatMap(_:) (discussion). Operations like makeIterator() and reversed() will also be difficult to implement efficiently due to fixed-size arrays being (trivial) value types. The optimizer will probably need to be modified to understand fixed-size arrays and emit efficient code for them.

The linked discussion says that [[T]].flatMap { $0 } was more efficient than [(T, T, T, T)].flatMap { [$0.0, $0.1, $0.2, $0.3] }, AKA passing arrays directly is more efficient than creating arrays from tuples and returning them. It also said

@Ben_Cohen

But it appears you can do even better if you conform the struct to itself be a collection, allowing it to be flat mapped directly:

Which is the case we would be dealing with here.

[TellowKrinkle]

I doubt (semantically) making copies of fixed size arrays for things like indexing iterators or slices is actually going to be a problem (assuming you use the slice immediately and don't store it) since while you are making a copy, it's an immutable copy of a non-heap allocated struct which is probably one of the best cases for the optimizer (note: may run into issues if your array is of a type with a non-trivial copy constructor, like something containing class references)

In my test here and here for with slicing it does appear that the compiler has some issues deciding whether the array should be stored in memory vs registers when I try to loop over it* (see below) but there is no difference between using a for-in loop (which in high level Swift uses an indexing iterator, which semantically makes a copy of the array) and indices (which uses a Swift range and indexes the array directly), even if at the moment the codegen is bad for both.

* it tries to store the fixed size array in xmm registers but has to dump it into memory to index into it... which it decides to do in every iteration of the loop. Ideally it would never load it into the xmm registers in the first place...

[Andrew_Trick]

You're right, we still don't have a reasonable version of withMemoryRebound for flattening aggregates. I thought that the stride restriction was only for the buffer pointer variant because it would need to compute a new count. But even the non-buffer variant has a restriction because it only takes the new count, not the old count. Since it was never enforced though, I'd be in favor of changing the implementation to always check and recompute the old count. It violates the principle that this is a zero-cost abstraction, but we might need to live with that.

At any rate, for now you either need to use assumingMemoryBound or make two calls to bindMemory.

[taylorswift]

@TellowKrinkle

it tries to store the fixed size array in xmm registers but has to dump it into memory to index into it... which it decides to do in every iteration of the loop. Ideally it would never load it into the xmm registers in the first place...

is this because it stores the tuple broken up and has to rearrange it into contiguous layout to take a pointer to it

[TellowKrinkle]

Possibly, here's a comparison of doing an index using C++ and Swift
The Swift one is a bit hard for me to understand, but it seems to want to represent the tuple as 4 UInt8x16 arrays instead of 1 UInt8x64 array among other things...

[CTMacUser (Daryle Walker)]

I've discussed fixed-size arrays here in the past. Here's what I think the design should be; a competing idea before any code hackers get too invested to this design.

@taylorswift and I both agree that SIMD vector types and fixed-size arrays should have similar syntax. Their difference is more in the implementations than the interfaces.

But @taylorswift's core design is very different from mine. S/he jams them in as quirky structs and tuples, while I use a brand new syntax.

Fixed-size arrays are compound types. Their declaration is like Rust, but the order is swapped:

let x:  [10; Int]

is an array of ten integers. Dereference works like our Array, which is also used in C and its many inspired languages (C++, Go, Rust, Java, etc.):

x[3]

The order is swapped from Rust so combining axes via nesting means going from the outermost span to the innermost span is left-to-right in both declaration and dereference. (The extent declaration and dereference orders also align in C and Go. I'm not sure why Rust switched it up.) Brackets are used since they are used for all array stuff in the C family of languages; I find stuffing fixed-size arrays as a quirky tuple as a surprise, especially since we already have an array declaration syntax. The separator between the extent and element type is a semicolon because (besides matching Rust) it's already a punctuator-keyword, as opposed to the asterisk which is currently only a punctuator-identifier.

When I referenced combining axes and the extent/element separator, I put in little qualifiers. That's because my design includes multi-dimensional support.

let y: [2, 5; Double]

Pre-C array designs, at least in Fortran and COBOL, where multi-dimensional. The designers of C ripped that out, probably because C was meant as a to-the-metal portable assembly language. We are not bound to that, like many of the ways Swift already eschew keeping copied-over C features primitive (big example: enumeration types). I'm anti-ripping it back in because the partition between extents is user-valuable design information. I'm not sure how multi-dimensionality is supposed to work in @taylorswift's design, besides dumping it and go with simple nesting, like C and every other C-inspired language does.

Dereference for a multi-dimensional type just comma-separates the coordinates:

y[1, 4]

There is also a static dereference mode, which is a single-number offset:

x.1  // x[1]
y.7  // y[1,2]

I came up with this to satisfy deterministic initialization until we get variadic generic function support ready enough to write the fixed-size array support functions. (The lack of a VGF story currently is one of the reasons why I never gave an update until the OP forced my hand.)

Oh yeah, zero-dimensional arrays are supported, which have exactly one element (and would probably need the zeroExample.0 = whatever syntax to use). Zero-valued extents should be supported; they would take up zero space when they're not a top-level object and minimal space when they are.

For vector support, I'm currently thinking of decorating the targeted extent:

let xx: [@vector 4, 16; Int]  // sixteen 4-way-SIMD-Int
let x3: [4, @vector 16; Int]  // four 16-way-SIMD-Int
let x4: [4, 16; @vector Int]  // compiler decides, including other combinations, like a single 64-way-SIMD-Int, or two 32-way-SIMD-Int or thirty-two 2-way-SIMD-Int

Maybe we need to support a [whatever ; @vector(directions) Int] where the "directions" are specific instructions, so we can force an option, like 4x16, 16x4, or 1x64. Storage is generally row-major, but the compiler can switch it up behind the scenes when vectorization is added. If a vector shape, element type, or combination is not supported, then the compiler can flag an error.

Existential arrays are also supported. I'm guessing that they'll be a bundle of a pointer to the array's data block and a reference to the object's witness table. Obviously, I'm imaging a new type of witness table entry. It would have a reference to the element type's witness table, a cached copy of the total number of elements, description of the SIMD status (if any), the number of extents, then a variadic list of each extent count. (The total number of elements is cached so we don't have to do the multiplication each time.)

The existential-ness can be on either the extent side or the element side. Casts can be done, as always, with "as", "as?", or "as!", where the punctuator-less version can't be used when whether a downcast is involved is either yes or unknown.

• An array of Derived can be upcast to Base with the same shape or an existentially-compatible one, where Derived and Base are reference types.
• An array of T can be upcast to MyProtocol.singular with the same shape or an existentially-compatible one, where T conforms to MyProtocol. The "singular" suffix can be bikeshedded later. Note the original array has elements all of the same type; a [Shape ; Numeric.singular] can be assigned a [Shape ; Int] or a [Shape ; Double], but not a mix. (Said mix of integers and doubles would be a regular [Shape ; Numeric], with no "singular" suffix. Remember that protocols don't conform to themselves so [Shape ; P] doesn't conform to [Shape ; P.singular] unless P is either Error or Any.) Dereferenced elements through the existential would be of MyProtocol. (Hmm, maybe we should let [Shape ; P] conform to [Shape ; P.singular].)
• An array where its shape consists of all numbers can be upcast to one where one or more extent numbers are replaced with a placeholder ("_") with the same element type or an existentially-compatible one. Such existential array types have a dimension-specified existential shape. An array or array existential where all the extents are numbers have a non-existential shape. (Zero-dimensional arrays always have a non-existential shape.)
• An array with a dimension-specified existential shape can be upcast to one with more of the definitive extents replaced with placeholder(s) with the same element type or an existentially-compatible one.
• An array with a non-existential or dimension-specified existential shape can be upcast to the dimension-agnostic existential shape, with the same element type or an existentially-compatible one. This shape is specified by using the ellipsis ("...") as the extent. (This is the only existential shape a zero-dimension array can transition to.)

Note that these rules mean that [... ; Any.singular] is the top fixed-size array type.

Since extent counts besides 1 are supported, automatic Sequence support would be awkward. But I was about to propose a reworking of the Sequence/Collection hierarchy, and fixed-size arrays could be made to conform to those, where single-dimension arrays could conform to MutableCollection too.

[rsebbe (Raphael Sebbe)]

+1 for fixed-size arrays, they are very much needed. More specifically:

• subscripting/dereference with compiler checks when possible
• loop iterations
• predictable storage

The older 2016 thread that was trying to use tuples for this seems wrong to me, as they are different things and should therefore be addressed in different ways for the very same reason that Swift uses strong (and specific) typing.

I find Daryle’s syntax (Rust-inspired) simpler. Not sure we want to have generics with integer parameters like C++ templates. Even in C/C++, this (basic) capability is exposed in C with a very simple syntax, it does not require the full template capabilities of C++. I don’t think it needs Swift type features that aren’t available yet.

I understand the need of discussing SIMD, but not sure it should be treated jointly with fixed-size arrays as they are very specific. “simd.h” approach seems superior to me, even though vectorizing hints could be passed in the fixed-size array syntax.

[Chris_Lattner3 (Chris Lattner)]

@ladislas

Regarding the literal syntax , I like the C/C++ syntaxt {1, 2, 3, 4, 5} using curly braces. Any reason it is not considered in the manifesto?

FWIW, Swift consistently uses square brackets for initializer sequences (with colons for key/value pairs). I don't see why we would want to diverge from this for vectors.