swift-async-algorithms: `throttle` does not emit the latest element at interval occurrence when latest is `true`

Unlike similar operator in Combine the throttle’s latest parameter is confusing, as it does not emit any latest, but a next element instead.

When latest parameter is set to true

Actual behavior:

The throttle emits the next element from the base sequence, if any, after the interval occurs. Meaning if there’s no new elements emitted after the interval occurrence, the latest element is just skipped, leading to only the first element being emitted.

Expected behavior:

The throttle emits the latest cached element instantly when the interval occurs.

About this issue

  • Original URL
  • State: open
  • Created 3 years ago
  • Comments: 33 (7 by maintainers)

Most upvoted comments

One would indeed expect to receive the last element when using throttle. A very common use case for example is to throttle a sequence of progress values where receiving the last element (i.e. 100%) is crucial.

In this example:

var numbers = Array((0...100).reversed())
let stream = AsyncStream {
    try! await Task.sleep(nanoseconds: 50_000_000)
    return numbers.popLast()
}

Task {
    let sequence = stream
        .throttle(for: .seconds(1))
    for try await num in sequence {
        print(num)
    }
}

The output is:

0 19 38 58 77 96

Which is unexpected as the latest element is 100.

The problem is that in the AsyncThrottleSequence implementation we can wait for the next element longer then interval which can result in the latest element being ‘stuck’. Wouldn’t it make sense to add a timeout when awaiting the base sequence’s next() so that the latest element is always emitted after interval amount of time passed?

public mutating func next() async rethrows -> Reduced? {
    var reduced: Reduced?
    let start = last ?? clock.now
    repeat {
        // Return reduced if we wait longer then interval (and reduced was not returned previously)
        guard let element = try await base.next() else {
            return nil
        }
        let reduction = await reducing(reduced, element)
        let now = clock.now
        if start.duration(to: now) >= interval || last == nil {
            last = now
            return reduction
        } else {
            reduced = reduction
        }
    } while true
}

We have been working on a 1.0.0 for quite some time now and are just going through the final open issues that are blocking the release. The goal for 1.0.0 is not feature parity or providing all possible algorithms but to have a baseline of algorithms that are working and functional. There are many more algorithms that we want to support but the 1.0.0 is important for us to settle the foundation. Furthermore, it is important for the ecosystem since nobody can really depend on this package before the 1.0.0 is out.

Okay, perhaps there is a way to do this. My problem above was trying to solve the problem as a TaskGroup. But using Swift continuations, we have a lot more flexibility. It requires some unstructured child tasks to do it but it seems to work? It’s not exactly simple, though.

Curious to know if anyone has any thoughts about this approach. It’s a drop-in replacement for _AsyncThrottleSequence.Iterator in AsyncThrottleSequence.swift.

    /// The iterator for an `AsyncThrottleSequence` instance.
    public struct Iterator: AsyncIteratorProtocol {
        var base: Base.AsyncIterator
        
        var last: C.Instant?
        let interval: C.Instant.Duration
        let clock: C
        let reducing: @Sendable (Reduced?, Base.Element) async -> Reduced
        var baseNextTask: Task<Base.Element?, Error>?
        
        enum Emit {
            case timer
            case next(Base.Element?)
        }
        
        enum State {
            case waiting(CheckedContinuation<Emit, Error>)
            case notWaiting(Result<Emit, Error>?)
        }
        
        init(_ base: Base.AsyncIterator, interval: C.Instant.Duration, clock: C, reducing: @Sendable @escaping (Reduced?, Base.Element) async -> Reduced) {
            self.base = base
            self.interval = interval
            self.clock = clock
            self.reducing = reducing
        }
        
        public mutating func next() async rethrows -> Reduced? {
            var reduced: Reduced?
            let start = last ?? clock.now
            let result = Mutex<State>(.notWaiting(nil))
            repeat {
                var timerTask: Task<Void, Error>?
                do {
                    let emit = try await withTaskCancellationHandler {
                        try await withCheckedThrowingContinuation { (continuation: CheckedContinuation<Emit, Error>) in
                            result.withLock { result in
                                // Check if a previous iteration of the repeat loop has emitted a value
                                if case .notWaiting(let emittedResult?) = result {
                                    result = .notWaiting(nil)
                                    continuation.resume(with: emittedResult)
                                    return
                                } else {
                                    // Common case is that we start waiting
                                    result = .waiting(continuation)
                                }
                            }
                            
                            if reduced != nil, let last {
                                // If we already have a cached reduction start a timer so we can just emit what we already
                                // have when the timer elapses
                                timerTask = Task { [interval, last, clock] in
                                    let amount = interval - last.duration(to: clock.now)
                                    if amount > .zero {
                                        try await clock.sleep(until: clock.now.advanced(by: amount), tolerance: nil)
                                    }
                                    result.withLock { result in
                                        // In all cases, emit only if we won the race
                                        guard case .waiting(let continuation) = result else { return }
                                        result = .notWaiting(nil)
                                        continuation.resume(with: .success(Emit.timer))
                                        return
                                    }
                                }
                            }
                            
                            if reduced == nil, let baseNextTask, !baseNextTask.isCancelled {
                                // If we have no cached reduction and have a baseNextTask from a previous iteration
                                // Just wait on the baseNextTask since there's no other source of values
                                Task {
                                    let element = try await baseNextTask.value
                                    result.withLock { result in
                                        guard case .waiting(let continuation) = result else { return }
                                        result = .notWaiting(nil)
                                        continuation.resume(with: .success(.next(element)))
                                        
                                        // We can't mutate Iterator.baseNextTask back to nil from here so mark the task
                                        // as cancelled, which should be considered equivalent.
                                        baseNextTask.cancel()
                                        return
                                    }
                                }
                            } else if baseNextTask?.isCancelled ?? true {
                                // We have no "next" task so start a new one
                                baseNextTask = Task<Base.Element?, Error> { [base] in
                                    var base = base
                                    do {
                                        let element = try await base.next()
                                        result.withLock { result in
                                            switch result {
                                            case .waiting(let continuation):
                                                result = .notWaiting(nil)
                                                continuation.resume(with: .success(.next(element)))
                                            case .notWaiting:
                                                result = .notWaiting(.success(.next(element)))
                                            }
                                            
                                            // We can't mutate Iterator.baseNextTask back to nil from here so mark the task
                                            // as cancelled, which should be considered equivalent.
                                            withUnsafeCurrentTask { task in task?.cancel() }
                                            return
                                        }
                                        return element
                                    } catch {
                                        result.withLock { result in
                                            switch result {
                                            case .waiting(let continuation):
                                                result = .notWaiting(nil)
                                                continuation.resume(with: .failure(error))
                                            case .notWaiting:
                                                result = .notWaiting(.failure(error))
                                            }

                                            // We can't mutate Iterator.baseNextTask back to nil from here so mark the task
                                            // as cancelled, which should be considered equivalent.
                                            withUnsafeCurrentTask { task in task?.cancel() }
                                            return
                                        }
                                        throw error
                                    }
                                }
                            }
                        }
                    } onCancel: {
                        result.withLock { result in
                            // On cancellation, immediately complete the continuation (if possible)
                            guard case .waiting(let continuation) = result else { return }
                            result = .notWaiting(nil)
                            continuation.resume(throwing: CancellationError())
                        }
                    }
                    
                    // Clean up our unstructured tasks
                    timerTask?.cancel()
                    if let baseNextTask, baseNextTask.isCancelled {
                        self.baseNextTask = nil
                    }
                    
                    switch emit {
                    case .timer:
                        // Emit cached values when the timer fires
                        last = clock.now
                        return reduced
                    case .next(let element):
                        if let element {
                            // Reduce and cache the value
                            reduced = await reducing(reduced, element)

                            // Choose to either emit the new value or continue
                            // accumulating
                            let now = clock.now
                            if start.duration(to: now) >= interval || last == nil {
                                last = now
                                return reduced
                            }
                        } else {
                            // End of stream.
                            if reduced != nil, let last {
                                // If we're going to emit additional values, make sure we've waited enough
                                // since the previous values
                                let amount = interval - last.duration(to: clock.now)
                                if amount > .zero {
                                    try await clock.sleep(until: clock.now.advanced(by: amount), tolerance: nil)
                                }
                            }
                            return reduced
                        }
                    }
                } catch is CancellationError {
                    // Be sure to cancel unstructured tasks on the way out
                    timerTask?.cancel()
                    baseNextTask?.cancel()
                    return nil
                }
            } while true
        }
    }

Is there any roadmap for when there’ll be a solution for this? I hoped that there was a 1.1 release planned in sync with swift 6, but it seems it doesn’t work like this. I don’t really care how it’s named, I just want an async function that lets me limit the number of values per time and let’s me chose which one it filters – without omitting the last value. I can’t understand why this is an issue that’s open so long, if the code is done but the naming isn’t.

+1 Any updates on this issue so far?

A side topic, but I was somewhat surprised to see a 1.0.0 release already. There is no description or a changelog for it. Just wondering, are there some breaking changes to justify the major increment or was it more of a milestone thing? I’d personally like to see 1.0.0 when we already have feature parity with Combine (at least its first version as of iOS 13 SDK), and throttle is one thing which is missing currently and is very demanded by UI app developers.

Could you do me a favour an try to write a validation test that represents what currently is not working like you expect it to work.

Let me help there. I believe this validation test should pass but it doesn’t:

    validate {
       "ab--cd-e-f---gh|"
       $0.inputs[0].throttle(for: .steps(3), clock: $0.clock, latest: true)
       "a--b--d--f---g--[h|]"
     }

@phausler just put up a PR https://github.com/apple/swift-async-algorithms/pull/292 to change the behaviour. We would appreciate if you all could check that it is doing what you expected it to do now.

@kdubb I think that is the expected behaviour from throttle though. It will apply infinite demand as long as it has demand on itself. If you have a root asynchronous sequence that produces infinite values instantly then throttle will produce exactly one value at every interval.

I think you want another algorithm for what you describe here.

Just as a use case, I attempted to use throttle to sample the audio level from an AVAudioRecorder; which immediately returns the current value. During a simple test I realized it was consuming values at an unchecked pace.