[I] Explore ManualResetEvent waiter storage and state fast paths [asyncband]

["tisonkun (via GitHub)" <gi...@apache.org>]

tisonkun opened a new issue, #252:
URL: https://github.com/apache/asyncband/issues/252

   ## Background
   
   PR #243 added `ManualResetEvent` with a mutex-protected boolean state and `WaitList`. Its approval review left the internal representation as a follow-up exploration: the ideas may improve the implementation, but keeping the current design is valid if the alternatives do not preserve its contracts or reduce overall cost.
   
   ## Questions to explore
   
   1. Can `ManualResetEvent` replace `WaitList` and its per-waiter `notified` state with `WaitSet` while preserving the rule that every wait registered before `set` remains committed even if `reset` happens before its next poll?
   2. Can `is_set` and the already-set wait path use an atomic boolean, or another compact atomic state, instead of acquiring the state mutex on every observation?
   
   ## Requirements
   
   - preserve the public API and the set/reset, first-poll registration, cancellation, and memory-publication contracts introduced by #243;
   - prevent lost wake-ups across concurrent state checks, waiter registration, `set`, and `reset`;
   - keep waker clone, drop, and wake callbacks outside internal locks;
   - account for reentrant callbacks and a rapid `set` followed by `reset`;
   - compare complexity and benchmark results with the current implementation, including `is_set`, already-set waits, pending registration/cancellation, set/reset reuse, and fan-out;
   - prefer the current implementation if an alternative only moves complexity or lacks a meaningful workload benefit.
   
   Follow-up to #221 and #243. The originating approval review is [here](https://github.com/apache/asyncband/pull/243#pullrequestreview-5061484283).
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For additional commands, e-mail: commits-help@asyncband.apache.org

Re: [I] Explore ManualResetEvent waiter storage and state fast paths [asyncband]

["tisonkun (via GitHub)" <gi...@apache.org>]

tisonkun commented on issue #252:
URL: https://github.com/apache/asyncband/issues/252#issuecomment-5470306022

   ## Research notes
   
   ### Conclusion
   
   Both ideas are viable, but they are not equally independent or equally cheap:
   
   - An atomic signal bit is the best first experiment. `is_set()` and an unregistered wait that observes the set state can use an acquire load without taking the waiter lock. The bit does not replace synchronization around `set`, `reset`, and waiter registration; those transitions should initially remain serialized by the waiter lock.
   - `WaitSet` can replace `WaitList`, but not as a drop-in substitution. The event needs a new `WaitSet` operation that turns a stale/drained token into a persistent "this wait was committed" result. Without that operation, the current `register` behavior would re-register a stale token after a rapid `set`/`reset` and lose the commitment made by `set`.
   - A fully lock-free transition path is possible, but comparable implementations need packed flags, waiter generations, and more elaborate per-future state. That does not look like the right first optimization without measurements showing transition contention.
   
   ### 1. Replacing `WaitList` with `WaitSet`
   
   The event does not need `WaitList` for FIFO ordering. Its important property is that an unlinked node remains addressable: `set` marks each waiter `notified`, removes its waker, and the future can still observe that notification after `reset`.
   
   `WaitSet` already has most of an alternative representation. A non-empty `drain` advances its epoch, so a future whose token belongs to the previous epoch can infer that its waker was drained. However, that fact is currently only used to prevent slot aliasing. It is not exposed as completion, and calling `register` with such a token creates a new registration in the current epoch.
   
   A viable event-specific use therefore needs an API equivalent to `take_drained(&mut Option<WakerToken>) -> bool`, called while holding the `WaitSet` lock. Event polling would use this order:
   
   1. If an existing token belongs to an earlier epoch, clear it and return `Ready`, regardless of the current signal bit.
   2. If there is no token and the event is currently set, return `Ready`.
   3. Otherwise register or update the waker in the current epoch.
   
   `set` must change the signal state and drain the current epoch in one critical section; `reset` and the registration recheck must be ordered by that same lock. Waker clone, drop, and wake callbacks remain outside the lock.
   
   This would remove the event-specific `Waiter { notified, waker }`, the unlink loop, and detached nodes that remain allocated until their futures are polled or dropped. A queued `WaitSet` entry stores only a `Waker`, and `set` can release all arena slots immediately. The costs are less obvious at the future boundary: on a 64-bit target, the current `WaiterId` is one word while `WakerToken { epoch, slot }` is two words. More importantly, the shared `WaitSet` API gains a new semantic contract, and its checked `u64` epoch increment introduces a theoretical overflow panic into a primitive intended for unlimited reuse. That overflow policy should be resolved explicitly before adopting this representation.
   
   My assessment: this is a credible simplification experiment, not an obvious win. It should be evaluated separately from the atomic-state change so code-size, future-size, waiter-memory, and fan-out effects remain attributable.
   
   ### 2. Making the signal state atomic
   
   A simple and conservative shape is:
   
   ```rust
   struct ManualResetEvent {
       is_set: AtomicBool,
       waiters: Mutex<WaitList<Waiter>>, // or the separately evaluated WaitSet design
   }
   ```
   
   `is_set()` can use an acquire load. A wait with no existing registration can use the same load as its ready fast path. After observing `false` and cloning a waker outside the lock, it must acquire the waiter lock and recheck the atomic state before registering. The unset-to-set transition should publish `true` with release ordering.
   
   For the first version, both state-changing operations should still acquire the waiter lock and recheck the bit there. In particular, a design where `set` stores `true`, obtains the lock later to drain, and `reset` independently stores `false` is incorrect for the current contract:
   
   1. an old `set` stores `true` but has not drained yet;
   2. `reset` stores `false`;
   3. a new-generation wait registers;
   4. the old `set` drains and incorrectly commits that new wait.
   
   Serializing the state transition, cohort detach, reset, and registration recheck avoids that ABA-style race while still making the two common observation paths lock-free. Asyncband's `CountdownState` already demonstrates the atomic-probe plus lock-and-recheck pattern with `AtomicU32` and `WaitSet`, but countdown completion is monotonic; reusable reset is the additional constraint here.
   
   A packed state word is not needed merely to optimize `is_set`. It becomes useful only if we also want a lock-free `set` fast path with a `HAS_WAITERS` bit or encode a generation. That optimization has materially more proof and test surface and should follow evidence, not precede it.
   
   ### Ecosystem comparison
   
   | Implementation | State and waiters | Relevant tradeoff |
   | --- | --- | --- |
   | [.NET `ManualResetEventSlim`](https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Threading/ManualResetEventSlim.cs) | Packs the signaled bit and waiter count into an integer; `IsSet` is a volatile read, `Set` uses an interlocked update and pulses a monitor when waiters exist. | Strong precedent for an atomic observation path, but its `Reset` documentation explicitly disallows concurrent use with other members. Asyncband promises useful concurrent `set`/`reset` behavior, so its transition algorithm cannot be copied directly. |
   | [Microsoft's `AsyncManualResetEvent` sketch](https://devblogs.microsoft.com/dotnet/building-async-coordination-primitives-part-1-asyncmanualresetevent/) | Each generation is a `TaskCompletionSource`; `set` completes it and `reset` atomically swaps in a new one. | Old tasks remain complete naturally after reset. The price is a new completion object per generation and continuation-scheduling concerns during `set`. An `Arc<Generation>` design would be the analogous Rust alternative. |
   | [CPython `threading.Event`](https://github.com/python/cpython/blob/main/Lib/threading.py) | A boolean flag plus a condition lock; `set`/`clear` hold that lock, while `is_set` directly reads the flag. | Its waiter returns the condition notification result instead of re-reading the flag, so a later `clear` does not retract that notification. The direct Python read is not a Rust memory-ordering recipe, but the split between a cheap snapshot and locked transitions is relevant. |
   | [CPython `asyncio.Event`](https://github.com/python/cpython/blob/main/Lib/asyncio/locks.py) | A boolean plus a deque of per-waiter futures; `set` completes all queued futures and `clear` only changes the boolean. | This closely matches the committed-wait contract: completed waiter futures stay complete after `clear`. It can avoid thread synchronization because asyncio primitives are single-event-loop and explicitly not thread-safe. |
   | Rust [`events::ManualResetEvent`](https://docs.rs/events/latest/events/struct.ManualResetEvent.html) and its [source](https://docs.rs/crate/events/latest/source/src/manual.rs) | Uses an `AtomicU8` containing `IS_SET` and `HAS_WAITERS`, plus a mutex-protected intrusive/pinned `AwaiterSet`, waiter notification state, and generations. | It implements a directly comparable committed-wait contract and shows that more aggressive atomic transitions are possible. It also shows the amount of machinery required; this is substantially more complex than replacing the current mutex-protected boolean with `AtomicBool`. |
   | Tokio [`Notify`](https://docs.rs/tokio/latest/tokio/sync/struct.Notify.html) / [`watch`](https://docs.rs/tokio/latest/tokio/sync/watch/) | `Notify` stores at most one permit or wakes only the current cohort; `watch` retains only the latest value. | Neither is a direct manual-reset event: `Notify` has different permit/cohort semantics, and a watcher may miss an intermediate `true` followed by `false`. |
   
   ### Suggested experiment order
   
   1. Prototype `AtomicBool + Mutex<WaitList<_>>`, limiting the atomic to `is_set`, the no-token ready path, and publication of the set transition. Keep transitions and registration serialized by the waiter lock.
   2. Add focused schedules for false-probe versus registration, `set`/`reset` before repoll, cancellation before and after detach, and reentrant clone/drop/wake callbacks; preserve the existing publication test.
   3. Benchmark `is_set`, already-set waits, pending registration/cancellation, set/reset reuse, and fan-out against the merged implementation.
   4. Separately prototype `WaitSet` with an explicit drained-token observation API and resolve the epoch-overflow/API question. Compare code complexity and both per-future and per-waiter memory, not only throughput.
   5. Consider a packed atomic/generation design only if the first two experiments show that transition locking, rather than state observation or waiter storage, is a meaningful bottleneck.
   
   So the two ideas should not be bundled initially. The atomic read path directly addresses a concrete cost with a small design delta; `WaitSet` is an independent representation choice whose main expected benefit is simpler and smaller queued waiter state.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For additional commands, e-mail: commits-help@asyncband.apache.org