marshal.dumps() takes exponential time on nested frozensets

Bug report

marshal.dumps() marshals every element of a set or frozenset twice: once through a nested _PyMarshal_WriteObjectToString() call to compute a sort key, and once again with w_object() to write it out. If the element is itself a set, that nested call does the same for its elements, so the time doubles with every level of nesting.

import marshal, time

f = frozenset()
for _ in range(22):
    f = frozenset({f})

t = time.perf_counter()
data = marshal.dumps(f)
print(f"{time.perf_counter() - t:.3f} s for {len(data)} bytes")

depth  20:    110 ms        105 bytes
depth  21:    220 ms        110 bytes
depth  22:    449 ms        115 bytes
depth  23:    892 ms        120 bytes
depth  24:   1772 ms        125 bytes
depth  25:   3574 ms        130 bytes

Each level adds five bytes to the output and doubles the time. Depth 30 takes about two minutes, depth 40 several days.

The sorting was added in 33d95c6facd (bpo-37596, GH-27926) to make set marshalling deterministic. The same input takes 0 ms on 3.10 and 1683 ms on 3.11, and it is equally slow up to main.

Note also that the nested call starts a fresh WFILE with depth = 0, so MAX_MARSHAL_STACK_DEPTH does not bound recursion through set elements. The exponential time is reached long before the C stack, so this is not a crash.

cc @brandtbucher

Linked PRs

• gh-157128

Bắt đầu bằng cách đọc đường dẫn xử lý tập hợp của marshal quanh _PyMarshal_WriteObjectToString(), w_object() và MAX_MARSHAL_STACK_DEPTH; issue giải thích benchmark về các frozenset lồng nhau và hành vi bị ảnh hưởng. So sánh cách triển khai hiện tại với PR được liên kết gh-157128, sau đó xác minh rằng các frozenset lồng nhau ở độ sâu lớn không còn có thời gian thực thi theo cấp số nhân, đồng thời vẫn giữ đầu ra xác định.