Avoid full task-list scans for async identity lookup and dependent wakeups
- Dominant language
- Rust
- Stars
- 53
- Forks
- 16
- Avg merge
- 4h 22m
- Merged PRs (30d)
- 46
Description
The executor performs linked-list scans in `_find`, `_wake_dependents`, and each `_drive` scheduling round. Task records are retained for reuse until shutdown. After a large fan-out has completed, operations can still traverse the historical high-water list; waking many dependents also produces quadratic work in the number of task slots.
This is a source-level complexity finding, not a claimed benchmark result. A focused patch should establish deterministic work counters before choosing data structures.
Source evidence at the head of #520:
- [std/task.wave:167](https://github.com/wavefnd/Wave/blob/2ae0a91c57fd76323124c0e4dff552adbfadbe1b/std/task.wave#L167) — `fun _find`
- [std/task.wave:175](https://github.com/wavefnd/Wave/blob/2ae0a91c57fd76323124c0e4dff552adbfadbe1b/std/task.wave#L175) — `fun _wake_dependents`
- [std/task.wave:306](https://github.com/wavefnd/Wave/blob/2ae0a91c57fd76323124c0e4dff552adbfadbe1b/std/task.wave#L306) — `export(c, "__wave_task_drive")`
Acceptance:
- [ ] Add bounded fan-out/join and grow-then-shrink workloads with operation or traversal counters rather than timing-only gates.
- [ ] Provide efficient identity lookup and explicit dependency/ready bookkeeping while keeping the single-threaded executor model.
- [ ] Ensure completed/reused slots do not make steady-state work proportional to all historical slots.
- [ ] Preserve single-consumer futures, wake coalescing and cancellation correctness.
Related: #444. This is a focused complexity follow-up to its initial executor, not a request for a multithreaded runtime.
Audit status: identified by static source inspection; the scenarios above have not been executed during this audit. This follows up the implementation introduced in draft PR #520.
Contributor guide
Research direction
Start in std/task.wave at _find, _wake_dependents, and __wave_task_drive, then establish deterministic operation or traversal counters for bounded fan-out/join and grow-then-shrink workloads. Done means the workloads show bounded steady-state work while preserving single-consumer futures, wake coalescing, cancellation correctness, and the single-threaded executor model.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100