Yet another fixed-size array spitball session

Evolution Discussion
21

There was someone a few weeks ago trying to port his Go game to Swift from (I believe) C++ and found out that the lack of fixed-size arrays was causing the move-computing algorithm to slow down significantly.

This is due to fixed arrays being able to live on stack, while "normal Array" is dynamically allocated on heap, etc.

10 000 may have been David's exageration, but imagine trying to form a chessboard using tuples - aside from the fact that you can't iterate over the tuple, the tuple type would be huge - instead of ChessPiece[8][8] (or similar syntax), you get:

((ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece))

And the practical use isn't just games - just think of any fixed-size matrices.

···

On May 30, 2017, at 12:25 PM, Pavol Vaskovic via swift-evolution <swift-evolution@swift.org> wrote:

On Tue, May 30, 2017 at 7:51 AM, David Sweeris <davesweeris@mac.com <mailto:davesweeris@mac.com>> wrote:

`(Int, Int, Int, Int)` isn't *that* horrible compared to "[Int x 4]", but would you want to replace "[Int8 x 10000]" with the multipage-long tuple equivalent?

:flushed:
It would be really helpful to my understanding, if you spoke about a practical use case. This reads as a contrived counterexample to me


If your type really has 10 000 values in it, why does it have to be static, why doesn't normal Array fit the bill?

--Pavol
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

22

I agree that Swift absolutely needs a static array type.

However, until then, here's a gist to generate the code for a static array struct: https://gist.github.com/rltbennett/8a750aa61d58746b3ca4531b3ca3d0db . Happy coding. (Disclaimer: barely tested.)

···

On May 30, 2017, at 11:27 AM, David Sweeris via swift-evolution <swift-evolution@swift.org> wrote:

On May 30, 2017, at 03:25, Pavol Vaskovic <pali@pali.sk> wrote:

On Tue, May 30, 2017 at 7:51 AM, David Sweeris <davesweeris@mac.com> wrote:

`(Int, Int, Int, Int)` isn't *that* horrible compared to "[Int x 4]", but would you want to replace "[Int8 x 10000]" with the multipage-long tuple equivalent?

:flushed:
It would be really helpful to my understanding, if you spoke about a practical use case. This reads as a contrived counterexample to me


If your type really has 10 000 values in it, why does it have to be static, why doesn't normal Array fit the bill?

Sure, I meant it as an example of how unwieldy large tuples can be. Even medium ones, really. Tuples are great for bundling a few values, but much more than that any they become annoying to work with because there's no easy way to iterate through them. As a more realistic example, what if you want a stack-allocated 256-element buffer (which is a real possibility since statically-allocated C arrays are imported as tuples)? You have to manually keep track of i, because you have to hard-code which element you're addressing ("buf.0", "buf.1", etc), rather than being able to look it up directly from an index variable like, well, an array ("buf[i]").

Plus the fact that they can't conform to protocols really limits their usefulness in filling the role of a "normal" type. For instance, even though you could easily create the normal, 64-bit hash value from an instance of a `(Int32, Int32)` simply by concatenating the two elements' bits, you can't create a `Dictionary<(Int32, Int32), SomeType>` because there's no mechanism to get `(Int, Int)` to conform to Dictionary's `Hashable` requirement.

Could both of these features get added to Tuples? From a technically PoV, sure, and it's been discussed in previous threads. IMHO we'd get more benefit out of adding support for variadic generic parameters and using literal values as generic parameters (both of which have also been previously discussed).

But it's all out of scope until after Swift 4 comes out, because none of this affects ABI or source-code compatibility.

- Dave Sweeris
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

23

The other issue is when you're importing an existing enum from a fixed size data structure which has a fixed array count:

// in include/*.h
#define MAX_ELEMENTS 100
typedef struct {
  size_t count;
  int elements[MAX_ELEMENTS];
} MyData

This gets imported into Swift as a 100-element tuple, which means you can't do elements[i] to look them up. And while a case statement will be hand-rollable, given that this is a compile-time value which could be changed in the future, it won't be safe.

You can end up with such unrolled loops (e.g. https://github.com/apple/swift-corelibs-foundation/blob/46b4e84a263d4fb657d84dfa4ca5b8fb4ed1f75f/Foundation/NSDecimal.swift#L1546-L1591 ) but they're pretty unwieldy for something that should be a compile-time check.

It can be hacked with mirror, but well, it's a hack:

  subscript(index:Int) -> Int {
      let all = Mirror(reflecting:self.elements).children.map({$0.value as! Int})
      return all[index]
  }

Alex

···

On 30 May 2017, at 16:27, David Sweeris via swift-evolution <swift-evolution@swift.org> wrote:

On May 30, 2017, at 03:25, Pavol Vaskovic <pali@pali.sk <mailto:pali@pali.sk>> wrote:

On Tue, May 30, 2017 at 7:51 AM, David Sweeris <davesweeris@mac.com <mailto:davesweeris@mac.com>> wrote:

`(Int, Int, Int, Int)` isn't *that* horrible compared to "[Int x 4]", but would you want to replace "[Int8 x 10000]" with the multipage-long tuple equivalent?

:flushed:
It would be really helpful to my understanding, if you spoke about a practical use case. This reads as a contrived counterexample to me


If your type really has 10 000 values in it, why does it have to be static, why doesn't normal Array fit the bill?

Sure, I meant it as an example of how unwieldy large tuples can be. Even medium ones, really. Tuples are great for bundling a few values, but much more than that any they become annoying to work with because there's no easy way to iterate through them. As a more realistic example, what if you want a stack-allocated 256-element buffer (which is a real possibility since statically-allocated C arrays are imported as tuples)? You have to manually keep track of i, because you have to hard-code which element you're addressing ("buf.0", "buf.1", etc), rather than being able to look it up directly from an index variable like, well, an array ("buf[i]").

24

Static-Sized Arrays

My preference would still be to build this from four separate features:

1. Magic tuple conformances: We already want to be able to automatically conform tuples to protocols like Equatable, Hashable, and Comparable. These can all be compiler magic; they don't have to be definable in userspace.

2. Conform tuples to Collection: The Element type should be the most specific common supertype of the tuple's elements. If all the elements are the same type, it would be that type. The Index and IndexDistance types should be Int.

3. Conform same-type tuples to MutableCollection: If all elements are the same type, you can also modify the values. (If their types vary in any way, however, it would not be safe to allow mutations, since you could assign the wrong type to an element.)

3. Add sugar for a tuple of N identical elements: Probably something like `4 * Int`, but opinions can vary.

This solution avoids adding another structural type to the language or introducing non-type generic parameters. It also addresses other needs: 1 and 2 are desirable features in their own right which address other use cases in addition to this one. And it's nicely incremental, which is always a plus.

Exactly this. The whole conversation is wildly out of scope and the critical technical details about implementation of the feature is either missing or inaccurate, but I'll chime in for future reference to say that this particular color of the shed is, in my view, the most congruent with Swift's direction.

+1

···

Sent from my iPad

On Jun 2, 2017, at 7:33 AM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:
On Fri, Jun 2, 2017 at 04:28 Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:

On May 28, 2017, at 11:37 PM, Daryle Walker via swift-evolution <swift-evolution@swift.org> wrote:

--
Brent Royal-Gordon
Architechies

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

25

My favorite proposal so far is one that was posted a while ago, [Int * 4]. I think that this syntax looks pretty Swifty. There isn't an oddball subscript operator like with Int[4], and there isn't a need to allow generics to support values as parameters. It's clear that [Int * 4] will be array-like and contain four Ints. For multidimensional arrays we could use [Int * (2,3)]. For an array of tuples, [(x: Int, y: Int) * 4]. I'm not sure why nested static arrays would be needed when multidimentionality is provided out of the box, but presumably the syntax would support them; you would just need to subscript the arrays one at a time instead of with a single subscript operator, e.g., a[i][j] instead of a[i, j].

I'm imagining this syntax working like [T] does now as a shorthand for Array<T>, although I'm not sure what [Int * 4] should be short for (StaticArray<Int, 4>? Vector4<Int>? ...). Constructors for static arrays would be called using [Int * 4](args). I'm thinking the constructors would be [T * 4](filledWith: T), [T * 4](filledBy: (Int)->T), and an initializer taking a Sequence that fails in some manner on a dimension mismatch.

Even with that syntax I'd say there should be a means of handling it in a general purpose way.

For example, let's say you defined that syntax as an operator:

  func * <T>(lhs: T.self, rhs: Int) -> (type: T.self, size:Int) { return (type: lhs, size: rhs) }

Now you have an explicit tuple describing what it is you want to do, which the compiler can now pass to a type during compilation to do with as it pleases. In this case it would pass to some FixedArray type which can use the type and size to optimise itself. Not sure on the specifics of how just yet, but point being to try to make this a part of the language that others can use, rather than simply being some form of compiler magic.

My reasoning being that it may be useful to have other type operators in future, and/or other types able to take and use the same information.

For example, I briefly discussed once the possibility of a Float variant whose compatibility would be limited by its target precision, and use ± as an operator so that I could define for example:

  var a:Float±0.1 = 0.5
  var b:Float±0.5 = 5.0
  a = b // error; precision mismatch (b's precision is too low to guarantee accuracy)
  b = a // this is fine, as a is "more precise" than b

Now put aside whether that idea is actually useful or not; my point is that I'd like support for fixed-size arrays to be general purpose, as there are other possible uses for the same basic capabilities (i.e- type variables).

The key thing really is that we need some way for the compiler to recognise that a type is being refined somehow, and compile it separately as appropriate. I mentioned generics style variable passing because to me this is the most logical way to pass information into a type, not because I want it to be the default syntax at the call site; I fully support other shorthands for the actual passing of data, the key for me is being able to leverage the same kind of type-refining capabilities in my own types, rather than this whole thing just being focused solely on fixed-sized arrays implemented with compiler magic.

···

On 2 Jun 2017, at 07:38, Robert Bennett <rltbennett@icloud.com> wrote:

On Jun 1, 2017, at 7:36 AM, Haravikk via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Just wanted to add my two-cents to this discussion, but in terms of syntax I think that the basic method for specifying size should be with some kind of type variables, like so:

  struct MyFixedArray<T, size:Int> { 
 }

The idea being that we can then use size as a variable anywhere within the code for MyFixedArray, but unlike other variables it is determined at compile time, so should be optimised accordingly. As with generics, setting a type variable effectively creates a variant type so for example, a MyFixedArray<Int, size:3> and a MyFixedArray<Int, size:4> would no longer be directly compatible as they may differ internally.

This would be useful not just for fixed arrays, but other possibly type variations as well. Ideally it should be possible to specify a default value for type variables; while this wouldn't be useful for fixed arrays, it may be useful for other type variants.

To better suit the specific use-case of arrays, we could also add some useful attributes or keywords, for example, reusing subscript could give us:

struct MyFixedArray<T, subscript size:Int> { 
 }
let foo:MyFixedArray[4] = [1, 2, 3, 4] // with T being inferred, this is a shorthand for specifying a size of 4

Type variables could also be usable with generics, like-so:

// only accept fixed arrays of same or smaller size:
func myMethod<FA>(values:FA) where FA:FixedArray, FA.size <= Self.size { 
 }

These are the kind of general purpose capabilities I'd like to see at some point, as the usefulness extends beyond just fixed-size arrays.

However, on the subject of fixed-size arrays specifically, one other possibility to explore is the concept of Tuple repetition and subscripting. For example, it would be interesting if we could do things like:

  var foo:(Int)[4] = 0 // Initialises four Ints, all set initially to zero
  for i in 0 ..< 4 { foo[i] = i } // values are no 0, 1, 2, 3

This can be especially interesting when you get into more complex tuples like so:

  var bar:(x:Int, y:Int)[10] = (x: 0, y: 0) // Initialises 10 pairs of Ints, all initially set to zero
  for i in 0 ..< 10 { bar[i].x = i; bar[i].y = i } // here we need to use .x and .y to access the values of each pair

Of course this would have the same performance characteristics as standard tuples, but it's an interesting means for creating quick, fixed-size arrays in a flexible way. Part of the idea here is that by subscripting tuples, we avoid the need for a general subscript on all types, keeping that available for use-cases like the above.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

26

Static-Sized Arrays

My preference would still be to build this from four separate features:

1. Magic tuple conformances: We already want to be able to
automatically conform tuples to protocols like Equatable, Hashable,
and Comparable. These can all be compiler magic; they don't have to be
definable in userspace.

2. Conform tuples to Collection: The Element type should be the most
specific common supertype of the tuple's elements. If all the elements
are the same type, it would be that type. The Index and IndexDistance
types should be Int.

3. Conform same-type tuples to MutableCollection: If all elements are
the same type, you can also modify the values. (If their types vary in
any way, however, it would not be safe to allow mutations, since you
could assign the wrong type to an element.)

3. Add sugar for a tuple of N identical elements: Probably something
like `4 * Int`, but opinions can vary.

Static-sized arrays should not be shoved into being a tuple with funny settings; that introduces subtleties into the tuple concept only because of jammed-in array support. The fact 3 separate-proposal-worthy features need to be introduced first, in which at least one is dubious in value (#2, since a lot of times the common type would be “Any”), should be a code smell on this approach.

I think any complete solution depends on at least two more things:

1. adding the ability to get an UnsafePointer to an immutable instance
  of value type

Do you mean something besides applying the address-of operator (I’m not sure what that is.) to “myArray.0”?

What are you thinking of doing with such unsafe-pointers? In this thread, I had “array of T” or “[of T]” to make array-segment references, so you can make a function that can take an array of a certain type without specializing for each shape. (Worse, since we only have type-based generic parameters, we couldn’t generate such functions.) It’s the same as using “T” as a function parameter type in C.

While thinking of this response, I looked at the same section of SwiftDoc.org <http://swiftdoc.org/&gt; for UnsafePointer, and there were Unsafe(Mutable)BufferPointer. These types do the same job as my theoretical “[of T]”, so maybe I should defer to those. We would add a global function to convert given arrays to unsafe-buffer-pointers.

2. support for leaving some of the elements uninitialized, or
  alternatively, a variation of this type that is RangeReplaceable but
  also bounded in capacity.

AFAIK, all objects have to be fully initialized before the first read. If that’s the case, then skipping element initialization (which I can understand wanting when using a large array for a mathematical matrix type) would require a separate proposal, since we would need a full consideration of the consequences. (What happens when reading an uninitialized element?) For the variant, couldn’t that be implemented with a library type (since you need a per-object list of current elements), maybe using the base array type as a generic parameter.

···

On Jun 2, 2017, at 10:26 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Fri Jun 02 2017, Brent Royal-Gordon <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On May 28, 2017, at 11:37 PM, Daryle Walker via swift-evolution >>> <swift-evolution@swift.org> wrote:

—
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com

27

>
> I agree strongly that the syntax looks awkward — imho
> var v: Vector<Int, size: 3>
> would be a much better fit than
> var v array 3 of Int
>
> As much as I want to have "real" arrays, I don't think we should add new
keywords for them.

Yeah, a "fixed-size array" is probably the most obvious use-case for
allowing literal values to be generic parameters. In fact, at that point,
they'd just be another type... no special support needed, other than
validating the count when assigning array literals to them.

The syntax that gained some traction last time they were seriously
discussed would also be better, IMHO:
let x: [Int x 4]
or maybe it was this?
let x: [Int * 4]
Either way, it's more concise, far easier to read (IMHO), and doesn't need
new keyword(s).

I have not followed all previous discussions on this (so sorry if it was
already proposed and/or discussed) but from the point of view of the
"standard mathematics writing", it seems to me that it should rather be
[Int^4] .

Indeed the three dimensional space built by combining the set of real
numbers R is noted R^3 or alternatively RxRxR (but for larger dimensions
you certainly do not want this writing!)

Strictly speaking Int^4 would be mathematically speaking more correct but
[Int^4] has the advantage of making clear that this is indeed an array.

There are many aspects in the initial proposal that certainly need a more
expert eye than mine. I have one question though. It seems to me that the
constant expressions as known as constexpr in C++11 would be allowed as
well. Is that right? If yes, are there any differences in the proposal to
what is allowed in C++11?

Nicolas

···

On Mon 29. May 2017 at 20:57, David Sweeris via swift-evolution < swift-evolution@swift.org> wrote:

> On May 29, 2017, at 01:12, Tino Heth via swift-evolution < > swift-evolution@swift.org> wrote:

- Dave Sweeris
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

28

There was someone a few weeks ago trying to port his Go game to Swift from (I believe) C++ and found out that the lack of fixed-size arrays was causing the move-computing algorithm to slow down significantly.

This is due to fixed arrays being able to live on stack, while "normal Array" is dynamically allocated on heap, etc.

Really ? Isn’t it due to the value semantic of swift arrays ?

If this is the former, its algorithm can probably be tweak to reuse the array and require less allocations.

Unless if you algorithm is eager in memory allocation/deallocation, you shouldn't get a significant difference between static array and dynamic array.

···

Le 30 mai 2017 Ă  12:42, Charlie Monroe via swift-evolution <swift-evolution@swift.org> a Ă©crit :

10 000 may have been David's exageration, but imagine trying to form a chessboard using tuples - aside from the fact that you can't iterate over the tuple, the tuple type would be huge - instead of ChessPiece[8][8] (or similar syntax), you get:

((ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece))

And the practical use isn't just games - just think of any fixed-size matrices.

On May 30, 2017, at 12:25 PM, Pavol Vaskovic via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Tue, May 30, 2017 at 7:51 AM, David Sweeris <davesweeris@mac.com <mailto:davesweeris@mac.com>> wrote:

`(Int, Int, Int, Int)` isn't *that* horrible compared to "[Int x 4]", but would you want to replace "[Int8 x 10000]" with the multipage-long tuple equivalent?

:flushed:
It would be really helpful to my understanding, if you spoke about a practical use case. This reads as a contrived counterexample to me


If your type really has 10 000 values in it, why does it have to be static, why doesn't normal Array fit the bill?

--Pavol
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

29

Static-sized arrays should not be shoved into being a tuple with funny settings; that introduces subtleties into the tuple concept only because of jammed-in array support. The fact 3 separate-proposal-worthy features need to be introduced first,

The fact that I described the tuple-based alternative in more words than it takes to write "Just add a non-nominal fixed-size array type" doesn't mean that "Just add a non-nominal fixed-size array type" is actually a simpler proposal. As it often does, the word "just" hides a ton of complexity. Adding a non-nominal type is a *big deal*. There are only a few, and each one of them requires lots of special handling.

My proposal makes non-nominal types less special, then uses the reduced special-ness to add new functionality. Yours introduces additional special cases to add the new functionality.

in which at least one is dubious in value (#2, since a lot of times the common type would be “Any”),

Yes, the subscript would sometimes be `Any`, or `CustomStringConvertible`, or `AnyHashable`, or a combination like `AnyHashable & Codable`. So what? Even `Any` is a useful type sometimes.

I think any complete solution depends on at least two more things:

1. adding the ability to get an UnsafePointer to an immutable instance
  of value type

Do you mean something besides applying the address-of operator (I’m not sure what that is.) to “myArray.0”?

That would be `&myArray.0`, which isn't allowed if `myArray` is immutable, because it's designed for `inout` and merely overloaded for address-of. (Well, my understanding is that there are slightly deeper reasons too, but I'll let others explain that.)

···

On Jun 4, 2017, at 6:56 AM, Daryle Walker via swift-evolution <swift-evolution@swift.org> wrote:

--
Brent Royal-Gordon
Architechies

30

There’s enough interest in a “constexpr” feature that I suspect it (or something like it) will eventually get added, but as far as I know it’s not on any official todo list or roadmap or anything.

- Dave Sweeris

···

On May 29, 2017, at 2:39 PM, Nicolas Fezans <nicolas.fezans@gmail.com> wrote:

There are many aspects in the initial proposal that certainly need a more expert eye than mine. I have one question though. It seems to me that the constant expressions as known as constexpr in C++11 would be allowed as well. Is that right? If yes, are there any differences in the proposal to what is allowed in C++11?

31

Sorry if this has been suggested before, but what is wrong with something along

let x: Int[4]
let x: Int<4>

In case of multi-dimension arrays:

let x: Int[4][4]
let x: Int[4, 4]
let x: Int<4><4>
let x: Int<4, 4>

I see small issues with each that would need to be discussed - the first would disallow subscripts on types. Subscripts currently cannot be static, at least now anyway, though. The second syntax is too close to generics, which may be confusing...

···

On May 29, 2017, at 11:39 PM, Nicolas Fezans via swift-evolution <swift-evolution@swift.org> wrote:

On Mon 29. May 2017 at 20:57, David Sweeris via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

> On May 29, 2017, at 01:12, Tino Heth via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
>
> I agree strongly that the syntax looks awkward — imho
> var v: Vector<Int, size: 3>
> would be a much better fit than
> var v array 3 of Int
>
> As much as I want to have "real" arrays, I don't think we should add new keywords for them.

Yeah, a "fixed-size array" is probably the most obvious use-case for allowing literal values to be generic parameters. In fact, at that point, they'd just be another type... no special support needed, other than validating the count when assigning array literals to them.

The syntax that gained some traction last time they were seriously discussed would also be better, IMHO:
let x: [Int x 4]
or maybe it was this?
let x: [Int * 4]
Either way, it's more concise, far easier to read (IMHO), and doesn't need new keyword(s).

I have not followed all previous discussions on this (so sorry if it was already proposed and/or discussed) but from the point of view of the "standard mathematics writing", it seems to me that it should rather be [Int^4] .

Indeed the three dimensional space built by combining the set of real numbers R is noted R^3 or alternatively RxRxR (but for larger dimensions you certainly do not want this writing!)

Strictly speaking Int^4 would be mathematically speaking more correct but [Int^4] has the advantage of making clear that this is indeed an array.

There are many aspects in the initial proposal that certainly need a more expert eye than mine. I have one question though. It seems to me that the constant expressions as known as constexpr in C++11 would be allowed as well. Is that right? If yes, are there any differences in the proposal to what is allowed in C++11?

Nicolas

- Dave Sweeris
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

32

Eliminating the dynamic allocations and extra indirections caused by the Swift array implementation can make a huge difference, not just in itself, but it also gives the compiler more opportunities to optimize the code. In my code (Monte Carlo simulations for a Go-playing program) I was able to gain a factor of 5 by using the ugly workaround of importing fixed-size arrays from C.

Anders

···

On May 30, 2017, at 3:36 PM, Jean-Daniel via swift-evolution <swift-evolution@swift.org> wrote:

Le 30 mai 2017 Ă  12:42, Charlie Monroe via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a Ă©crit :

There was someone a few weeks ago trying to port his Go game to Swift from (I believe) C++ and found out that the lack of fixed-size arrays was causing the move-computing algorithm to slow down significantly.

This is due to fixed arrays being able to live on stack, while "normal Array" is dynamically allocated on heap, etc.

Really ? Isn’t it due to the value semantic of swift arrays ?

If this is the former, its algorithm can probably be tweak to reuse the array and require less allocations.

Unless if you algorithm is eager in memory allocation/deallocation, you shouldn't get a significant difference between static array and dynamic array.

33

It's not just about the cost of allocation; heap accesses are incredibly slow compared to stack accesses.

···

On May 30, 2017, at 5:36 PM, Jean-Daniel via swift-evolution <swift-evolution@swift.org> wrote:

Le 30 mai 2017 Ă  12:42, Charlie Monroe via swift-evolution <swift-evolution@swift.org> a Ă©crit :

There was someone a few weeks ago trying to port his Go game to Swift from (I believe) C++ and found out that the lack of fixed-size arrays was causing the move-computing algorithm to slow down significantly.

This is due to fixed arrays being able to live on stack, while "normal Array" is dynamically allocated on heap, etc.

Really ? Isn’t it due to the value semantic of swift arrays ?

If this is the former, its algorithm can probably be tweak to reuse the array and require less allocations.

Unless if you algorithm is eager in memory allocation/deallocation, you shouldn't get a significant difference between static array and dynamic array.

10 000 may have been David's exageration, but imagine trying to form a chessboard using tuples - aside from the fact that you can't iterate over the tuple, the tuple type would be huge - instead of ChessPiece[8][8] (or similar syntax), you get:

((ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece),
(ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece, ChessPiece))

And the practical use isn't just games - just think of any fixed-size matrices.

On May 30, 2017, at 12:25 PM, Pavol Vaskovic via swift-evolution <swift-evolution@swift.org> wrote:

On Tue, May 30, 2017 at 7:51 AM, David Sweeris <davesweeris@mac.com> wrote:

`(Int, Int, Int, Int)` isn't *that* horrible compared to "[Int x 4]", but would you want to replace "[Int8 x 10000]" with the multipage-long tuple equivalent?

:flushed:
It would be really helpful to my understanding, if you spoke about a practical use case. This reads as a contrived counterexample to me


If your type really has 10 000 values in it, why does it have to be static, why doesn't normal Array fit the bill?

--Pavol
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

34

I agree strongly that the syntax looks awkward — imho
var v: Vector<Int, size: 3>
would be a much better fit than
var v array 3 of Int

As much as I want to have "real" arrays, I don't think we should add new keywords for them.

Should Swift be closed to adding any new keywords, beside those that start with “#”? Or is it just not using a keyword for static-sized arrays? If yes for that last question, are you proposing that nominal arrays be dropped, since “array” is still needed as a tag to introduce them?

Yeah, a "fixed-size array" is probably the most obvious use-case for allowing literal values to be generic parameters. In fact, at that point, they'd just be another type... no special support needed, other than validating the count when assigning array literals to them.

Still need some sort of special support. There either needs to be a directive inside the struct to create a contiguous block of objects, or your static-sized array generic struct needs to be a straight-up magical type. When I first had a similar idea, I had to consider how a directive would interact with other stored properties, or would I block said interactions. At that point, what’s the difference between a struct with a bunch of tweaks and a new category of type. We didn’t make enum a struct with funny settings, after all.

The syntax that gained some traction last time they were seriously discussed would also be better, IMHO:
let x: [Int x 4]
or maybe it was this?
let x: [Int * 4]
Either way, it's more concise, far easier to read (IMHO), and doesn't need new keyword(s).

I have not followed all previous discussions on this (so sorry if it was already proposed and/or discussed) but from the point of view of the "standard mathematics writing", it seems to me that it should rather be [Int^4] .

C++ has its set of punctuators fixed by the language. Swift doesn’t do this; its punctuators are mostly user level, just like identifiers. And just like identifiers, there are a small set of punctuators reserved for the language itself, an analogue of keywords. Using “x”, “*”, or “^” would take some string out of free use and into (conditional) reserved use. Since I’m already using “array” as a tag for nominal arrays, why not reuse the word for immediate arrays.

Indeed the three dimensional space built by combining the set of real numbers R is noted R^3 or alternatively RxRxR (but for larger dimensions you certainly do not want this writing!)

Strictly speaking Int^4 would be mathematically speaking more correct but [Int^4] has the advantage of making clear that this is indeed an array.

If this change like this is made, what about “[N for Int]” for immediate arrays and “[for Int]” for array-segment references? The count goes first so nested arrays keep their extent priority order the same as C’s nested arrays. (Otherwise, the C to Swift source-code converter would have to flip the order of the extents.) Using “of” for the separator would be better, but that would violate the desire to avoid new keywords. Of course, how would nominal arrays be declared under this design? Or would those be dropped?

···

On May 29, 2017, at 5:39 PM, Nicolas Fezans via swift-evolution swift-evolution@swift.org wrote:
On Mon 29. May 2017 at 20:57, David Sweeris via swift-evolution swift-evolution@swift.org wrote:

On May 29, 2017, at 01:12, Tino Heth via swift-evolution swift-evolution@swift.org wrote:

There are many aspects in the initial proposal that certainly need a more expert eye than mine. I have one question though. It seems to me that the constant expressions as known as constexpr in C++11 would be allowed as well. Is that right? If yes, are there any differences in the proposal to what is allowed in C++11?

—

Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com

35

I don’t see how static sized array would solve that issue.

If swift wants to keep value semantic it has to support COW or a similar machinery.
If you want to avoid COW and force the array to be allocated on the stack, it will impose swift to copy it at each function boundary (there is no @unescape for array to tell the compiler it can safely pass a reference).

If what you want is just a preallocated array with reference semantic, wrap it in a class. You should get the same speed up than when using imported C arrays.

···

Le 31 mai 2017 Ă  01:47, Anders Kierulf <anders@smartgo.com> a Ă©crit :

On May 30, 2017, at 3:36 PM, Jean-Daniel via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Le 30 mai 2017 Ă  12:42, Charlie Monroe via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a Ă©crit :

There was someone a few weeks ago trying to port his Go game to Swift from (I believe) C++ and found out that the lack of fixed-size arrays was causing the move-computing algorithm to slow down significantly.

This is due to fixed arrays being able to live on stack, while "normal Array" is dynamically allocated on heap, etc.

Really ? Isn’t it due to the value semantic of swift arrays ?

If this is the former, its algorithm can probably be tweak to reuse the array and require less allocations.

Unless if you algorithm is eager in memory allocation/deallocation, you shouldn't get a significant difference between static array and dynamic array.

Eliminating the dynamic allocations and extra indirections caused by the Swift array implementation can make a huge difference, not just in itself, but it also gives the compiler more opportunities to optimize the code.

36

FWIW, I made a similar comment in a similar thread, and IIRC the notion was generally frowned upon. [swift-evolution] Proposal: Contiguous Variables (A.K.A. Fixed Sized Array Type)

Perhaps optimizations made over the past — wow, 1.25 years — have addressed Jordan’s concern about a “needless amount of extra work for the compiler”?

Also, I thought we’d decided this was out of scope for now? Am I thinking of something else, or are we just talking about it anyway, for funsies?

- Dave Sweeris

···

On Jun 6, 2017, at 10:55, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Jun 4, 2017, at 6:56 AM, Daryle Walker via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

in which at least one is dubious in value (#2, since a lot of times the common type would be “Any”),

Yes, the subscript would sometimes be `Any`, or `CustomStringConvertible`, or `AnyHashable`, or a combination like `AnyHashable & Codable`. So what? Even `Any` is a useful type sometimes.

37

I already mentioned that I do not want to use generics syntax.

For “Int[4]” or similar: we don’t use C’s (cute) “declaration looks like use” syntax. The declaration wouldn’t spiral out, but be strictly in one direction. That means that the bracketed part would array-ize the type expression to its left. That means that “Int[4][6]” would make the widest span the extent with six elements, the reverse direction of C’s array declarations. However, dereferencing still happens in C’s order. So now it’s double confusing, unless we break Swift’s philosophy and make nested array extent order to be the same as C. Or do what I did and make the extent length precede the element type.

I kept multiple-dimension support out of immediate arrays for similar reasons. Think about “Int[5, 6]”, does that store the elements like “Int[5][6]” or “Int[6][5]”? (And is that like C’s order or my theoretical Swift reversed order?) Instead of worrying about that in quick & dirty arrays, I moved said concerns to a full declaration block syntax for arrays, and even allow overriding of row-major vs. column-major. And the immediate arrays use tuple’s “object.index” for dereference; I would have to find a way to make that work with multiple coordinates, but not for nominal arrays which can use the subscript operator. (And no, I don’t support “” on immediate arrays, since they’re supposed to model tuples (with homogenous member type), which are generally closed for extensions.)

···

On May 30, 2017, at 2:32 AM, Charlie Monroe via swift-evolution swift-evolution@swift.org wrote:

Sorry if this has been suggested before, but what is wrong with something along

let x: Int[4]

let x: Int<4>

In case of multi-dimension arrays:

let x: Int[4][4]

let x: Int[4, 4]

let x: Int<4><4>

let x: Int<4, 4>

I see small issues with each that would need to be discussed - the first would disallow subscripts on types. Subscripts currently cannot be static, at least now anyway, though. The second syntax is too close to generics, which may be confusing...

—

Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com

Another fixed-sized scoped-storage array manifesto spitball session
38

Creating an Array in Swift immediately makes a heap allocation. You then get COW semantics, but you already made a heap allocation (unless the array is empty).

https://github.com/apple/swift/blob/master/stdlib/public/core/ContiguousArrayBuffer.swift#L208 <https://github.com/apple/swift/blob/master/stdlib/public/core/Arrays.swift.gyb#L946&gt;

With sized arrays, they can live on stack and the compiler can access the elements by referencing the stack frame (quick access), vs. the array, where it needs to dereference the pointer. Not to mention that the compiler can actually make some elements accessible via registers.

Might seem like a small gain, but if you are making something that needs to compute really fast, even getting 2x speed is fast (and accessing heap via Array is more than 2x compared to accessing something on the stack). Not to mention if you create a lot of arrays (e.g. matrix computations), creating a static-sized array means just adding the size to the stack pointer.

···

On May 31, 2017, at 4:16 PM, Jean-Daniel <mailing@xenonium.com> wrote:

Le 31 mai 2017 Ă  01:47, Anders Kierulf <anders@smartgo.com <mailto:anders@smartgo.com>> a Ă©crit :

On May 30, 2017, at 3:36 PM, Jean-Daniel via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Le 30 mai 2017 Ă  12:42, Charlie Monroe via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a Ă©crit :

There was someone a few weeks ago trying to port his Go game to Swift from (I believe) C++ and found out that the lack of fixed-size arrays was causing the move-computing algorithm to slow down significantly.

This is due to fixed arrays being able to live on stack, while "normal Array" is dynamically allocated on heap, etc.

Really ? Isn’t it due to the value semantic of swift arrays ?

If this is the former, its algorithm can probably be tweak to reuse the array and require less allocations.

Unless if you algorithm is eager in memory allocation/deallocation, you shouldn't get a significant difference between static array and dynamic array.

Eliminating the dynamic allocations and extra indirections caused by the Swift array implementation can make a huge difference, not just in itself, but it also gives the compiler more opportunities to optimize the code.

I don’t see how static sized array would solve that issue.

If swift wants to keep value semantic it has to support COW or a similar machinery.
If you want to avoid COW and force the array to be allocated on the stack, it will impose swift to copy it at each function boundary (there is no @unescape for array to tell the compiler it can safely pass a reference).

If what you want is just a preallocated array with reference semantic, wrap it in a class. You should get the same speed up than when using imported C arrays.

39

If you replace “heap access” with “heap allocation/deallocation” in the argument, then the performance differences become very relevant.

···

On May 31, 2017, at 10:15 AM, David Waite via swift-evolution <swift-evolution@swift.org> wrote:

On May 31, 2017, at 9:28 AM, Robert Bennett via swift-evolution <swift-evolution@swift.org> wrote:

Without static arrays, swift cannot be used in high performance applications. The cost of repeated heap accesses is simply too high. And tuples are not ergonomic enough to use in the same manner as arrays. So I think we do need to add static arrays to Swift, if not necessarily in Swift 4.

I don’t quite understand why there is such a massive heap access cost vs stack. My understanding is the instructions for both are pointer dereferences, both stack and heap memory equally cache, neither require read or write barriers with swift, and the MMU isn’t set to fault heap memory (except as a general virtual memory policy).

I understand memory-sensitive applications using static arrays within data structures, but high performance applications using stack-allocated static arrays sounds pretty restrictive in terms of use. Given value semantics, there is a lot of pressure on the optimizer to prevent those arrays from being copied on mutation and being passed into calls. The chessboard example may have been 64 bytes, or may have been 512 bytes - quite expensive if the optimizer decides a method invocation needs a copy.

-DW
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

40

I don’t quite understand why there is such a massive heap access cost vs stack. My understanding is the instructions for both are pointer dereferences, both stack and heap memory equally cache, neither require read or write barriers with swift, and the MMU isn’t set to fault heap memory (except as a general virtual memory policy).

I understand memory-sensitive applications using static arrays within data structures, but high performance applications using stack-allocated static arrays sounds pretty restrictive in terms of use. Given value semantics, there is a lot of pressure on the optimizer to prevent those arrays from being copied on mutation and being passed into calls. The chessboard example may have been 64 bytes, or may have been 512 bytes - quite expensive if the optimizer decides a method invocation needs a copy.

-DW

···

On May 31, 2017, at 9:28 AM, Robert Bennett via swift-evolution <swift-evolution@swift.org> wrote:

Without static arrays, swift cannot be used in high performance applications. The cost of repeated heap accesses is simply too high. And tuples are not ergonomic enough to use in the same manner as arrays. So I think we do need to add static arrays to Swift, if not necessarily in Swift 4.