Swift Async Algorithms: Design Guidelines

Yes, that's what I was trying to say. If you call makeAsyncIterator() on an asynchronous sequence in one async context, then 'take' the asynchronous sequence into another asynchronous context (via a Task for example), and call makeAsyncIterator() again in the new context, you'll potentially have two concurrent iterators regardless of whether the sequence was taken.

Yes, I'm arguing exactly the same thing, see 2.2.5.

What I'm saying is that an asynchronous sequence that is iterated multiple times probably wouldn't fatalError() in an ideal world.

I am implying here that taking means that the sequence is not usable anymore, I.e. you can only call makeAsyncIterator once. The sequence would also need to be a move-only type

Got it, that would certainly be an interesting route if it can indeed be expressed like that.

Yeah I disagree. You should hope that it traps. It is definitely the ideal outcome.

Take this example, from the Sequence documentation:

for element in sequence {
    if ... some condition { break }
}

for element in sequence {
    // No defined behavior
}

That should scare the living daylights out of anybody who writes generic algorithms using Sequence.

Too many developers have this idea that trapping is the worst thing that can happen. Unpredictable behaviour should never be the preferable outcome.

2 Likes

I think you're fighting a different argument. I don't have an issue with trapping, generally. And I'm not trying to come up with blanket rules for the Swift developers who are creating their own asynchronous sequences. I'm talking about the SAA package specifically. If developers or library designers wish to design their own trapping asynchronous algorithms – that's fine.

I'm talking here about the SAA library specifically and creating a set of tools that allow programmers to snap together components and sequences in a way that feels at least as intuitive as other reactive programming libraries.

I don't have any issue with developers snapping together components.

I do have an issue with the idea that they won't be given prompt notice when they compose those components incorrectly, and the suggestion that unpredictable behaviour is a more ideal outcome in that situation, or that being lax about such misuse leads to a more intuitive library.

That applies to this package, as well as it applies to any other library.

I think in general trapping is only really needed in root AsyncSequences since they decide what kind of castiness they have. Most other algorithms are just inheriting the castiness of their upstreams (unless the algo is about changing that property e.g. multicast())

However, I agree with @Karl here. Trapping is way better than undefined behavior or silent failures. Furthermore, Swift is quite big on this with bound checking etc.

The aim here is to foster predictability, so if anything here were to run counter to that I'd consider it a failure. I don't think I'd be alone in hoping that a Sequence or AsyncSequence that trapped on multiple iteration at least documented that behavior. Do you think that would be a fair assumption for a programmer to make?

I'm certainly not arguing for undefined behaviour. I'm not sure where that was suggested. But I do think asynchronous algorithms are falling short of the Rx ergonomics in this regard. I also think relating it to a bounds check is clearly a false comparison. A sequence has isEmpty or count to assess whether it can be accessed safely at a particular index. Asynchronous sequences have no equivalent methods/properties to assess whether or not they are safe to iterate.

Well, if the documentation didn't mention it, I wouldn't assume that it was safe to iterate multiple times. It might be worth reiterating that in the type's documentation, but everybody has their own idea of what makes "good" documentation - I tend to like specifying these kinds of things, but others find it verbose.

Actually, Sequence doesn't have either of those. All it has it makeIterator().

I think the problem you're having is that synchronous Sequence is just kind of broken and doesn't compose, and AsyncSequence inherited most of that brokenness. I did mention those shortcomings during the review:

I think we need a better model for async data streams which isn't based on Sequence. AsyncIterator is fine - it is single-pass, no question - but when you get in to questions like multiple iteration, or what data you will see from those iterations, things get a lot murkier and we don't have a good model for them. Sequence is designed to not answer those questions, which means you must be conservative in your assumptions.

I'd also like to point out another important consideration - leaving gaps where you fail to enforce correct usage can lead users to depend on accidental results stemming from implementation details, which makes maintenance of the library much more difficult.

Unless the library authors are willing to document and guarantee that a particular async sequence will always allow multiple iterators to be created, the safest thing to do is fatalError to prevent it.

1 Like

You're absolutely right, but generally I don't think an API would vend a non-Collection level Sequence if its iteration count could be unknown and its behavior on multiple iterations was undefined. In the async world, we don't yet have that option, unfortunately.

Thanks for sending this through, an interesting read that articulates some of the difficulties I've been having trying to reconcile the behaviour of asynchronous sequences. I would agree that AsyncIteratorProtocol better encapsulates that one-pass behaviour. My own assessment was that a 'root unicast' asynchronous sequence isn't a sequence at all, but a form of asynchronous iterator – so this echoes that idea in some ways.

It would be great to see what this might look like. On the consumption side, I think the model works quite well with for await _ in x { ... }, the transformation algorithms work relatively well with some question marks on priority inversion with multicasting, but the production side of things definitely feels like it could benefit from a more capable model.

I think agreeing a rule here either way would go some ways to helping people get intuition here. So if the best way of doing that is saying whether a root sequence will trap or not in the docs – I think that's all we can do. Non-root sequences will inherit the iterability of their base, so no need for any special callout in the docs here. But for root sequences, it sounds like the behavior will need to be called out one way or the other – which is less than ideal, but sounds like the best route forward absent of a better way of modelling things.

Outside of these guidelines: it's definitely making me lean towards the creation of some Subject-like multicasting root sequences as a way of smoothing out the intuition of the production side of things.

Regarding push vs pull, it may be useful to know that one of the really foundational things in both Combine and AsyncSequence was the realization that you can use buffers to turn push into pull, and use coroutines to turn pull into push. Registering a callback block and blocking a coroutine in next() are fundamentally the same operation. So I kinda reject the idea that it’s actually a pull model.

We spent a hilarious amount of time from 2012-2014 debating this before we figured out the symmetry I described above.

11 Likes

That caught my attention. Would you mind to provide very minimal examples for those cases? I find myself running into bugs when working with back pressure mechanics. For example flatMap works fairly different with AsyncSequence than it does in RxSwift.

I think I’d need to see specifics, but maybe it’s the difference between “like a one-shot callback block” and “like a block that’s registered once and called repeatedly”?

That's an interesting perspective, this is kind of fundamental to rule 2.1.4.

My own opinion is that it's going to be very difficult to reason about a pipeline that has multiple buffers (of the unbounded/latest/earliest variety) placed throughout its length.

The idea behind 2.1.4 is that whilst a pipeline that maintains back pressure from the point of consumption to the point of production can easily be converted into one that does not – through the placement of a buffer – the reverse is not true. Therefore, the algorithms for SAA should support back pressure as a default, and programmers can then compose the behavior they want either way. In other words, algorithm designers need to be mindful of the effect of placing a buffer in their algorithm.

Going back to the push/pull analogy (if it holds), I'm not sure that you're converting from a pull/push by placing a buffer, it's more like adding an additional source of 'pull' locomotion up the pipeline. It's not too dissimilar to plumbing in that regard, if you place a bunch of pumps at different levels you have to be careful not to cause a flood.

I think the natural polarity of the overall system is important, it does inform the design of the algorithms.

While your insights are generally applicable here, it is important to grasp that "placing a buffer" doesn't imply "abandoning backpressure". You can continue to maintain backpressure while using a buffer to invert a push model to a pull model. SwiftNIO exposes just such a type: NIOAsyncSequenceProducer. We needed this to deal with exactly the situation that @David_Smith discussed: NIO's ChannelPipeline has a push model, AsyncSequence has a pull model, so we had to turn the backpressure model around.

The mere presence of a buffer does not inherently make a pipeline more difficult to reason about. The presence of a buffer that is unbounded and doesn't exert backpressure most certainly does. That's not a reason not to do this, but it is a reason to take particular care.

The core distinction about push-vs-pull streaming semantics is that pull semantics are impossible to implement unless you have a source transformation step or something thread-like you can block. Pull is a vastly superior programming model: it's easier to understand, users tend to naturally implement backpressure, and it matches our synchronous intuitions. The only problem is that if you don't have a powerful macro system or pervasive green threading, you cannot build such a system outside of a programming language. This is (part of) why Netty and NIO are both push-based: it is (or in NIO's case was) simply not possible to implement them as pull-based in their respective languages.

I will disagree with @David_Smith though. While I agree entirely that push and pull can be transformed into one another, the experience of working in them is fundamentally different. Inversion of control is hell for programmers, and returning to standard control flow makes understanding code far easier. It also requires pull-based streaming. While you can always transform one into the other, that transformation doesn't make them identical.

4 Likes

That's definitely a fair critique; I should try to be more precise about the distinctions I'm making.

What to do about multiple buffers in a stream is something I spent a while thinking about in the past and never reached any truly satisfying conclusions on. It does seem like you want them to be "aware" of each other in some sense, which makes piecewise composition of streams by unrelated bits of code tricky.

Figuring out where the optimal place for the buffer is can be nontrivial as well. Like if you have a network -> image data -> image stream, with a fast image decoder and not much ram you probably want to buffer compressed image data and decode it on the way out, but if you have more ram and a slower decoder you probably want to buffer decoded images so you can let the decoder get ahead during down time.

This is probably getting a bit off topic for this thread though, sorry. Better suited to the Buffer proposal I think :slight_smile:

I think that's where the distinction between a 'back pressure aware' buffer and a 'non back pressure aware' buffer comes in. In the buffer thread, one variation of these 'back pressure aware' buffers has been referred to as 'throughput' buffers. As @lukasa says, I don't think adding this kind of buffer makes a pipeline any more difficult to reason about.

It's the unbounded/earliest/latest variety you see in AsyncStream. There's nothing wrong with this kind of buffer, it just needs to be considered within context. I've seen people using AsyncStream as a surrogate type eraser for AsyncSequence. That'll cause a surprise one day!

This is precisely why I raised the issue. My argument would be that, while it won't alleviate all difficulties, if we can at least at least consider 2.1.4 when adding an algorithm to SAA, the overall system will be much easier to reason about. Snapping together a bunch of 'back pressure ready' components will be easier than dealing with a two-tier system where some algorithms do support back pressure and some don't. (Of course there's no issue with creating components which explicitly release back pressure, like the above described buffer, I just think their behavior should be intentional.)

In the end, the ability to do this requires understanding the difference between the pull and push models.

I will again note that you really don't need the buffers to be aware of each other. Networking is the canonical example, where every node in the network has buffers, all of which are unaware of each other. The key is that the buffers need to be capable of exerting backpressure on one another, such that they can appropriately rate-limit.

5 Likes

Thank you so much to everyone that contributed their thoughts to this thread. It’s been a really useful exercise. It’s certainly opened my eyes to some things that I hadn’t considered before, and I’m grateful for that.

Gathering the feedback from the comments above, there appears to be a broad consensus, with one notable exception:

  • 2.2.4: If an asynchronous sequence is Sendable, it MUST be safe for its iterators to co-exist across Tasks. This is because it is possible for more than one Task to iterate a Sendable asynchronous sequence at the same time.

The community felt that this rule was at odds with the existing aims of consistency with synchronous Sequence types, for which no specific multi-pass behaviour is defined. Specifically, the documentation for Sequence states: “ [the Sequence] protocol makes no requirement on conforming types regarding whether they will be destructively consumed by iteration.” Therefore, this guideline has been removed in its entirety.

Thanks again, all, for your valuable input.

2 Likes