[runtime] always sort transition arrays during rehashing [v8/v8 : main]
Joyee Cheung (Gerrit)
Joyee Cheung added 1 comment![]( "Open in Gerrit")
Related details
- Igor Sheludko
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Joyee Cheung (Gerrit)
Joyee Cheung added 1 comment![]( "Open in Gerrit")
PTAL, thanks!
By the way I am not sure if we should also remove the sorts added by https://chromium-review.googlesource.com/c/v8/v8/+/7252791 - the root cause for the bug that's being reproduced in the test here seems to be that the `if (entry->hash() > hash)` branch in `LinearSearchName` also implicitly assume hash-sorted order, while the previous bug was about binary search (which explicitly assumes this). Rehashing is a common way to break the assumption, I don't know if the hash-sorted order is always maintained otherwise or if there's another way to break it.
Related details
- Igor Sheludko
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Joyee Cheung (Gerrit)
Joyee Cheung added 1 comment![]( "Open in Gerrit")
Joyee CheungPTAL, thanks!
By the way I am not sure if we should also remove the sorts added by https://chromium-review.googlesource.com/c/v8/v8/+/7252791 - the root cause for the bug that's being reproduced in the test here seems to be that the `if (entry->hash() > hash)` branch in `LinearSearchName` also implicitly assume hash-sorted order, while the previous bug was about binary search (which explicitly assumes this). Rehashing is a common way to break the assumption, I don't know if the hash-sorted order is always maintained otherwise or if there's another way to break it.
Another alternative might be to fix `LinearSearchName` to no longer implicitly assume the hash-sorted order, and always append it to the end, though I feel for unblocking the V8 upgrade in Node.js that changing he insertion order the blast radius might be bigger than necessary, so maybe that could be left as a follow-up?
Related details
- Igor Sheludko
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Igor Sheludko (Gerrit)
Igor Sheludko voted and added 2 comments![]( "Open in Gerrit")
Votes added by Igor Sheludko
| Code-Review | +1 |
2 comments
Joyee CheungPTAL, thanks!
Joyee CheungBy the way I am not sure if we should also remove the sorts added by https://chromium-review.googlesource.com/c/v8/v8/+/7252791 - the root cause for the bug that's being reproduced in the test here seems to be that the `if (entry->hash() > hash)` branch in `LinearSearchName` also implicitly assume hash-sorted order, while the previous bug was about binary search (which explicitly assumes this). Rehashing is a common way to break the assumption, I don't know if the hash-sorted order is always maintained otherwise or if there's another way to break it.
Another alternative might be to fix `LinearSearchName` to no longer implicitly assume the hash-sorted order, and always append it to the end, though I feel for unblocking the V8 upgrade in Node.js that changing he insertion order the blast radius might be bigger than necessary, so maybe that could be left as a follow-up?
I agree, fixing `TA::LinearSearchName` is the right way to go. Let's land this as a quick fix and cleanup in a follow-up. Luckily we now we have tests for these cases ))
- Joyee Cheung
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Joyee Cheung (Gerrit)
Joyee Cheung voted Commit-Queue+2![]( "Open in Gerrit")
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
V8 LUCI CQ (Gerrit)
V8 LUCI CQ submitted the change![]( "Open in Gerrit")
Change information
[runtime] always sort transition arrays during rehashing
After rehashing, the arrays are no longer in hash-sorted order.
In this case, we need to force a re-sort even for small arrays,
so that subsequent linear searches can find the correct transition
and avoid inserting duplicates.
- M src/objects/objects.cc
- M src/objects/transitions.cc
- M src/objects/transitions.h
- M test/cctest/test-transitions.cc
Code-Review: +1 by Igor Sheludko
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Joyee Cheung (Gerrit)
Joyee Cheung added 1 comment![]( "Open in Gerrit")
lgtm, thanks!
Thanks for the review, I'll work on a follow up and test it with Node.js's debug build, it seems the debug mode tests in Node.js tend to uncover edge cases for this.
Related details
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |