Sketching out more efficient variadics

[This is not intended to even be a pitch yet; it's exploring a problem and the design space even before that. There are more important things to happen in Swift 5.3 anyway and I won't be pushing for this to happen in that timeframe.]

TLDR:

  1. Variadics and array literals both default to allocating Arrays, which usually means a heap allocation.
  2. The compiler can already stack-promote Arrays if it can prove that there are no outstanding references to the Array instance.
  3. But it's hard to do that through a non-inlinable function call.
  4. We can sidestep that problem today by using UnsafeBufferPointer.
  5. When move-only types come along, we're close to being able to make a safe BorrowedBuffer type. (Which we'll very likely want anyway, for other purposes.)
  6. If we then come up with a syntax to allow types other than Array to be used for variadic parameters, we get safe stack-allocated variadics out of it. (I don't much care what the syntax is at the moment.)

Background

Variadics are a convenient syntax for passing several arguments to a function:

// Without variadics: clearly too hideous to ship
func max(_ values: [Int]) -> Int { … }
let requiredHeightOfShowerhead = max([myHeight, yourHeight, theirHeight, plumbingHeight])

// With variadics: ahh, much better!
func max(_ values: Int...) -> Int { … }
let requiredHeightOfShowerhead = max(myHeight, yourHeight, theirHeight, plumbingHeight)

As you can see, they're pretty much syntactic sugar for an array. Other threads have talked about ways to make these two calling syntaxes interoperate—that is, if you already have an Array, you should be able to pass it to a variadic function, which is important for forwarding arguments from one variadic function to another.

That's not what this is about. In fact, I've somewhat done a bait-and-switch here. For most of the rest of this post I'm going to talk about array literals.

Passing Arrays requires a heap allocation

In both versions of max, we have the nice property that we can treat the values parameter as a plain old Array. We can call methods on it, pass it to other functions, store it in a global…

*record scratch* …wait, store it in a global? That means the storage for the Array has to outlive the call! And that means calling a variadic function or passing an array literal is going to result in a heap allocation.

(Aside: In a language like C++ with copy constructors, there'd be a chance for the array to initially be allocated on the stack and then copy itself to the heap when stored somewhere else, much like what "copy-on-write" logic does when you mutate an array with shared storage. But in Swift, copying one value somewhere doesn't allow calling custom user code, except for the possible deallocation of the value that was there before.)

So calling variadic functions, as well as passing one-off arrays to functions, has a bit of a cost over just passing individual arguments (assuming the function can't be inlined). That's probably the right trade-off for approachability, but as a (small) part of "Making Swift A Systems Language", I feel like there should be support for passing a variable number of values to a function without a heap allocation. After all, the stack is right there.

Making it work in today's Swift

Let's add another overload of max. (And please forgive the simple example; of course the max that's on Sequence would provide the real implementation of this.)

func max(_ values: UnsafeBufferPointer<Int>) -> Int

let requiredHeightOfShowerhead =
  [myHeight, yourHeight, theirHeight, plumbingHeight].withUnsafeBufferPointer { max($0) }

An unsafe buffer pointer offers no guarantees about lifetime, so as far as the compiler is concerned, the storage for the temporary array is not referenced after the call to withUnsafeBufferPointer. That's already enough for the compiler to promote the array to the stack when optimizations are turned on.

Since I said this is meant for systems programming, I suppose this is technically good enough to package up and use, even with the sharp edges UnsafeBufferPointer has.

@_transparent
func withUnsafeBuffer<Element, Result>(
  _ elements: Element...,
  do body: (UnsafeBufferPointer<Element>) throws -> Result
) rethrows -> Result {
  try elements.withUnsafeBufferPointer(body)
}

let requiredHeightOfShowerhead =
  withUnsafeBuffer(myHeight, yourHeight, theirHeight, plumbingHeight) { max($0) }

Making it safe(r)

The primary problem I see with passing an UnsafeBufferPointer is that it's, well, not safe. I'm not talking about all the operations you shouldn't do here, like trying to deallocate the buffer when you don't own it. No, the concern I have is about someone saving the buffer pointer past the end of the call, when it's no longer valid—something you can do with a simple assignment in Swift. Can we disallow that somehow? Not today, but we can in the future with move-only types.

moveonly struct BorrowedBuffer<Element> {
  var rawBuffer: UnsafeBufferPointer<Element>

  // forwarding APIs like subscript
}

func max(_ values: __shared BorrowedBuffer<Int>) -> Int

Note that the parameter to max is "shared" rather than "owned". If it were "owned", it would still be possible (if unlikely) for the implementer of max to save the BorrowedBuffer off somewhere. Fortunately, I think the plan is for "shared" to be the default for function arguments even within move-only types, which means the most common path will still be the safe one.

(I'm not going to go over these ownership terms here; you can read the Ownership Manifesto, or you can think of __shared as & in Rust and const & in C++, and __owned as an unannotated value in both languages.)

What about the call side, though? How do we make a borrowed buffer? If we want to be safe all around, we can't just add an initializer that takes an UnsafeBufferPointer and call it a day. We want to make sure that a BorrowedBuffer in "safe" code can't accidentally reference memory past its lifetime. After all, it doesn't have "unsafe" in the name.

Fortunately, one of the goals of move-only types is to allow resource management; we should be able to do something like this:

moveonly struct BorrowedBuffer<Element> {
  private var owner: Unmanaged<AnyObject>?
  var rawBuffer: UnsafeBufferPointer<Element>

  deinit {
    owner?.release()
  }

  // forwarding APIs like subscript
}

extension BorrowedBuffer: Collection { … }

I've written the owner reference as Unmanaged and done some manual memory management to make it clear that the reference does not escape; unfortunately the compiler is (correctly) conservative and still refuses to promote the owning array to the stack. (It's not wrong, either; even with a private field someone could still get the value out by reflection.) So we'd have to add additional logic to the compiler to understand that this field's value never escapes, which this Unmanaged logic is standing in for.

@_transparent
deinit {
  precondition(
    isKnownUniquelyReferenced(&owner),
    "you mustn't access the 'owner' field of a BorrowedBuffer")
}

(I don't think a bare precondition would work today, but since there is no memory-unsafety introduced by stack-promoting if you abort whenever the stack isn't the only reference, this ought to be optimizable.)

But without this additional "owner" field, we've only made stack buffers "safer" but not "safe", at least without not making the caller side clunky again. If we could solve this problem, though…

Making it pretty

…I'd suggest lifting an idea from an old proposal from @Haravikk3 (no longer around on the site, I guess): [Proposal] Variadics as Attribute (with later [Discussion] Variadics as an Attribute)

func max(_ values: @variadic BorrowedBuffer<Int>) -> Int
// Hooray, we're back to the original syntax!
let requiredHeightOfShowerhead = max(myHeight, yourHeight, theirHeight, plumbingHeight)

Specifically, a "desugared" syntax for variadics that allows choosing the type used for the variadic argument, as long as it is ExpressibleByArrayLiteral. If we can safely make BorrowedBuffer ExpressibleByArrayLiteral, that gives us all the tools we need.

Oh, and I just snuck that in there, but it ought to work for regular old array literals too. BorrowedBuffer ensures that the backing storage is kept alive as long as the BorrowedBuffer is alive, and that as long as the BorrowedBuffer instance isn't passed "owned", the backing storage can be stack-promoted. That's true whether the array literal's passed as an argument or stored in a variable first—it can even be used multiple times.

I don't want to discuss the syntax for this, just whether people think it's reasonable to allow other types to be used for variadic parameters besides Array. (I only briefly skimmed the old discussions so I should probably read those again.)

Conclusion

Thoughts? In particular, any better ideas on how to make BorrowedBuffer safe on the creation side?

Appendix: Because This Post Isn't Long Enough

There's one other possible way to handle the "lifetime extension" needed for borrowed buffer: generalized coroutines. That would look something like this:

moveonly struct BorrowedBuffer<Element> {
  var rawBuffer: UnsafeBufferPointer<Element>

  // as usual, please ignore syntax
  static func borrow(
    from: AnyObject?,
    rawBuffer: UnsafeBufferPointer<Element>
  ) -> __shared BorrowedBuffer {
    // Normally we'd use withExtendedLifetime here,
    // but I'm not sure how yields work from inside a closure.
    defer { _fixLifetime(owner) }
    self.rawBuffer = rawBuffer
    yield &self
  }
}

What this means is that anyone who calls borrow(from:rawBuffer:) gets back a BorrowedBuffer, but also a sort of "cleanup" call that needs to happen when they're done using it. It's the same basic behavior as passing a callback to withUnsafeBufferPointer, but without the nesting. That alone isn't enough to do this, though; we'd also need to change ExpressibleByArrayLiteral to use it:

__shared init(arrayLiteral elements: Element...)

And, you know, maintain backwards compatibility somehow. I don't know if generalized coroutines are ever going to happen, though—even if they're implementable, the core team or community might decide they make the caller side's behavior too subtle. So I don't want to pin the idea of stack-allocated variadic arguments to getting generalized coroutines.

8 Likes

We could address the "how do we stack promote more arrays" problem more generally, without specifically targeting variadics, by having a "copy on escape" model for all value type buffers, where a the compiler has to assume that any array buffers it receives might be on the stack and copy it if it wants it to outlive the call, sort of like how blocks and _Block_copy work in ObjC. Though we can't do that for existing binaries, it could maybe be a forward-compatible change where binaries compiled with a new compiler are known to copy-on-escape, but calling into older binaries requires pre-copying any potentially stack-allocated arguments before passing them along.

8 Likes

I am a huge fan of this idea (and even started a thread on it once Enhanced Variadic Parameters), thanks for reviving it!

It would be really cool if we had a consistent and straightforward way to reason about when stack promotion of arrays would happen. Are there similar changes we could make to facilitate similar guarantees around arrays that are returned from functions (at least for inlinable functions)?

1 Like

This is fascinating (at least in my dim understanding), and I’d be curious to see it fleshed out as its own proposal.


Could Jordan’s solution at hand be exposed to callees in Swift’s current universe as a non-escaping closure argument that yields each argument in turn?

func max(_ values: Int...) -> Int { … }
// …becomes:
func max(_ values: /*non-escaping*/ () -> Int?) -> Int { … }

Probably not very ergonomic, but it does at least force a copy / materialization elsewhere if the value escapes.

It's a cool idea, but right now we don't have any notion of "older binaries" and "newer binaries" for library evolution—there's no "oldest version of Swift this library was built with" encoded anywhere.

I think we're going to want "guaranteed buffer" as a type anyway, so we can move forward with both ideas when we get closer to move-only types. (A guaranteed buffer that isn't meant to be the only owner of its storage can have a nil owner; anything more complicated than that is basically just Slice.)

Hm, that's a very different API that probably negates the efficiency gains of keeping all the values on the stack. :-/ I like the explicit connection of "non-escaping closure" to "non-escaping value", though.

That's fine, as long as we add the "oldest version this was built with" information at the same time we add functionality that relies on it. We can assume the worst about pre-history.

In an ideal world IMO, we would try to minimize the degree to which you need to use an entirely different universe of types in "systems Swift", and minimize the amount of alternative attributes and language features you need to deploy our existing language features in that context. I can definitely see the utility of making variadics syntax more powerful by letting you use it with different kinds of backing types, but I'd hate for it to be a requirement to use the feature and get decent performance.

2 Likes

Being able to associate a Swift version range with an API would be quite valuable for a lot of reasons. We could even take advantage of this for existing APIs by e.g. seeing that a function was introduced under Swift 5 compatibility but is part of a module interface that guarantees up to Swift K compatibility, and thus knowing that it offers both an old-ABI and a new-ABI entrypoint. (Whether it's a worthwhile trade-off to introduce a second polymorphic entry for variadic protocol requirements and class methods is a separate question.)

It's not just us who have to add it; it's a backwards-deployment story. Anyone who is making a Swift library has to say "the oldest version of this library in existence was built with Swift 6.0" explicitly on their command line. I don't know if that's something that pulls its weight. (We've seen this problem before in the discussion of library versions and types that become frozen after the first release; any client libraries still have to assume the types might be non-frozen unless we add a per-dependency "minimum library version" setting.)

Well, calling across an ABI boundary is also generally not something you want to do in hot code anyway, so maybe having a better baseline convention for variadics could be valuable even if we can only use it for local or nonresilient calls.

I'm thinking of "code that can't do heap allocation" more than "code that needs to be as fast as possible" here. Local calls ideally could always get stack-promoted because we'd be able to determine whether the array escapes. Non-resilient code would still benefit, though, that's true!

I guess this also suggest another possibility for non-resilient code: record in an inferred SIL attribute whether parameters escape, and then callers get to assume that when deciding whether to stack promote. That probably falls down if the API takes an arbitrary Collection rather than an Array, but that might not ever have been worth optimizing to this extent.

Well, I’d imagined that it would be a “compiler magic” closure that compiles down directly to the appropriate pointer arithmetic, not an actual jump or anything. And yes, as you observe, the (not particularly carefully formed) thought was just to find a way to let the compiler enforce the values staying on the stack without have to add anything fussy to the language surface.

I do think, though, that it would be a somewhat awkward API to use.


Semi-related thought: I’ve longed wished for autoclosure variadics, for the one mundane reason that it would make this nicer:

log(.debug, "Message includes", expensiveFormatting(someValue),
    "that we don't want to do unless debug logging is enabled")

Granted custom string interpolation may fill this need, but it's a wish I’ve long had.

Terms of Service

Privacy Policy

Cookie Policy