Speed Up a Slow Async Python DAG Runner by Merging Single-Parent Jobs

You are given a fairly large Python codebase that runs asynchronous tasks. The jobs and their dependencies form a directed acyclic graph (DAG): a job can start only after all of its parents have finished. The code runs slower than expected. Read the existing implementation, find out why, and make it faster. The report recalls the outline of the exercise, not the code. The investigation centered on how long each job takes to start. The optimization merges a job that has only one parent into that parent, so that fewer jobs have to be started. The final step implements two functions in the existing code that perform the merge. The full merge conditions and the two functions' interfaces were not recalled, so settle them with the interviewer; the sketch below is an assumed shape that makes the parts concrete. ```python # Assumed shape of the existing code; the real interfaces were not reported. from dataclasses import dataclass from typing import Awaitable, Callable @dataclass class Job: name: str run: Callable[[dict], Awaitable[None]] # the job's work; writes its outputs into the shared dict parents: set[str] # names of the jobs it depends on async def run_dag(jobs: dict[str, Job]) -> dict: """Starts each job once all of its parents have finished, and returns the shared dict.""" ... ``` Starting a job costs time before its `run` begins; finding out how much, and what it consists of, is part of the task. ### Clarifying Questions - How does the runner start a job: as a task in the same event loop, a thread, a separate process, or a remote worker? - How does it learn that a job is ready: is it notified when a parent finishes, or does it poll? - How do jobs pass results to their children, and are retries, timeouts and logs tracked per job? - What does "slower than expected" mean here: compared with what, measured how? ### Part 1 — Find where the time goes Explain how you would read the unfamiliar runner and measure where the time goes, and how you would confirm that job startup, rather than the work inside the jobs, explains the slowdown. ```hint Measure the gaps Compare the time between a job becoming runnable and its first useful line of work with the time it spends working. Instrument both before you change anything. ``` #### What This Part Should Cover - A measurement plan: timestamps per job and profiling of a single job's startup - Separating startup overhead from scheduling delay and from blocking calls inside coroutines - Quantifying how much of the total runtime startup accounts for along the DAG ### Part 2 — Decide which jobs can be merged The optimization merges each job that has only one parent into that parent. State the exact conditions under which such a merge is safe and worthwhile, and what the merged job looks like. ```hint One parent is not the whole story A job with one parent may have siblings, and the parent may have other children waiting for it. Check what each of those jobs would wait for after the merge. ``` #### Clarifying Questions for this Part - If the parent has several children, may it absorb one of them, all of them, or none? - Must a merged job keep per-job results, logs, retries and timeouts? - Can merges cascade along a chain of single-parent jobs? #### What This Part Should Cover - Merge conditions that preserve every dependency, with a short argument why - The effect of a merge on parallelism and on the critical path - Keeping per-job behavior intact: results, errors, retries and observability ### Part 3 — Implement the two merge functions Implement the two functions the existing code needs to perform the merge. If the interviewer agrees, one natural split is a function that finds the groups of jobs to merge, and a function that turns each group into a single job and rewires the DAG. ```hint Rewire the edges After a child is merged into its parent, every job that depended on the child must depend on the merged job instead. Decide how you update the edges, and how you check that the result is still a valid DAG. ``` #### What This Part Should Cover - Correct detection of mergeable jobs, including cascades along a chain - Correct rewiring of dependencies and preservation of acyclicity - Verification that results are unchanged, and a measured speedup ### What a Strong Answer Covers - Measures first, and attributes the time to startup with evidence before optimizing - Merge rules that never violate a dependency and that account for lost parallelism - Small, clean changes to existing code that keep the original semantics - Verification: the same outputs before and after, and a measured runtime improvement - Awareness of other async slowdowns worth ruling out, such as blocking calls on the event loop ### Follow-up Questions - Merging a parent with one of several children removes a startup but can lengthen the critical path. When would you refuse such a merge, and is there a way to avoid the trade-off? - Suppose startup turns out to be dominated by importing heavy modules in each job's worker. What would you consider instead of, or in addition to, merging? - A merged job fails in its second part. How do you retry it without redoing the first part's work? - How would you keep this slowdown from coming back as new jobs are added?