`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

Beginne bei der asyncio-Implementierung des Aufrufgraphen, insbesondere bei capture_call_graph(), und führe den Reproducer aus dem Issue aus, um die exponentielle Ausgabe zu beobachten. Vergleiche die tatsächliche und die erwartete Anzahl der Knoten und überprüfe anschließend, dass der Graph durch die Anzahl der Tasks beschränkt bleibt und dass der bereits verlinkte Fix den DAG-Fall abdeckt.