[Planning][Request] "constexpr" for Swift 5

fclout · August 4, 2017, 5:19pm

That's not a concern with the `let` case that Robert brought up, since you can't mutate a `let` array at all.

The big thing is that unconstrained escape analysis is uncomputable. Since Swift array storage is COW, any function that receives the array as a parameter is allowed to take a reference on its storage. If the storage lives on the stack and that reference outlives the stack frame, you've got a problem. It's the same problem that motivated @escaping for closures.

You could allow storage to be on the stack by forcing user to make a pessimistic copy, which is possibly not an improvement.

···

Le 4 août 2017 à 09:21, Taylor Swift via swift-evolution <swift-evolution@swift.org> a écrit :

No, that doesn’t work. In many cases you want to mutate the elements of the array without changing its size. For example, a Camera struct which contains a matrix buffer, and some of the matrices get updated on each frame that the camera moves. The matrix buffer also stores all of the camera’s stored properties, so what would be conceptually stored properties are actually computed properties that get and set a Float at an offset into the buffer. Of course this could all be avoided if we had fixed layout guarantees in the language, and then the Camera struct could be the matrix buffer and dispense with the getters and setters instead of managing a heap buffer.

On Fri, Aug 4, 2017 at 11:02 AM, Robert Bennett via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
So, I’m getting into this thread kind of late, and I’ve only skimmed most of it, but…

A special FSA on the stack seems like the wrong direction. Wouldn’t it make more sense to have *all* value types that don’t change in size — including `let` Arrays — live on the stack? In which case, FSA would merely act like a normal `let` Array, without RangeReplaceableCollection conformance, whose elements could be changed via subscripting. I know nothing about the underlying implementation details of Swift, so I may be way off base here.

On Aug 4, 2017, at 2:18 AM, David Hart <david@hartbit.com <mailto:david@hartbit.com>> wrote:

Don’t small arrays live on the stack?

On 4 Aug 2017, at 06:35, Félix Cloutier via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

As far as I can tell, currently, all arrays live on the heap.

Le 3 août 2017 à 19:03, Robert Bennett via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a écrit :

Where do constant Arrays currently live? I hope the answer is on the stack, since their size doesn’t change.

On Aug 3, 2017, at 8:44 PM, Taylor Swift via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Thu, Aug 3, 2017 at 8:20 PM, Karl Wagner via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

The root cause, of course, is that the VLAs require new stack allocations each time, and the stack is only deallocated as one lump when the frame ends.

That is true of alloca(), but not of VLAs. VLAs are freed when they go out of scope.

Learned something today.

Anyway, if the goal is stack allocation, I would prefer that we explored other ways to achieve it before jumping to a new array-type. I’m not really a fan of a future where [3; Double] is one type and (Double, Double, Double) is something else, and Array<Double> is yet another thing.

They are completely different things.

[3; Double] is three contiguous Doubles which may or may not live on the stack.

(Double, Double, Double) is three Doubles bound to a single variable name, which the compiler can rearrange for optimal performance and may or may not live on the stack.

Array<Double> is an vector of Doubles that can dynamically grow and always lives in the heap.

From what I’ve read so far, the problem with stack-allocating some Array that you can pass to another function and which otherwise does not escape, is that the function may make an escaping reference (e.g. assigning it to an ivar or global, or capturing it in a closure).

How about if the compiler treated every Array it receives in a function as being potentially stack-allocated. The first time you capture it, it will check and copy to the heap if necessary. All subsequent escapes (including passing to other functions) use the Array known to be allocated on the heap, avoiding further checking or copying within the function.

The same goes for Dictionary, and really any arbitrary value-type with COW storage. The memory that those types allocate is part of the value, so it would be cool if we could treat it like that.

This is not true. FSAs have nothing to do with automatic storage, their static size only makes them eligible to live on the stack, as tuples are now. The defining quality of FSAs is that they are static and contiguous.
_______________________________________________
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 <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
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 <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

John_McCall · August 4, 2017, 6:15pm

That's not a concern with the `let` case that Robert brought up, since you can't mutate a `let` array at all.

The big thing is that unconstrained escape analysis is uncomputable. Since Swift array storage is COW, any function that receives the array as a parameter is allowed to take a reference on its storage. If the storage lives on the stack and that reference outlives the stack frame, you've got a problem. It's the same problem that motivated @escaping for closures.

You could allow storage to be on the stack by forcing user to make a pessimistic copy, which is possibly not an improvement.

Right. I think maybe the name people keeping using for this feature is misleading; a better name would be "inline arrays" or "directly-stored arrays". Having a fixed size is a necessary condition for storing the array elements directly, but the people asking for this feature are really asking for the different representation, not just the ability to statically constrain the size of an array.

That representation difference comes with a lot of weaknesses and trade-offs, but it's also useful sometimes.

John.

···

On Aug 4, 2017, at 1:19 PM, Félix Cloutier via swift-evolution <swift-evolution@swift.org> wrote:

Le 4 août 2017 à 09:21, Taylor Swift via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a écrit :

No, that doesn’t work. In many cases you want to mutate the elements of the array without changing its size. For example, a Camera struct which contains a matrix buffer, and some of the matrices get updated on each frame that the camera moves. The matrix buffer also stores all of the camera’s stored properties, so what would be conceptually stored properties are actually computed properties that get and set a Float at an offset into the buffer. Of course this could all be avoided if we had fixed layout guarantees in the language, and then the Camera struct could be the matrix buffer and dispense with the getters and setters instead of managing a heap buffer.

On Fri, Aug 4, 2017 at 11:02 AM, Robert Bennett via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
So, I’m getting into this thread kind of late, and I’ve only skimmed most of it, but…

A special FSA on the stack seems like the wrong direction. Wouldn’t it make more sense to have *all* value types that don’t change in size — including `let` Arrays — live on the stack? In which case, FSA would merely act like a normal `let` Array, without RangeReplaceableCollection conformance, whose elements could be changed via subscripting. I know nothing about the underlying implementation details of Swift, so I may be way off base here.

On Aug 4, 2017, at 2:18 AM, David Hart <david@hartbit.com <mailto:david@hartbit.com>> wrote:

Don’t small arrays live on the stack?

On 4 Aug 2017, at 06:35, Félix Cloutier via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

As far as I can tell, currently, all arrays live on the heap.

Le 3 août 2017 à 19:03, Robert Bennett via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a écrit :

Where do constant Arrays currently live? I hope the answer is on the stack, since their size doesn’t change.

On Aug 3, 2017, at 8:44 PM, Taylor Swift via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Thu, Aug 3, 2017 at 8:20 PM, Karl Wagner via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

The root cause, of course, is that the VLAs require new stack allocations each time, and the stack is only deallocated as one lump when the frame ends.

That is true of alloca(), but not of VLAs. VLAs are freed when they go out of scope.

Learned something today.

Anyway, if the goal is stack allocation, I would prefer that we explored other ways to achieve it before jumping to a new array-type. I’m not really a fan of a future where [3; Double] is one type and (Double, Double, Double) is something else, and Array<Double> is yet another thing.

They are completely different things.

[3; Double] is three contiguous Doubles which may or may not live on the stack.

(Double, Double, Double) is three Doubles bound to a single variable name, which the compiler can rearrange for optimal performance and may or may not live on the stack.

Array<Double> is an vector of Doubles that can dynamically grow and always lives in the heap.

From what I’ve read so far, the problem with stack-allocating some Array that you can pass to another function and which otherwise does not escape, is that the function may make an escaping reference (e.g. assigning it to an ivar or global, or capturing it in a closure).

How about if the compiler treated every Array it receives in a function as being potentially stack-allocated. The first time you capture it, it will check and copy to the heap if necessary. All subsequent escapes (including passing to other functions) use the Array known to be allocated on the heap, avoiding further checking or copying within the function.

The same goes for Dictionary, and really any arbitrary value-type with COW storage. The memory that those types allocate is part of the value, so it would be cool if we could treat it like that.

This is not true. FSAs have nothing to do with automatic storage, their static size only makes them eligible to live on the stack, as tuples are now. The defining quality of FSAs is that they are static and contiguous.
_______________________________________________
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 <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
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 <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
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

bob · August 4, 2017, 8:00pm

Sorry, not sure how I missed that .

···

On Aug 4, 2017, at 3:16 PM, Félix Cloutier <felixcloutier@icloud.com> wrote:

Le 4 août 2017 à 11:39, Robert Bennett <rltbennett@icloud.com> a écrit :

That's not a concern with the `let` case that Robert brought up, since you can't mutate a `let` array at all.

The big thing is that unconstrained escape analysis is uncomputable. Since Swift array storage is COW, any function that receives the array as a parameter is allowed to take a reference on its storage. If the storage lives on the stack and that reference outlives the stack frame, you've got a problem. It's the same problem that motivated @escaping for closures.

You could allow storage to be on the stack by forcing user to make a pessimistic copy, which is possibly not an improvement.

Good point. If this is only problematic when multiple threads are accessing an array, then it could still be worthwhile if all accesses are (provably) on the thread that created the array.

To be clear, it's a problem independently of multi-threading. `func foo() -> [Int] { return [1, 2, 3] }` is the most basic representation of it: you can't store the array in the stack frame if you return it. (To be fair, that one would be caught by escape analysis of any quality.) `func foo() { bar([1, 2, 3, 4]) }` is another example: if you don't know what `bar` does with the array, you can't store it on the stack because it might pass it to an object that lives on the heap and outlives `foo`, for instance. @escaping solves that problem for closures by specifically annotating parameters when the assigned closure could still be referenced after the called function returns.

And pessimistic copying might still be worth it for arrays below a certain size — for instance, copying an Array<Int> of length 1 (and recall that the array in question is a constant so its size is known at compile time) would definitely be worth not having that array in heap memory.

You only need pessimistic copies when that copy escapes, and since it escapes, it needs to live on the heap by definition. Right now an array of size 1 passed to 4 objects on the heap has one single backing representation. With pessimistic copies, you'd get 4 times that buffer of size 1, which is definitely not an improvement.

Going back to the literal notion of FSAs — fixed size arrays not necessarily on the stack — I think that simply copying Array’s implementation sans RangeReplaceableCollection conformance is not a bad way to go. Any optimizations used for `let` Arrays could probably be applied to this type of FSA.

We're actually splitting this in multiple directions. John talks of variable-sized arrays necessarily on the stack. :)

I see two useful characteristics to fixed-size arrays, which, uncoincidentally, are what it takes to use them for C interop:

Their storage is inlined into their container (whether it be the stack or an object)
Their length is part of their type (and not directly included with the data itself)

This is also enough to implement fixed-size arrays not necessarily on the stack, mind you.

Félix

bob · August 4, 2017, 6:39pm

That's not a concern with the `let` case that Robert brought up, since you can't mutate a `let` array at all.

The big thing is that unconstrained escape analysis is uncomputable. Since Swift array storage is COW, any function that receives the array as a parameter is allowed to take a reference on its storage. If the storage lives on the stack and that reference outlives the stack frame, you've got a problem. It's the same problem that motivated @escaping for closures.

You could allow storage to be on the stack by forcing user to make a pessimistic copy, which is possibly not an improvement.

Good point. If this is only problematic when multiple threads are accessing an array, then it could still be worthwhile if all accesses are (provably) on the thread that created the array. And pessimistic copying might still be worth it for arrays below a certain size — for instance, copying an Array<Int> of length 1 (and recall that the array in question is a constant so its size is known at compile time) would definitely be worth not having that array in heap memory.

Going back to the literal notion of FSAs — fixed size arrays not necessarily on the stack — I think that simply copying Array’s implementation sans RangeReplaceableCollection conformance is not a bad way to go. Any optimizations used for `let` Arrays could probably be applied to this type of FSA.

···

On Aug 4, 2017, at 2:15 PM, John McCall via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Aug 4, 2017, at 1:19 PM, Félix Cloutier via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

That's not a concern with the `let` case that Robert brought up, since you can't mutate a `let` array at all.

The big thing is that unconstrained escape analysis is uncomputable. Since Swift array storage is COW, any function that receives the array as a parameter is allowed to take a reference on its storage. If the storage lives on the stack and that reference outlives the stack frame, you've got a problem. It's the same problem that motivated @escaping for closures.

You could allow storage to be on the stack by forcing user to make a pessimistic copy, which is possibly not an improvement.

Right. I think maybe the name people keeping using for this feature is misleading; a better name would be "inline arrays" or "directly-stored arrays". Having a fixed size is a necessary condition for storing the array elements directly, but the people asking for this feature are really asking for the different representation, not just the ability to statically constrain the size of an array.

That representation difference comes with a lot of weaknesses and trade-offs, but it's also useful sometimes.

John.

Le 4 août 2017 à 09:21, Taylor Swift via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a écrit :

No, that doesn’t work. In many cases you want to mutate the elements of the array without changing its size. For example, a Camera struct which contains a matrix buffer, and some of the matrices get updated on each frame that the camera moves. The matrix buffer also stores all of the camera’s stored properties, so what would be conceptually stored properties are actually computed properties that get and set a Float at an offset into the buffer. Of course this could all be avoided if we had fixed layout guarantees in the language, and then the Camera struct could be the matrix buffer and dispense with the getters and setters instead of managing a heap buffer.

On Fri, Aug 4, 2017 at 11:02 AM, Robert Bennett via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
So, I’m getting into this thread kind of late, and I’ve only skimmed most of it, but…

A special FSA on the stack seems like the wrong direction. Wouldn’t it make more sense to have *all* value types that don’t change in size — including `let` Arrays — live on the stack? In which case, FSA would merely act like a normal `let` Array, without RangeReplaceableCollection conformance, whose elements could be changed via subscripting. I know nothing about the underlying implementation details of Swift, so I may be way off base here.

On Aug 4, 2017, at 2:18 AM, David Hart <david@hartbit.com <mailto:david@hartbit.com>> wrote:

Don’t small arrays live on the stack?

On 4 Aug 2017, at 06:35, Félix Cloutier via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

As far as I can tell, currently, all arrays live on the heap.

Le 3 août 2017 à 19:03, Robert Bennett via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a écrit :

Where do constant Arrays currently live? I hope the answer is on the stack, since their size doesn’t change.

On Aug 3, 2017, at 8:44 PM, Taylor Swift via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Thu, Aug 3, 2017 at 8:20 PM, Karl Wagner via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

The root cause, of course, is that the VLAs require new stack allocations each time, and the stack is only deallocated as one lump when the frame ends.

That is true of alloca(), but not of VLAs. VLAs are freed when they go out of scope.

Learned something today.

Anyway, if the goal is stack allocation, I would prefer that we explored other ways to achieve it before jumping to a new array-type. I’m not really a fan of a future where [3; Double] is one type and (Double, Double, Double) is something else, and Array<Double> is yet another thing.

They are completely different things.

[3; Double] is three contiguous Doubles which may or may not live on the stack.

(Double, Double, Double) is three Doubles bound to a single variable name, which the compiler can rearrange for optimal performance and may or may not live on the stack.

Array<Double> is an vector of Doubles that can dynamically grow and always lives in the heap.

From what I’ve read so far, the problem with stack-allocating some Array that you can pass to another function and which otherwise does not escape, is that the function may make an escaping reference (e.g. assigning it to an ivar or global, or capturing it in a closure).

How about if the compiler treated every Array it receives in a function as being potentially stack-allocated. The first time you capture it, it will check and copy to the heap if necessary. All subsequent escapes (including passing to other functions) use the Array known to be allocated on the heap, avoiding further checking or copying within the function.

The same goes for Dictionary, and really any arbitrary value-type with COW storage. The memory that those types allocate is part of the value, so it would be cool if we could treat it like that.

This is not true. FSAs have nothing to do with automatic storage, their static size only makes them eligible to live on the stack, as tuples are now. The defining quality of FSAs is that they are static and contiguous.
_______________________________________________
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 <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
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 <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
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 <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

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

Karl · August 6, 2017, 3:15pm

Right, and the question I’ve been asking (indirectly) is: why is this only useful for arrays? Doesn’t it really apply to any value-type which allocates storage which it manages with COW semantics (e.g. Dictionary, Set, Data, your own custom types…)? Really, we want to inform the compiler that the dynamically-allocated memory is part of the value - and if it sees that the storage is only allocated once, it should be allowed to allocate that storage inline with the value, on the stack.

As I understand it, the only problem with this is when a function takes such a value as a parameter and assigns it to some escaping reference (an ivar, global, or capturing it inside an escaping closure).

So why can’t such assignments simply check if the value has inline storage and copy it to the heap if necessary? The compiler should be able to optimise the function so the check (which is really cheap anyway) only needs to happen once per function. Because the entire type has value semantics, we can substitute the original value with the copy for the rest of the function (preventing further copies down the line).

// Module one

import ModuleTwo

func doSomething() {

let values = (0..<5).map { _ in random() } // allocated inline, since the size can never change
ModuleTwo.setGlobalItems(values) // passes a stack-allocated array to the (opaque) function
}

// Module two

var GlobalItems = [Int]()
var MoreGlobalItems = [Int]()

func setGlobalItems(_ newItems: [Int]) {

GlobalItems = newItems // assignment to escaping reference: checks for inline storage, copies to heap if needed

// all references to ‘newItems’ from this point refer to the copy known to be on the heap

MoreGlobalItems = newItems // we already have a known out-of-line copy of the value; no checks or copying needed
}

// To make it more explicit...

func setGlobalItems_explicit(_ newItems: [Int]) {

    let newItems_heap = newItems.backing.isAllocatedInline ? newItems(withBacking: newItems.backing.clone()) : newItems
    GlobalItems = newItems_heap
    MoreGlobalItems = newItems_heap
}

This would require some special language support for values that allocate memory which is managed as COW.

- Karl

···

On 4. Aug 2017, at 20:15, John McCall via swift-evolution <swift-evolution@swift.org> wrote:

On Aug 4, 2017, at 1:19 PM, Félix Cloutier via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

That's not a concern with the `let` case that Robert brought up, since you can't mutate a `let` array at all.

The big thing is that unconstrained escape analysis is uncomputable. Since Swift array storage is COW, any function that receives the array as a parameter is allowed to take a reference on its storage. If the storage lives on the stack and that reference outlives the stack frame, you've got a problem. It's the same problem that motivated @escaping for closures.

You could allow storage to be on the stack by forcing user to make a pessimistic copy, which is possibly not an improvement.

Right. I think maybe the name people keeping using for this feature is misleading; a better name would be "inline arrays" or "directly-stored arrays". Having a fixed size is a necessary condition for storing the array elements directly, but the people asking for this feature are really asking for the different representation, not just the ability to statically constrain the size of an array.

That representation difference comes with a lot of weaknesses and trade-offs, but it's also useful sometimes.

John.

fclout · August 4, 2017, 7:16pm

That's not a concern with the `let` case that Robert brought up, since you can't mutate a `let` array at all.

The big thing is that unconstrained escape analysis is uncomputable. Since Swift array storage is COW, any function that receives the array as a parameter is allowed to take a reference on its storage. If the storage lives on the stack and that reference outlives the stack frame, you've got a problem. It's the same problem that motivated @escaping for closures.

You could allow storage to be on the stack by forcing user to make a pessimistic copy, which is possibly not an improvement.

Good point. If this is only problematic when multiple threads are accessing an array, then it could still be worthwhile if all accesses are (provably) on the thread that created the array.

To be clear, it's a problem independently of multi-threading. `func foo() -> [Int] { return [1, 2, 3] }` is the most basic representation of it: you can't store the array in the stack frame if you return it. (To be fair, that one would be caught by escape analysis of any quality.) `func foo() { bar([1, 2, 3, 4]) }` is another example: if you don't know what `bar` does with the array, you can't store it on the stack because it might pass it to an object that lives on the heap and outlives `foo`, for instance. @escaping solves that problem for closures by specifically annotating parameters when the assigned closure could still be referenced after the called function returns.

And pessimistic copying might still be worth it for arrays below a certain size — for instance, copying an Array<Int> of length 1 (and recall that the array in question is a constant so its size is known at compile time) would definitely be worth not having that array in heap memory.

You only need pessimistic copies when that copy escapes, and since it escapes, it needs to live on the heap by definition. Right now an array of size 1 passed to 4 objects on the heap has one single backing representation. With pessimistic copies, you'd get 4 times that buffer of size 1, which is definitely not an improvement.

Going back to the literal notion of FSAs — fixed size arrays not necessarily on the stack — I think that simply copying Array’s implementation sans RangeReplaceableCollection conformance is not a bad way to go. Any optimizations used for `let` Arrays could probably be applied to this type of FSA.

We're actually splitting this in multiple directions. John talks of variable-sized arrays necessarily on the stack. :)

I see two useful characteristics to fixed-size arrays, which, uncoincidentally, are what it takes to use them for C interop:

Their storage is inlined into their container (whether it be the stack or an object)
Their length is part of their type (and not directly included with the data itself)

This is also enough to implement fixed-size arrays not necessarily on the stack, mind you.

Félix

···

Le 4 août 2017 à 11:39, Robert Bennett <rltbennett@icloud.com> a écrit :

John_McCall · August 6, 2017, 4:27pm

That's not a concern with the `let` case that Robert brought up, since you can't mutate a `let` array at all.

The big thing is that unconstrained escape analysis is uncomputable. Since Swift array storage is COW, any function that receives the array as a parameter is allowed to take a reference on its storage. If the storage lives on the stack and that reference outlives the stack frame, you've got a problem. It's the same problem that motivated @escaping for closures.

You could allow storage to be on the stack by forcing user to make a pessimistic copy, which is possibly not an improvement.

Right. I think maybe the name people keeping using for this feature is misleading; a better name would be "inline arrays" or "directly-stored arrays". Having a fixed size is a necessary condition for storing the array elements directly, but the people asking for this feature are really asking for the different representation, not just the ability to statically constrain the size of an array.

That representation difference comes with a lot of weaknesses and trade-offs, but it's also useful sometimes.

John.

Right, and the question I’ve been asking (indirectly) is: why is this only useful for arrays? Doesn’t it really apply to any value-type which allocates storage which it manages with COW semantics (e.g. Dictionary, Set, Data, your own custom types…)? Really, we want to inform the compiler that the dynamically-allocated memory is part of the value - and if it sees that the storage is only allocated once, it should be allowed to allocate that storage inline with the value, on the stack.

There are absolutely things we could do as part of the Array implementation to dynamically avoid heap allocations for temporary arrays. However, it would be very difficult to take advantage of that for arrays stored in temporary structs or enums; worse, even if we could, it still wouldn't have the optimal representation that people want for mathematical types like vectors and matrices.

John.

···

On Aug 6, 2017, at 11:15 AM, Karl Wagner <razielim@gmail.com> wrote:

On 4. Aug 2017, at 20:15, John McCall via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Aug 4, 2017, at 1:19 PM, Félix Cloutier via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

As I understand it, the only problem with this is when a function takes such a value as a parameter and assigns it to some escaping reference (an ivar, global, or capturing it inside an escaping closure).

So why can’t such assignments simply check if the value has inline storage and copy it to the heap if necessary? The compiler should be able to optimise the function so the check (which is really cheap anyway) only needs to happen once per function. Because the entire type has value semantics, we can substitute the original value with the copy for the rest of the function (preventing further copies down the line).

// Module one

import ModuleTwo

func doSomething() {

    let values = (0..<5).map { _ in random() } // allocated inline, since the size can never change
    ModuleTwo.setGlobalItems(values) // passes a stack-allocated array to the (opaque) function
}

// Module two

var GlobalItems = [Int]()
var MoreGlobalItems = [Int]()

func setGlobalItems(_ newItems: [Int]) {

    GlobalItems = newItems // assignment to escaping reference: checks for inline storage, copies to heap if needed

    // all references to ‘newItems’ from this point refer to the copy known to be on the heap

    MoreGlobalItems = newItems // we already have a known out-of-line copy of the value; no checks or copying needed
}

// To make it more explicit...

func setGlobalItems_explicit(_ newItems: [Int]) {

    let newItems_heap = newItems.backing.isAllocatedInline ? newItems(withBacking: newItems.backing.clone()) : newItems
    GlobalItems = newItems_heap
    MoreGlobalItems = newItems_heap
}

This would require some special language support for values that allocate memory which is managed as COW.

- Karl

fclout · August 6, 2017, 9:12pm

That's not a concern with the `let` case that Robert brought up, since you can't mutate a `let` array at all.

The big thing is that unconstrained escape analysis is uncomputable. Since Swift array storage is COW, any function that receives the array as a parameter is allowed to take a reference on its storage. If the storage lives on the stack and that reference outlives the stack frame, you've got a problem. It's the same problem that motivated @escaping for closures.

You could allow storage to be on the stack by forcing user to make a pessimistic copy, which is possibly not an improvement.

Right. I think maybe the name people keeping using for this feature is misleading; a better name would be "inline arrays" or "directly-stored arrays". Having a fixed size is a necessary condition for storing the array elements directly, but the people asking for this feature are really asking for the different representation, not just the ability to statically constrain the size of an array.

That representation difference comes with a lot of weaknesses and trade-offs, but it's also useful sometimes.

John.

Right, and the question I’ve been asking (indirectly) is: why is this only useful for arrays?

One special thing about fixed-size arrays is that they address the sore spot of C interop.

Doesn’t it really apply to any value-type which allocates storage which it manages with COW semantics (e.g. Dictionary, Set, Data, your own custom types…)? Really, we want to inform the compiler that the dynamically-allocated memory is part of the value - and if it sees that the storage is only allocated once, it should be allowed to allocate that storage inline with the value, on the stack.

Assuming that fixed-size arrays are a different type (like FixedSizeArray<T, N> vs Array<T>), the feature work that supports them would likely be sufficient to support fixed-size whatever collections, too. However (and I'm talking a bit through my hat here, that's not my area of expertise), I think that there could be some drawbacks to implementing some other collections in a fixed amount of memory. For instance, you have to decide on a fixed number of buckets for sets and dictionaries, regardless of what ends up in the collection. Dictionaries and sets also tend to use more memory than arrays, which could cause storage size to balloon up to degrees that are not immediately obvious.

As I understand it, the only problem with this is when a function takes such a value as a parameter and assigns it to some escaping reference (an ivar, global, or capturing it inside an escaping closure).

So why can’t such assignments simply check if the value has inline storage and copy it to the heap if necessary? The compiler should be able to optimise the function so the check (which is really cheap anyway) only needs to happen once per function. Because the entire type has value semantics, we can substitute the original value with the copy for the rest of the function (preventing further copies down the line).

The rest of the function might not be enough, especially if you use the same array for multiple calls. See:

var globalArray = [[Int]]
func append(array: [Int])
  globalArray.append(array)
}

func foo() {
  let bar = [1,2,3]
  append(array: bar)
  append(array: bar)
  append(array: bar)
}

The function that escapes the array is `append(array:)`, so you'd get one copy per call to `append(array:)`, unless functions start annotating the escaping behavior of each parameter. That could work in many cases, but the compiler would still have to be pessimistic in common instances, like when calls to virtual functions are involved, including closures and calls to methods of objects represented as protocol instances. (Also, the amount of work required is likely to be significant.)

Félix

···

Le 6 août 2017 à 08:15, Karl Wagner <razielim@gmail.com> a écrit :

On 4. Aug 2017, at 20:15, John McCall via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Aug 4, 2017, at 1:19 PM, Félix Cloutier via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Karl · August 6, 2017, 3:23pm

Should, of course, be:

let newItems_heap = newItems.backing.isAllocatedInline ? Array(withBacking: newItems.backing.clone()) : newItems

···

On 6. Aug 2017, at 17:15, Karl Wagner via swift-evolution <swift-evolution@swift.org> wrote:

let newItems_heap = newItems.backing.isAllocatedInline ? newItems(withBacking: newItems.backing.clone()) : newItems

carlhung · September 9, 2024, 4:57pm

Can we consider it again?

John_McCall · September 9, 2024, 9:58pm

Hi, @carlhung. If you have anything new to add to this discussion, please make a new thread and link the old one.