FIFO not respected in `AsyncChannel`

[alessionossa]

While testing AsyncChannel behavior to determine if it was a good match for my use case, I noticed that when AsyncChannel.send(_:) is called from different Tasks, the order of the output is inconsistent and unpredictable, even if the schedule happens on a specific actor and so does the reading.

The following script sends 500 elements, one after the other, each in its own Task. This recreates a common scenario of the real word where new elements generates from user inputs in a synchronous context and the call to send(_:) has to be wrapped in a Task to bridge sync and async worlds. This behavior is also described at [Pitch] Async buffered channel - Related Projects / Swift Async Algorithms - Swift Forums.

import Foundation
import AsyncAlgorithms

@globalActor actor ConsumerActor: GlobalActor {
    static let shared = ConsumerActor()
}

func testAsyncChannel() async throws {
    let channel = AsyncChannel<Int>()

    let task1 = Task { @ConsumerActor in        
        var count = 0
        
        for await value in channel {
            count += 1
            if value != count {
                print(value, "on ConsumerActor does not match", count)
            }
            // print("AsyncChannel value: ", value)
        }
    }
    
    for element in 1...500 {
        Task { @MainActor in
            // print("Sending \(element)")
            await channel.send(element)
        }
        // try await Task.sleep(for: .nanoseconds(30000)) // For values above 30000 ns, the order is respected.
    }
}

try await testAsyncChannel()

try await Task.sleep(for: .seconds(2))

The output this script is:

3 on ConsumerActor does not match 1
4 on ConsumerActor does not match 2
5 on ConsumerActor does not match 3
6 on ConsumerActor does not match 4
7 on ConsumerActor does not match 5
1 on ConsumerActor does not match 6
8 on ConsumerActor does not match 7
12 on ConsumerActor does not match 8
13 on ConsumerActor does not match 9
[...]

Showing that the order the elements are emitted by the AsyncChannel does not correspond to the ordinal numbers.

The expectation is that the elements emitted by the AsyncChannel are in the same order AsyncChannel.send(_:) has been called. This happens when calls to AsyncChannel.send(_:) are at least 30000 ns.

In fact, the following script demonstrates that normally the order of execution of several scheduled Task is respected when they are scheduled to run on an actor - while the order cannot be determined when an actor is not specified.

import Foundation

actor Counter {
    var count = 0
    func increment() -> Int {
        count += 1
        return count
    }
}

func experiment() async {
    let s = Counter()
    
    for i in 1 ... 1_000_000 {
        Task { @MainActor [i] in
            let result = await s.increment()
            if i != result {
                print(i, "on MainActor does not match", result)
            }
        }
    }
    
    let t = Counter()
    for i in 1 ... 1_000 {
        Task { [i] in
            let result = await t.increment()
            if i != result {
                print(i, "does not match", result)
            }
        }
    }
    

    try? await Task.sleep(nanoseconds: 1 * NSEC_PER_SEC)
    let finalCountS = await s.count
    print("Completed all tasks S, count:", finalCountS)
    let finalCountT = await t.count
    print("Completed all task T, count:", finalCountT)
    
}

await experiment()

The output of this script is:

14 does not match 13
40 does not match 39
43 does not match 42
44 does not match 43
[...]
979 does not match 980
995 does not match 994
994 does not match 995
Completed all tasks S, count: 1000000
Completed all task T, count: 1000

Demonstrating that all the 1000000 Task scheduled on the Main Actor runs in the order they are scheduled.

[ole]

Regarding your experiment script to verify the behavior without any AsyncChannel specifics:

Demonstrating that all the 1000000 Task scheduled on the Main Actor runs in the order they are scheduled.

Interesting find. However, I don't think (not sure though!) the language guarantees this. In this code:

    for i in 1 ... 1_000_000 {
        Task { @MainActor [i] in
            let result = await s.increment()
            if i != result {
                print(i, "on MainActor does not match", result)
            }
        }
    }

• Task semantics guarantee that the @MainActor closures start running on the main actor in the order they were scheduled.
• But it's not guaranteed (I think!) that calling into another actor with await s.increment() will schedule the s.increment() calls on the actor s in order, even if the current implementation behaves this way.

[alessionossa]

• Task semantics guarantee that the @MainActor closures start running on the main actor in the order they were scheduled.

Yes, as you mentioned that's the case since Swift 6.0 as described in SE-0431 - @isolated(any) Function Types > Detailed design > Adoption in task-creation routines. This was discussed Task: Is order of task execution deterministic? - Swift Forums.

• But it's not guaranteed (I think!) that calling into another actor with await s.increment() will schedule the s.increment() calls on the actor s in order, even if the current implementation behaves this way.

Regarding this I couldn't find any reliable source confirming or denying the hypothesis.

Given the previous point, however, I believe that AsyncChannel.send(_:) have the possibility of enqueue the items in the order the items are sent by maintaining the same isolation the function is called on, for example with the interface public func send(_ element: sending Element, isolation: isolated (any Actor)? = #isolation) async. With the current implementation that relies on the Cooperative Global Executor the calls to AsyncChannel.send(_:) and ChannelStorage.send(element:isolation:) are already out of order even if started from the same actor. On top of that, the use of os_unfair_lock on Darwin platforms to manage the suspension seems to lead to even more disorder in the output of the elements.

Considering that AsyncChannel is an AsyncSequence, I would expect its order to be deterministic.

This means also that SE-0406 - Backpressure support for AsyncStream > Comparison to other root asynchronous sequences > swift-async-algorithm: AsyncChannel is probably stating

The AsyncChannel is a multi-consumer/multi-producer root asynchronous sequence which can be used to communicate between two tasks. It only offers asynchronous production APIs and has no internal buffer. This means that any producer will be suspended until its value has been consumed. AsyncChannel can handle multiple consumers and resumes them in FIFO order.

[ole]

Given the previous point, however, I believe that AsyncChannel.send(_:) have the possibility of enqueue the items in the order the items are sent

I agree that this would be a good property to have. (I think. I haven't thought it through if there are any downsides. And I've never really used AsyncChannel except for small experiments.)