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

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-156861

Bắt đầu từ phần triển khai call graph của asyncio, đặc biệt là capture_call_graph(), và chạy reproducer trong issue để quan sát đầu ra theo cấp số mũ. So sánh số lượng node thực tế và dự kiến, sau đó xác minh rằng graph vẫn bị giới hạn bởi số lượng task và rằng fix hiện đã được liên kết bao phủ trường hợp DAG.