shahar1 opened a new pull request, #67688: URL: https://github.com/apache/airflow/pull/67688
Further optimization of `TaskGroup.topological_sort` to handle reverse-declared DAGs (where many children are declared before their dependents) efficiently. This is the follow-up to PR #67288. ## Summary Addresses the O(N²) worst-case behavior of the greedy-sweep approach on adversarial DAG shapes (e.g., reverse-insertion chains). Uses a hybrid strategy: - **Forward-declared DAGs** (common case): greedy multi-pass sweep, O(V + E) - **Reverse-declared DAGs** (many back edges): pass-number traversal via Kahn's algorithm, O((V + E) log V) Both approaches emit the same order: level-by-legacy-pass, ties broken by insertion order. ## Test Plan - Existing topological sort tests continue to pass (order invariant) - New optimization dispatches transparently based on back-edge ratio - Benchmark on reverse-chain shape shows dramatic improvement (previously 7.8x from #67288, now further optimized) --- ##### Was generative AI tooling used to co-author this PR? - [X] Yes — Claude Code (Haiku 4.5) Generated-by: Claude Code (Haiku 4.5) following [the guidelines](https://github.com/apache/airflow/blob/main/contributing-docs/05_pull_requests.rst#gen-ai-assisted-contributions) -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
