Skip to content

Executor scheduling efficiency: O(N^2) readiness re-scan #56

Description

@qinhaihong-red

Parent

#4

What to build

Found by the #4 review (deferred — real wasted work, but no executor-level scale test exists yet and the change is non-trivial; not needed for #4's correctness).

The concurrent scheduler recomputes readiness by full-scanning all nodes and rebuilding running/done sets on every scheduler wakeup, giving O(N^2) scheduling per run — even though an in-degree counter already exists and is decremented on each success. Drive readiness from a ready-frontier: when a node's in-degree reaches 0 (or it is skipped), push its now-unblocked dependents onto the frontier; the launch loop pops from the frontier. Target O((V+E)) scheduling, preserving the declaration-order tie-break exactly (the model layer's unit test pins it).

This bites at Pattern-Expander scale (hundreds–thousands of nodes); hand-written workflows never notice.

Acceptance criteria

  • Scheduling is O((V+E)) (or O((V+E) log V)) rather than O(N^2), with the declaration-order tie-break among ready nodes preserved
  • Existing parallel/skip/failure tests stay green unchanged
  • A scale guard exercises the executor (not just the model layer) on a large fan-out within a generous time bound

Blocked by

None - can start immediately

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or requestready-for-agentFully specified, ready for an AFK agent

    Type

    No type

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions