René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"sys.settrace suffers quadratic behavior for large dictionary literals on 3.12+","articleBody":"# Bug report\n\n### Bug description:\n\nUsing a trace function with sys.settrace, performance suffers when importing a large dictionary literal.  The performance exhibits quadratic time complexity on 3.12 and up.  It is fine on 3.11.\n\nThis originated with a coverage.py bug report: https://github.com/nedbat/coveragepy/issues/1906\n\nTo reproduce, create make_mapping.py:\n\n```python\n\"\"\"\nCreate a really large dict to import.\n\"\"\"\n\nimport random\n\nprint(\"MAPPING = {\")\nfor n in range(25_000):\n    print(f\"    '{n:08d}': {n},\")\nprint(\"}\")\n```\n\nand trace_it.py:\n\n```python\nimport linecache, sys, time\n\nt0 = tlast = time.monotonic_ns()\n\ndef trace(frame, event, arg):\n    global tlast\n    if \"mapping.py\" in frame.f_code.co_filename:\n        lineno = frame.f_lineno\n        now = time.monotonic_ns()\n        print(\"{:12d} ({}): {} {:05d}\".format(\n            now - t0, now - tlast,\n            event[:4], lineno,\n        ))\n        tlast = now\n    return trace\n\nprint(sys.version)\nsys.settrace(trace)\n\nimport mapping\n```\n\nThen, create the large mapping, and run trace_it.py on multiple versions, and look at the timings:\n\n```\npython3 make_mapping.py \u003e mapping.py\npython3.11 trace_it.py \u003e 11.out\npython3.12 trace_it.py \u003e 12.out\npython3.13 trace_it.py \u003e 13.out\npython3.14 trace_it.py \u003e 14.out\ngrep 'line \\d[05]000' *.out\n```\n\nThese are the results I see. The parenthetical numbers are nanoseconds since the last output line:\n\n```\n11.out:    76131833 (1917): line 05000\n11.out:    86116875 (917): line 10000\n11.out:    96115250 (917): line 15000\n11.out:   106099958 (958): line 20000\n11.out:   116161416 (875): line 25000\n\n12.out:   803728958 (148833): line 05000\n12.out:  3009835500 (293042): line 10000\n12.out:  6750690750 (444833): line 15000\n12.out: 11966781625 (596292): line 20000\n12.out: 18720473667 (739000): line 25000\n\n13.out:   443250333 (75125): line 05000\n13.out:  1565451416 (147583): line 10000\n13.out:  3447408625 (220625): line 15000\n13.out:  6130466958 (294458): line 20000\n13.out:  9455595416 (370500): line 25000\n\n14.out:   445441625 (89291): line 05000\n14.out:  1556189584 (152250): line 10000\n14.out:  3410512125 (220625): line 15000\n14.out:  6007919334 (366584): line 20000\n14.out:  9369414792 (375083): line 25000\n```\n\n\n### CPython versions tested on:\n\n3.11, 3.12, 3.13, 3.14\n\n### Operating systems tested on:\n\nmacOS\n\n\u003c!-- gh-linked-prs --\u003e\n### Linked PRs\n* gh-128350\n* gh-129127\n* gh-132268\n\u003c!-- /gh-linked-prs --\u003e\n","author":{"url":"https://github.com/nedbat","@type":"Person","name":"nedbat"},"datePublished":"2024-12-14T21:00:26.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":15},"url":"https://github.com/127953/cpython/issues/127953"}