Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

1.10/master regression on Dict/Set #51594

Closed
yuyichao opened this issue Oct 4, 2023 · 6 comments · Fixed by #51595
Closed

1.10/master regression on Dict/Set #51594

yuyichao opened this issue Oct 4, 2023 · 6 comments · Fixed by #51595
Labels
regression Regression in behavior compared to a previous version

Comments

@yuyichao
Copy link
Contributor

yuyichao commented Oct 4, 2023 •
edited
Loading

The following code triggers the "never trigger" assertion reliably.

import Base.UUID

deps = Set{Base.UUID}()
empty!(deps)
union!(deps, Base.UUID[UUID("c3fe647b-3220-5bb0-a1ea-a7954cac585d")])
union!(deps, Base.UUID[UUID("864edb3b-99cc-5e75-8d2d-829cb0a9cfe8")])
union!(deps, Base.UUID[UUID("1222c4b2-2114-5bfd-aeef-88e4692bbb3e")])
union!(deps, Base.UUID[UUID("861a8166-3701-5b0c-9a16-15d98fcdc6aa"), UUID("276daf66-3868-5448-9aa4-cd146d93841b"), UUID("a759f4b9-e2f1-59dc-863e-4aeb61b1ea8f"), UUID("77ba4419-2d1f-58cd-9bb1-8ffee604a2e3")])
empty!(deps)
union!(deps, Base.UUID[UUID("102ac46a-7ee4-5c85-9060-abc95bfdeaa3"), UUID("7c1d4256-1411-5781-91ec-d7bc3513ac07")])
union!(deps, Base.UUID[UUID("864edb3b-99cc-5e75-8d2d-829cb0a9cfe8")])
union!(deps, Base.UUID[UUID("e2ed5e7c-b2de-5872-ae92-c73ca462fb04")])
union!(deps, Base.UUID[UUID("187b0558-2788-49d3-abe0-74a17ed4e7c9"), UUID("efcf1570-3423-57d1-acb7-fd33fddbac46")])
union!(deps, Base.UUID[UUID("1520ce14-60c1-5f80-bbc7-55ef81b5835c")])
union!(deps, Base.UUID[UUID("8ea1fca8-c5ef-4a55-8b96-4e9afe9c9a3c")])
union!(deps, Base.UUID[UUID("1222c4b2-2114-5bfd-aeef-88e4692bbb3e")])
union!(deps, Base.UUID[UUID("2ee39098-c373-598a-b85f-a56591580800"), UUID("90137ffa-7385-5640-81b9-e52037218182"), UUID("615f187c-cbe4-4ef1-ba3b-2fcf58d6d173"), UUID("2f01184e-e22b-5df5-ae63-d93ebab69eaf")])
union!(deps, Base.UUID[UUID("ffbed154-4ef7-542d-bbb7-c09d3a79fcae")])
union!(deps, Base.UUID[UUID("d360d2e6-b24c-11e9-a2a3-2a2ae2dbcce4")])
union!(deps, Base.UUID[UUID("861a8166-3701-5b0c-9a16-15d98fcdc6aa"), UUID("276daf66-3868-5448-9aa4-cd146d93841b"), UUID("a759f4b9-e2f1-59dc-863e-4aeb61b1ea8f"), UUID("77ba4419-2d1f-58cd-9bb1-8ffee604a2e3")])
union!(deps, Base.UUID[UUID("37e2e46d-f89d-539d-b4ee-838fcccc9c8e")])
empty!(deps)
union!(deps, Base.UUID[UUID("102ac46a-7ee4-5c85-9060-abc95bfdeaa3"), UUID("7c1d4256-1411-5781-91ec-d7bc3513ac07")])
union!(deps, Base.UUID[UUID("864edb3b-99cc-5e75-8d2d-829cb0a9cfe8")])
union!(deps, Base.UUID[UUID("e2ed5e7c-b2de-5872-ae92-c73ca462fb04")])
union!(deps, Base.UUID[UUID("187b0558-2788-49d3-abe0-74a17ed4e7c9"), UUID("efcf1570-3423-57d1-acb7-fd33fddbac46")])
union!(deps, Base.UUID[UUID("1520ce14-60c1-5f80-bbc7-55ef81b5835c")])
union!(deps, Base.UUID[UUID("1222c4b2-2114-5bfd-aeef-88e4692bbb3e")])
union!(deps, Base.UUID[UUID("2ee39098-c373-598a-b85f-a56591580800"), UUID("90137ffa-7385-5640-81b9-e52037218182"), UUID("615f187c-cbe4-4ef1-ba3b-2fcf58d6d173"), UUID("2f01184e-e22b-5df5-ae63-d93ebab69eaf")])
union!(deps, Base.UUID[UUID("ffbed154-4ef7-542d-bbb7-c09d3a79fcae")])
union!(deps, Base.UUID[UUID("d360d2e6-b24c-11e9-a2a3-2a2ae2dbcce4")])
union!(deps, Base.UUID[UUID("861a8166-3701-5b0c-9a16-15d98fcdc6aa"), UUID("276daf66-3868-5448-9aa4-cd146d93841b"), UUID("a759f4b9-e2f1-59dc-863e-4aeb61b1ea8f"), UUID("77ba4419-2d1f-58cd-9bb1-8ffee604a2e3")])
union!(deps, Base.UUID[UUID("a7c27f48-0311-42f6-a7f8-2c11e75eb415")])
union!(deps, Base.UUID[UUID("37e2e46d-f89d-539d-b4ee-838fcccc9c8e")])
empty!(deps)
union!(deps, Base.UUID[UUID("102ac46a-7ee4-5c85-9060-abc95bfdeaa3"), UUID("7c1d4256-1411-5781-91ec-d7bc3513ac07")])
union!(deps, Base.UUID[UUID("864edb3b-99cc-5e75-8d2d-829cb0a9cfe8")])
union!(deps, Base.UUID[UUID("e2ed5e7c-b2de-5872-ae92-c73ca462fb04")])
union!(deps, Base.UUID[UUID("187b0558-2788-49d3-abe0-74a17ed4e7c9"), UUID("efcf1570-3423-57d1-acb7-fd33fddbac46")])
union!(deps, Base.UUID[UUID("1520ce14-60c1-5f80-bbc7-55ef81b5835c")])
union!(deps, Base.UUID[UUID("1222c4b2-2114-5bfd-aeef-88e4692bbb3e")])
union!(deps, Base.UUID[UUID("2ee39098-c373-598a-b85f-a56591580800"), UUID("90137ffa-7385-5640-81b9-e52037218182"), UUID("615f187c-cbe4-4ef1-ba3b-2fcf58d6d173"), UUID("2f01184e-e22b-5df5-ae63-d93ebab69eaf")])
union!(deps, Base.UUID[UUID("ffbed154-4ef7-542d-bbb7-c09d3a79fcae")])
union!(deps, Base.UUID[UUID("d360d2e6-b24c-11e9-a2a3-2a2ae2dbcce4")])
union!(deps, Base.UUID[UUID("861a8166-3701-5b0c-9a16-15d98fcdc6aa"), UUID("276daf66-3868-5448-9aa4-cd146d93841b"), UUID("a759f4b9-e2f1-59dc-863e-4aeb61b1ea8f"), UUID("77ba4419-2d1f-58cd-9bb1-8ffee604a2e3")])
union!(deps, Base.UUID[UUID("a7c27f48-0311-42f6-a7f8-2c11e75eb415")])
union!(deps, Base.UUID[UUID("37e2e46d-f89d-539d-b4ee-838fcccc9c8e")])
empty!(deps)
union!(deps, Base.UUID[UUID("1222c4b2-2114-5bfd-aeef-88e4692bbb3e")])
union!(deps, Base.UUID[UUID("861a8166-3701-5b0c-9a16-15d98fcdc6aa"), UUID("276daf66-3868-5448-9aa4-cd146d93841b"), UUID("a759f4b9-e2f1-59dc-863e-4aeb61b1ea8f"), UUID("77ba4419-2d1f-58cd-9bb1-8ffee604a2e3")])
empty!(deps)
union!(deps, Base.UUID[UUID("e9d8d322-4543-424a-9be4-0cc815abe26c")])
union!(deps, Base.UUID[UUID("102ac46a-7ee4-5c85-9060-abc95bfdeaa3"), UUID("7c1d4256-1411-5781-91ec-d7bc3513ac07")])
union!(deps, Base.UUID[UUID("864edb3b-99cc-5e75-8d2d-829cb0a9cfe8")])
union!(deps, Base.UUID[UUID("e2ed5e7c-b2de-5872-ae92-c73ca462fb04")])
union!(deps, Base.UUID[UUID("187b0558-2788-49d3-abe0-74a17ed4e7c9"), UUID("efcf1570-3423-57d1-acb7-fd33fddbac46")])
union!(deps, Base.UUID[UUID("1520ce14-60c1-5f80-bbc7-55ef81b5835c")])
union!(deps, Base.UUID[UUID("8ea1fca8-c5ef-4a55-8b96-4e9afe9c9a3c")])
union!(deps, Base.UUID[UUID("1222c4b2-2114-5bfd-aeef-88e4692bbb3e")])
union!(deps, Base.UUID[UUID("2ee39098-c373-598a-b85f-a56591580800"), UUID("90137ffa-7385-5640-81b9-e52037218182"), UUID("615f187c-cbe4-4ef1-ba3b-2fcf58d6d173"), UUID("2f01184e-e22b-5df5-ae63-d93ebab69eaf")])
union!(deps, Base.UUID[UUID("ffbed154-4ef7-542d-bbb7-c09d3a79fcae")])
union!(deps, Base.UUID[UUID("d360d2e6-b24c-11e9-a2a3-2a2ae2dbcce4")])
union!(deps, Base.UUID[UUID("861a8166-3701-5b0c-9a16-15d98fcdc6aa"), UUID("276daf66-3868-5448-9aa4-cd146d93841b"), UUID("a759f4b9-e2f1-59dc-863e-4aeb61b1ea8f"), UUID("77ba4419-2d1f-58cd-9bb1-8ffee604a2e3")])
union!(deps, Base.UUID[UUID("37e2e46d-f89d-539d-b4ee-838fcccc9c8e")])
empty!(deps)
union!(deps, Base.UUID[UUID("c3fe647b-3220-5bb0-a1ea-a7954cac585d")])

UUID("861a8166-3701-5b0c-9a16-15d98fcdc6aa") in deps

This reproduces on the Linux aarch64 binary for the 1.10 beta and also nightly but not on 1.9.3. It also reproduces on the Linux x86_64 nightly binary. From old versions I have around this does not happen on 4c32381 but does happen on 21d4c2f. I have not tried to reduce/debug/bisect this further yet.

Reduced test case:

import Base.UUID

deps = Set{UUID}([UUID("e9d8d322-4543-424a-9be4-0cc815abe26c"),
                  UUID("102ac46a-7ee4-5c85-9060-abc95bfdeaa3"),
                  UUID("7c1d4256-1411-5781-91ec-d7bc3513ac07"),
                  UUID("864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"),
                  UUID("e2ed5e7c-b2de-5872-ae92-c73ca462fb04"),
                  UUID("187b0558-2788-49d3-abe0-74a17ed4e7c9"),
                  UUID("efcf1570-3423-57d1-acb7-fd33fddbac46"),
                  UUID("1520ce14-60c1-5f80-bbc7-55ef81b5835c"),
                  UUID("8ea1fca8-c5ef-4a55-8b96-4e9afe9c9a3c"),
                  UUID("1222c4b2-2114-5bfd-aeef-88e4692bbb3e"),
                  UUID("2ee39098-c373-598a-b85f-a56591580800"),
                  UUID("90137ffa-7385-5640-81b9-e52037218182"),
                  UUID("615f187c-cbe4-4ef1-ba3b-2fcf58d6d173"),
                  UUID("2f01184e-e22b-5df5-ae63-d93ebab69eaf"),
                  UUID("ffbed154-4ef7-542d-bbb7-c09d3a79fcae"),
                  UUID("d360d2e6-b24c-11e9-a2a3-2a2ae2dbcce4"),
                  UUID("861a8166-3701-5b0c-9a16-15d98fcdc6aa"),
                  UUID("276daf66-3868-5448-9aa4-cd146d93841b"),
                  UUID("a759f4b9-e2f1-59dc-863e-4aeb61b1ea8f"),
                  UUID("77ba4419-2d1f-58cd-9bb1-8ffee604a2e3")])
union!(deps, [UUID("37e2e46d-f89d-539d-b4ee-838fcccc9c8e")])
empty!(deps)
union!(deps, [UUID("c3fe647b-3220-5bb0-a1ea-a7954cac585f")])

UUID("861a8166-3701-5b0c-9a16-15d98fcdc6aa") in deps
@yuyichao yuyichao added the regression Regression in behavior compared to a previous version label Oct 4, 2023
@vtjnash
Copy link
Member

vtjnash commented Oct 4, 2023

Looks like empty! fails to reset this value when it resets all of the other state:

julia/base/dict.jl

Line 258 in 165f728

resize!(h.keys, sz)

@yuyichao
Copy link
Contributor Author

yuyichao commented Oct 4, 2023

So it seems that 86b819c, which added the assertion, is probably the commit that triggers it.

oscardssmith added a commit that referenced this issue Oct 4, 2023
@oscardssmith
reset maxprobe on empty!
59efcab 
As pointed out in #51594 (comment), this is necessary for the assertion added in #49447 to be valid.
@oscardssmith oscardssmith mentioned this issue Oct 4, 2023
Merged
@oscardssmith
Copy link
Member

fixed by #51595

@oscardssmith
Copy link
Member

oscardssmith commented Oct 5, 2023 •
edited
Loading

Something else very odd is happening here. empty! doesn't reduce the size of the Dict, but for some reason, the next union! is shrinking the Dict, which seems somewhat pathological (why go to the effort of zeroing more data on empty! if we are just going to throw away the information the next time we add something?)

Ok. so the cause is that union! on a Set does a sizehint! I think this has potential to have accidental quadratic complexity.

@petvana
Copy link
Member

petvana commented Oct 5, 2023

Ok. so the cause is that union! on a Set does a sizehint! I think this has potential to have accidental quadratic complexity.

sizehint! is actually crucial for maintaining the complexity for union/merge operations, see #40412

@oscardssmith
Copy link
Member

so the problem is that it's only testing merging dicts of equal sizes, and ignoring the possibility that the dict already has a user chosen sizehint. I think we should change the logic to only sizehint if the anticipated length after the merge is larger than the capacity*load_factor of the dict we're merging into

oscardssmith added a commit that referenced this issue Oct 5, 2023
@oscardssmith
reset maxprobe on empty! (#51595)
c18e485 
As pointed out in
#51594 (comment),
this is necessary for the assertion added in
#49447 to be valid.

Fix #51594
KristofferC pushed a commit that referenced this issue Oct 9, 2023
@oscardssmith
reset maxprobe on empty! (#51595)
1e95bf8 
As pointed out in
#51594 (comment),
this is necessary for the assertion added in
#49447 to be valid.

Fix #51594

(cherry picked from commit c18e485)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
regression Regression in behavior compared to a previous version
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

reset maxprobe on empty! JuliaLang/julia
4 participants
@vtjnash @yuyichao @petvana @oscardssmith