| Summary: | [WTF] LikelyDenseUnsignedIntegerSet::add can cause a very slow reindexing of the entire bit vector with every call in the worst case | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Product: | WebKit | Reporter: | Robin Morisset <rmorisset> | ||||||
| Component: | Web Template Framework | Assignee: | Robin Morisset <rmorisset> | ||||||
| Status: | RESOLVED FIXED | ||||||||
| Severity: | Normal | CC: | benjamin, cdumez, cmarcelo, ews-watchlist, jbedard, keith_miller, mark.lam, msaboff, saam, tzagallo, webkit-bug-importer | ||||||
| Priority: | P2 | Keywords: | InRadar | ||||||
| Version: | WebKit Nightly Build | ||||||||
| Hardware: | Unspecified | ||||||||
| OS: | Unspecified | ||||||||
| Bug Depends on: | |||||||||
| Bug Blocks: | 236269 | ||||||||
| Attachments: |
|
||||||||
|
Description
Robin Morisset
2022-02-21 15:11:25 PST
Created attachment 452784 [details]
Patch
Comment on attachment 452784 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=452784&action=review r=me, this looks good. I wonder if there's something even more we can do here, that's less divide run time by 64, and perhaps more along the lines of "double memory each time you grow a vector" amortization. I'm not sure we need to go too crazy right now, but just food for thought. What if we were able to instead divide our minimum by 2 (or 4, or similar) each time, if we have reason to believe the set will stay dense. > Source/WTF/ChangeLog:19 > + On an M1 MBP (2019), on testair:: testZDefOfSpillSlotWithOffsetNeedingToBeMaterializedInARegister, with n=5000, in release mode, measuring just the time spent building the interference graph: I think you meant 2020 here. > Source/WTF/wtf/BitVector.cpp:110 > + ASSERT(shiftInWords + 1 <= newNumWords); RELEASE_ASSERT? > Source/WTF/wtf/BitVector.cpp:117 > + ASSERT(shiftInWords + oldNumWords <= newNumWords); RELEASE_ASSERT? > Source/WTF/wtf/LikelyDenseUnsignedIntegerSet.h:164 > + m_inline.bitVector.shiftRightByMultipleOf64(m_min - newMin); nit: ASSERT that newMin < m_min? 3 failures in https://ews-build.webkit.org/#/builders/70/builds/972 are known, stopped the build before retries. Created attachment 454029 [details]
Patch
Comment on attachment 454029 [details]
Patch
Trying to land this, as all bots are green except for iOS-wk2 which is visibly broken for all patches.
Committed r291027 (248201@main): <https://commits.webkit.org/248201@main> All reviewed patches have been landed. Closing bug and clearing flags on attachment 454029 [details]. |