sys.settrace suffers quadratic behavior for large dictionary literals on 3.12+ #127953
Description
Bug report
Bug description:
Using 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.
This originated with a coverage.py bug report: coveragepy/coveragepy#1906
To reproduce, create make_mapping.py:
""" Create a really large dict to import. """ import random print("MAPPING = {") for n in range(25_000): print(f" '{n:08d}': {n},") print("}")and trace_it.py:
import linecache, sys, time t0 = tlast = time.monotonic_ns() def trace(frame, event, arg): global tlast if "mapping.py" in frame.f_code.co_filename: lineno = frame.f_lineno now = time.monotonic_ns() print("{:12d} ({}): {} {:05d}".format( now - t0, now - tlast, event[:4], lineno, )) tlast = now return trace print(sys.version) sys.settrace(trace) import mappingThen, create the large mapping, and run trace_it.py on multiple versions, and look at the timings:
python3 make_mapping.py > mapping.py python3.11 trace_it.py > 11.out python3.12 trace_it.py > 12.out python3.13 trace_it.py > 13.out python3.14 trace_it.py > 14.out grep 'line \d[05]000' *.out These are the results I see. The parenthetical numbers are nanoseconds since the last output line:
11.out: 76131833 (1917): line 05000 11.out: 86116875 (917): line 10000 11.out: 96115250 (917): line 15000 11.out: 106099958 (958): line 20000 11.out: 116161416 (875): line 25000 12.out: 803728958 (148833): line 05000 12.out: 3009835500 (293042): line 10000 12.out: 6750690750 (444833): line 15000 12.out: 11966781625 (596292): line 20000 12.out: 18720473667 (739000): line 25000 13.out: 443250333 (75125): line 05000 13.out: 1565451416 (147583): line 10000 13.out: 3447408625 (220625): line 15000 13.out: 6130466958 (294458): line 20000 13.out: 9455595416 (370500): line 25000 14.out: 445441625 (89291): line 05000 14.out: 1556189584 (152250): line 10000 14.out: 3410512125 (220625): line 15000 14.out: 6007919334 (366584): line 20000 14.out: 9369414792 (375083): line 25000 CPython versions tested on:
3.11, 3.12, 3.13, 3.14
Operating systems tested on:
macOS