Title: gh-159184: Make the marshal order of set elements with equal dumps stable by gpshead · Pull Request #159197 · python/cpython · GitHub
Open Graph Title: gh-159184: Make the marshal order of set elements with equal dumps stable by gpshead · Pull Request #159197 · python/cpython
X Title: gh-159184: Make the marshal order of set elements with equal dumps stable by gpshead · Pull Request #159197 · python/cpython
Description: This is the second half of gh-159184. The first half, #159196 (merged), stopped marshal from comparing set elements, which fixed the TypeError for complex NaNs. This PR fixes the order such elements are written in.
Set elements with the same dump are NaNs that are distinct objects. marshal leaves them in set iteration order, which is the order of their addresses. That is invisible unless one of them is also referenced elsewhere in the dump; then the reference lands at a different place among them from run to run:
>>> nans = [float('nan') for _ in range(3)]
>>> len({marshal.dumps([n, set(nans)]) for n in nans})
3 # the same value every time; 1 with this PR
Change
flowchart TB
subgraph before["main"]
direction TB
b1["list of (dump, index, element)"] --> b2["PyList_Sort()"]
b2 --> b3{"run of equal dumps?"}
b3 -- no --> b4["ordered by dump"]
b3 -- yes --> b5["left in set order
= address order"]
end
subgraph after["this PR"]
direction TB
a1["array of {element, dump}"] --> a2["qsort() on the dump bytes"]
a2 --> a3{"run of equal dumps?"}
a3 -- no --> a4["ordered by dump"]
a3 -- yes --> a5["w_same_set_items()"]
a5 --> a6["already written in this dump:
first, in the order written"]
a5 --> a7["floats and complex not written yet:
interchangeable; which one is which
is decided when one is referenced again"]
end
Loading
For a run of elements with equal dumps, the order is a function of what the writer has already output, never of addresses. This uses the exact reference bookkeeping added by #159192 (merged).
The set code moves out of w_complex_object() into w_set_items(). It keeps the checks for a set whose size changes while it is marshalled (#159195, merged).
No tuples or list are allocated any more, so ordinary sets are marshalled faster. A set made only of distinct NaN objects is 10-24% slower.
Not covered
Elements that are containers with equal dumps, not written before the set (for example {(nan1,), (nan2,)} with one of the NaNs also used elsewhere), are still written in set order. A canonical order for that case amounts to graph canonisation. The compiler cannot produce it: every folded NaN is a new object.
Tests
ReferenceTestCase.test_nan_in_set_order checks exact bytes for sets of float and complex NaNs with references before, after and through other sets. test_nan_in_set also covers complex NaNs.
test_nan_constants_in_code compiles source whose constant folding produces NaNs (1e999 - 1e999) as a plain constant, in a tuple constant and in a frozenset constant (x in {...}, the only kind of set the compiler creates), and checks that the code can be marshalled and gives the same bytes in other processes. The compiler cannot make a NaN which is in a set and also referenced elsewhere, so the order fixed here is not observable from compiled code; the test documents that and would not be part of a backport.
Authored using Claude, reviewed by me.
Issue: gh-159184
Open Graph Description: This is the second half of gh-159184. The first half, #159196 (merged), stopped marshal from comparing set elements, which fixed the TypeError for complex NaNs. This PR fixes the order such eleme...
X Description: This is the second half of gh-159184. The first half, #159196 (merged), stopped marshal from comparing set elements, which fixed the TypeError for complex NaNs. This PR fixes the order such eleme...
Opengraph URL: https://github.com/python/cpython/pull/159197
X: @github
Domain: github.com
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /:user_id/:repository/pull/:id/files(.:format) |
| route-controller | pull_requests |
| route-action | files |
| fetch-nonce | v2:45e7d0d3-6580-6298-a0c9-eb7747beca53 |
| current-catalog-service-hash | ae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b |
| request-id | C758:2BE220:35E90A7:47DDDC4:6B020C69 |
| html-safe-nonce | be4e9b003190043c2ca856023d8cd292774c45694a5da983f16117e28333b8ab |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJDNzU4OjJCRTIyMDozNUU5MEE3OjQ3REREQzQ6NkIwMjBDNjkiLCJ2aXNpdG9yX2lkIjoiMTMwMTYzNjA2NzU4MTEwMzIwOSIsInJlZ2lvbl9lZGdlIjoiaWFkIiwicmVnaW9uX3JlbmRlciI6ImlhZCJ9 |
| visitor-hmac | 0358820f9034076ac4ffba558828802036a372c9b60d110a32eaab814fcfc89c |
| hovercard-subject-tag | pull_request:4822265163 |
| github-keyboard-shortcuts | repository,pull-request-list,pull-request-conversation,pull-request-files-changed,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/python/cpython/pull/159197/files |
| twitter:image | https://avatars.githubusercontent.com/u/68491?s=400&v=4 |
| twitter:card | summary_large_image |
| og:image | https://avatars.githubusercontent.com/u/68491?s=400&v=4 |
| og:image:alt | This is the second half of gh-159184. The first half, #159196 (merged), stopped marshal from comparing set elements, which fixed the TypeError for complex NaNs. This PR fixes the order such eleme... |
| og:site_name | GitHub |
| og:type | object |
| hostname | github.com |
| expected-hostname | github.com |
| None | 87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456 |
| turbo-cache-control | no-preview |
| diff-view | unified |
| go-import | github.com/python/cpython git https://github.com/python/cpython.git |
| octolytics-dimension-user_id | 1525981 |
| octolytics-dimension-user_login | python |
| octolytics-dimension-repository_id | 81598961 |
| octolytics-dimension-repository_nwo | python/cpython |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 81598961 |
| octolytics-dimension-repository_network_root_nwo | python/cpython |
| turbo-body-classes | logged-out env-production page-responsive full-width |
| disable-turbo | true |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 423dbb54c5e7bfecc838eb387c1435eb3d0e760d |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
Links:
Viewport: width=device-width