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

首先阅读 _PyMarshal_WriteObjectToString()、w_object() 和 MAX_MARSHAL_STACK_DEPTH 附近的 marshal 集合处理路径；issue 解释了嵌套 frozenset 基准测试以及受影响的行为。将当前实现与链接的 PR gh-157128 进行比较，然后验证深度嵌套的 frozenset 不再表现出指数级的执行时间，同时保持确定性输出。