[webkit-reviews] review granted: [Bug 236997] [WTF] LikelyDenseUnsignedIntegerSet::add can cause a very slow reindexing of the entire bit vector with every call in the worst case : [Attachment 452784] Patch

[bugzilla-daemon at webkit.org]

Saam Barati <sbarati at apple.com> has granted Robin Morisset
<rmorisset at apple.com>'s request for review:
Bug 236997: [WTF] LikelyDenseUnsignedIntegerSet::add can cause a very slow
reindexing of the entire bit vector with every call in the worst case
https://bugs.webkit.org/show_bug.cgi?id=236997

Attachment 452784: Patch

https://bugs.webkit.org/attachment.cgi?id=452784&action=review




--- Comment #2 from Saam Barati <sbarati at apple.com> ---
Comment on attachment 452784
  --> https://bugs.webkit.org/attachment.cgi?id=452784
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?