`asyncio.print_call_graph()` output is exponential in the number of tasks

[deadlovelll]

Bug report

Bug description:

The size of the asyncio.print_call_graph() output is proportional to the number of paths through the "awaited by" graph, not to the number of tasks:

import asyncio
import time

async def waits_for(*deps):
    await asyncio.gather(*deps)

async def main(levels):
    fut = asyncio.Future()
    layer = [fut]
    for _ in range(levels):
        layer = [asyncio.create_task(waits_for(*layer)) for _ in range(2)]
    await asyncio.sleep(0)

    t0 = time.perf_counter()
    graph = asyncio.format_call_graph(fut)
    dt = time.perf_counter() - t0
    print(f"{2 * levels:3d} tasks -> {graph.count('* Task'):9d} nodes,"
          f"{len(graph) / 1e6:9.1f} MB,{dt:8.2f} s")

for levels in (2, 4, 6, 8, 10, 12, 14, 16, 18, 20):
    asyncio.run(main(levels))

Actual output:

  4 tasks ->         6 nodes,      0.0 MB,    0.00 s
  8 tasks ->        30 nodes,      0.0 MB,    0.00 s
 12 tasks ->       126 nodes,      0.0 MB,    0.00 s
 16 tasks ->       510 nodes,      0.1 MB,    0.00 s
 20 tasks ->      2046 nodes,      0.6 MB,    0.00 s
 24 tasks ->      8190 nodes,      2.4 MB,    0.02 s
 28 tasks ->     32766 nodes,     10.7 MB,    0.07 s
 32 tasks ->    131070 nodes,     46.4 MB,    0.33 s
 36 tasks ->    524286 nodes,    200.3 MB,    1.96 s
 40 tasks ->   2097150 nodes,    859.8 MB,    9.90 s

Expected:

 4 tasks ->         6 nodes,      0.0 MB,    0.00 s
  8 tasks ->        14 nodes,      0.0 MB,    0.00 s
 12 tasks ->        22 nodes,      0.0 MB,    0.00 s
 16 tasks ->        30 nodes,      0.0 MB,    0.00 s
 20 tasks ->        38 nodes,      0.0 MB,    0.00 s
 24 tasks ->        46 nodes,      0.0 MB,    0.00 s
 28 tasks ->        54 nodes,      0.0 MB,    0.00 s
 32 tasks ->        62 nodes,      0.0 MB,    0.00 s
 36 tasks ->        70 nodes,      0.0 MB,    0.00 s
 40 tasks ->        78 nodes,      0.0 MB,    0.00 s

Besides that, the graph is impossible to read. The cause is that capture_call_graph() renders relations as a tree, but that relation is a DAG.

Proposed fix: expand each future's "awaited by" only once

Have a fix ready for that

CPython versions tested on:

CPython main branch

Operating systems tested on:

macOS

Linked PRs

• gh-156860: Fix exponential asyncio.print_call_graph() output #156861

[kumaraditya303]

cc @1st1 @pablogsal