[swift-evolution] Proposal for Passing Arrays to Variadic Functions

[Kevin Ballard]

On Sun, Dec 13, 2015, at 07:42 PM, Chris Lattner wrote:
> On Dec 13, 2015, at 3:53 PM, Kevin Ballard <kevin at sb.org> wrote:
> >> This hasn’t been done just because it has never risen to the highest priority, not because we’re against it.  In addition to Joe Groff’s downstream comment, one change we need to discuss: requiring the formation of a formal Array is somewhat unfortunate from a performance perspective.  It would make more sense to pass varargs by allocating the array as a fixed size buffer in the callers stack, and passing a pointer+length down to the callee.  The callee could then wrap that up and vend it with a formal type of Array or perhaps just SequenceType.  In the case where the sequence doesn’t escape, this would allow the allocation/deallocation + copy to the heap to be eliminated.
> > 
> > It would actually be pretty neat if we could do this not as a special case of variadic arguments, but as a general case of passing an array to any function. If the array never escapes the function call and it only reads from it, then having the array point to the stack frame of the caller would be great. Even mutation that doesn't increase the array size could be done in-place on the stack. Any action that might cause the array to escape the function (or any mutation that increases its size) could then move it to the heap. Mutation doesn't even need special handling; since the capacity is equal to the size, it'll move to the heap on any size increase automatically (and size decreases is fine, as the array will manage destruction of the elements). All the compiler really has to do is insert a call that forces a move-to-heap prior to any action that may cause the array to escape the function (e.g. assigning to a property, or capturing in an escaping closure).
> > 
> > If that function call is sufficiently cheap (and it should basically just be testing a boolean flag), then hopefully it's cheap enough to use everywhere for arrays passed as parameters to functions. If it turns out to actually be an issue then maybe we could use an attribute to annotate array parameters that allow for stack allocation, but that would mean it's used pretty rarely as people will usually not bother (except when it's automatically added for varargs).
> 
> Yes, there is some form of this that could be possible to do.  The trick with varargs though is that the caller always (at least without the “forwarding” case) knows the number of arguments that will be passed.  This means that the buffer allocated on the stack in the caller is a fixed and obviously known size, which is usually very small.  
> 
> A similar optimization could be done when passing down an array literal, but the calling convention would have to support passing down an array value obtained in other ways (e.g. passed down to the caller or loaded from memory).  In that case, it is hard to beat the performance of a single retain: no copy of the elements are implied.  Doing the optimization for general unknown number of elements also isn’t profitable in general because the stack is a very finite resource, so you’d have to handle the “large” case somehow.

Oh sure, when I said doing it in the general case, I just meant for arrays created from array literals (or possibly even arrays constructed using .append(), if the optimizer really wants to go ahead and figure out how many elements the resulting array has). And I was thinking that the calling convention is just pass an array, and instead Array will have the flag internally in its native storage that says "my buffer is on the stack" (as well as having a special method to construct an array from a stack buffer that the compiler will use for array literals / varargs). The biggest complication is having the compiler insert calls to array.moveToHeapIfCurrentlyOnStack() whenever an array parameter escapes the function (arrays returned from functions can't be on the stack, and arrays created in the function can skip the stack if it's known to escape), and the question there is whether this call will have meaningful performance implications.

-Kevin Ballard