sys.settrace suffers quadratic behavior for large dictionary literals on 3.12+

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: https://github.com/nedbat/coveragepy/issues/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 mapping

Then, 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

Linked PRs

• gh-128350
• gh-129127
• gh-132268

Bắt đầu bằng cách chạy make_mapping.py và trace_it.py với sys.settrace trên các phiên bản Python được liệt kê, sau đó so sánh đầu ra thời gian tại mỗi khoảng 5.000 dòng. Xem xét các PR được liên kết gh-128350, gh-129127 và gh-132268 trước khi điều tra thêm; được coi là hoàn tất khi việc import các dictionary lớn không còn cho thấy thời gian bậc hai khi tracing.