Bug 189633 – Add count() function to OptionSet

• Component: New Bugs
• Status: NEW

[Woodrow Wang]

As of now, the OptionSet class does not have a size() function, so programmers must perform their own bit manipulation to find the size of an OptionSet, AKA the number of bits that are set. Adding this functionality should make it much easier and less convoluted to find the cardinality of an OptionSet.

[Radar WebKit Bug Importer]

<rdar://problem/44469944>

[Woodrow Wang]

Created attachment 349941 [details]
Patch

[Woodrow Wang]

Created attachment 349946 [details]
Patch

[Alex Christensen]

Comment on attachment 349946 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=349946&action=review

> Source/WTF/wtf/OptionSet.h:128
> +        return __builtin_popcountll(static_cast<unsigned long long>(m_storage));

Is there any benefit to using __builtin_popcount if m_storage is the right size?  Does the optimizer not recognize the C implementation below and generate the same thing?

[EWS Watchlist]

Comment on attachment 349946 [details]
Patch

Attachment 349946 [details] did not pass mac-wk2-ews (mac-wk2):
Output: https://webkit-queues.webkit.org/results/9249512

New failing tests:
compositing/backing/backing-store-attachment-fill-forwards-animation.html

[EWS Watchlist]

Created attachment 349975 [details]
Archive of layout-test-results from ews107 for mac-sierra-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews107  Port: mac-sierra-wk2  Platform: Mac OS X 10.12.6

[Woodrow Wang]

Created attachment 349978 [details]
Patch

[Woodrow Wang]

(In reply to Alex Christensen from comment #4)
> Comment on attachment 349946 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=349946&action=review
> 
> > Source/WTF/wtf/OptionSet.h:128
> > +        return __builtin_popcountll(static_cast<unsigned long long>(m_storage));
> 
> Is there any benefit to using __builtin_popcount if m_storage is the right
> size?  Does the optimizer not recognize the C implementation below and
> generate the same thing?

Do you know of a good way to check if the optimizer would generate the built in instructions? I feel like we shouldn't rely on the optimizer to perform this optimization unless certain that it would recognize the popcount implementation.

[Saam Barati]

(In reply to Woodrow Wang from comment #8)
> (In reply to Alex Christensen from comment #4)
> > Comment on attachment 349946 [details]
> > Patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=349946&action=review
> > 
> > > Source/WTF/wtf/OptionSet.h:128
> > > +        return __builtin_popcountll(static_cast<unsigned long long>(m_storage));
> > 
> > Is there any benefit to using __builtin_popcount if m_storage is the right
> > size?  Does the optimizer not recognize the C implementation below and
> > generate the same thing?
> 
> Do you know of a good way to check if the optimizer would generate the built
> in instructions? I feel like we shouldn't rely on the optimizer to perform
> this optimization unless certain that it would recognize the popcount
> implementation.

godbolt.org is a good place to start.

However, I don't think we should rely on the optimizer for performing an optimization of turning an entire loop into something we know can be done in a single instruction.

[Daniel Bates]

Comment on attachment 349978 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=349978&action=review

> Source/WTF/wtf/OptionSet.h:124
> +    constexpr unsigned size()

This function should be marked const as constexpr will no longer imply const in a future C++ version.

> Source/WTF/wtf/OptionSet.h:127
> +        static_assert(sizeof(StorageType) <= sizeof(unsigned long long), "__builtin_popcount is not supported for the underlying OptionSet storage type.");

__builtin_popcount => __builtin_popcountll

> Source/WTF/wtf/OptionSet.h:129
> +#else

We should also add a fast path for MSVC. According to <https://docs.microsoft.com/en-us/previous-versions/visualstudio/visual-studio-2010/bb385231(v=vs.100)>, the MSVC equivalent of __builtin_popcountll is __popcnt64 (defined in header <intrin.h>). Notice that it takes an unsigned _int64. We should take care to cast m_storage to this type and then add a static assert similar to the one for GCC/Clang.

[Alex Christensen]

(In reply to Alex Christensen from comment #4)
> Comment on attachment 349946 [details]
> Patch
> 
> Is there any benefit to using __builtin_popcount if m_storage is the right
> size?

This was not answered.

[Woodrow Wang]

(In reply to Alex Christensen from comment #11)
> (In reply to Alex Christensen from comment #4)
> > Comment on attachment 349946 [details]
> > Patch
> > 
> > Is there any benefit to using __builtin_popcount if m_storage is the right
> > size?
> 
> This was not answered.

__builtin_popcount should be significantly faster as it can use a single machine instruction to count the number of set bits.

[Woodrow Wang]

(In reply to Woodrow Wang from comment #12)
> (In reply to Alex Christensen from comment #11)
> > (In reply to Alex Christensen from comment #4)
> > > Comment on attachment 349946 [details]
> > > Patch
> > > 
> > > Is there any benefit to using __builtin_popcount if m_storage is the right
> > > size?
> > 
> > This was not answered.
> 
> __builtin_popcount should be significantly faster as it can use a single
> machine instruction to count the number of set bits.

Sorry, I misread the question. I will templatize a general countSetBits() function in MathExtras, which can take advantage of using __builtin_popcount over __builtin_popcountll if the number is the right size. It avoids a single cast, but I don't think it'd be a huge performance enhancement.

[Woodrow Wang]

Created attachment 350056 [details]
Patch

[Woodrow Wang]

Created attachment 350081 [details]
Patch

[EWS Watchlist]

Comment on attachment 350081 [details]
Patch

Attachment 350081 [details] did not pass mac-wk2-ews (mac-wk2):
Output: https://webkit-queues.webkit.org/results/9263793

New failing tests:
accessibility/smart-invert-reference.html

[EWS Watchlist]

Created attachment 350086 [details]
Archive of layout-test-results from ews107 for mac-sierra-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews107  Port: mac-sierra-wk2  Platform: Mac OS X 10.12.6

[Anders Carlsson]

I don't think size() is the right name for this - I thought it returned the size of the underlying storage. (In fact, that's what std::bitset's size() function returns).

How about count() or countSetBits() instead? (boost's dynamic_bitset uses count()).

[Saam Barati]

(In reply to Anders Carlsson from comment #18)
> I don't think size() is the right name for this - I thought it returned the
> size of the underlying storage. (In fact, that's what std::bitset's size()
> function returns).

I had this same reaction initially.  But then I reasoned about it being a Set type, and we ask for a size() of a Set type all over WebKit code. For example, I think it’d be inconsistent for this to be a different name than HashSet size(). 
> 
> How about count() or countSetBits() instead? (boost's dynamic_bitset uses
> count()).

[Woodrow Wang]

Created attachment 350134 [details]
Patch

[Woodrow Wang]

(In reply to Anders Carlsson from comment #18)
> I don't think size() is the right name for this - I thought it returned the
> size of the underlying storage. (In fact, that's what std::bitset's size()
> function returns).
The general function in MathExtras is called countSetBits(), as a programmer using that function is likely thinking on the level of bits. My understanding for the OptionSet is that it's an abstraction of the underlying bit representation as a set. I think it's common practice for a set class to then provide a size() implementation to mirror cardinality in a mathematical set. 
> 
> How about count() or countSetBits() instead? (boost's dynamic_bitset uses
> count()).

[Woodrow Wang]

Created attachment 350150 [details]
Patch

[Simon Fraser (smfr)]

Comment on attachment 350150 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=350150&action=review

> Source/WTF/wtf/OptionSet.h:127
> +    constexpr unsigned size() const
> +    {
> +        return WTF::countSetBits(m_storage);
> +    }

I agree that this should not be called size().

[Saam Barati]

(In reply to Simon Fraser (smfr) from comment #23)
> Comment on attachment 350150 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=350150&action=review
> 
> > Source/WTF/wtf/OptionSet.h:127
> > +    constexpr unsigned size() const
> > +    {
> > +        return WTF::countSetBits(m_storage);
> > +    }
> 
> I agree that this should not be called size().

Can you explain why? Why should the implementation details of this class bleed into its names?

[Simon Fraser (smfr)]

(In reply to Saam Barati from comment #24)
> (In reply to Simon Fraser (smfr) from comment #23)
> > Comment on attachment 350150 [details]
> > Patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=350150&action=review
> > 
> > > Source/WTF/wtf/OptionSet.h:127
> > > +    constexpr unsigned size() const
> > > +    {
> > > +        return WTF::countSetBits(m_storage);
> > > +    }
> > 
> > I agree that this should not be called size().
> 
> Can you explain why? Why should the implementation details of this class
> bleed into its names?

I already find .size() on Vector ambiguous (number of items, or size in bytes?) and wish it were called count().

size() on OptionSet() is more ambiguous: is it the sizes in bytes, the total number of bits that it can hold, or the number of bits currently set? count() would be clearer.

[Woodrow Wang]

Given the similarities to std::bitset, I'll rename the function to count(). In std::bitset, size() refers to capacity of the set, whereas count() is used to return the number of turned on bits.

[Daniel Bates]

(In reply to Anders Carlsson from comment #18)
> I don't think size() is the right name for this - I thought it returned the
> size of the underlying storage. (In fact, that's what std::bitset's size()
> function returns).
> 

Although you added this class, I was never under the impression that OptionSet was meant to be comparable to std::bitset, which is used to represent actual "bits" and supports random access. OptionSet does not support random access and seems closer in purpose to Qt's QFlag class [1]. In the domain of OptionSet, the elements of the "set" are flags (read: not bits). It seems natural to want to ask for the number of flags in the "set". It seems unnatural to ask for the number of possible flags the set can hold.
 
> How about count() or countSetBits() instead? (boost's dynamic_bitset uses
> count()).

I do not have a strong opinion for calling the function that returns the number of flags in the set size() or count(). I prefer that we be consistent with similar purpose functions. If we choose to go with count() then I suggest that we should consider renaming other size() functions to count, including Vector::size() and HashSet::size().

[1] <http://doc.qt.io/archives/qt-4.8/qflags.html>

[Daniel Bates]

(In reply to Daniel Bates from comment #27)
> [1] <http://doc.qt.io/archives/qt-4.8/qflags.html>

The latest documentation for this class is at <http://doc.qt.io/qt-5/qflags.html>.

[Woodrow Wang]

Created attachment 350281 [details]
Patch

[Robin Morisset]

Comment on attachment 350281 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=350281&action=review

WTF already has a bitCount() function in StdLibExtras with the same meaning as countSetBits from this patch. Optimizing it like in this patch and using it for a count() function in OptionSet sounds better than duplicating it.

> Source/WTF/wtf/MathExtras.h:578
> +template<typename T> constexpr unsigned countSetBitsSlow(T number)

I suspect the branchless implementation currently in StdLibExtra::bitCount() is probably faster.

> Source/WTF/wtf/MathExtras.h:596
> +    template<typename T> constexpr unsigned operator()(T number)

It is not entirely clear that builtins can be called in a constexpr context. From a quick search online, it seems to be tolerated by GCC at least, but it is neither standards compliant nor documented, and I am afraid this might break in the future or on some other compilers.
I would recommend only keeping countSetBitsSlow as constexpr, and then anyone that needs to compute bit counts in a constexpr expression can call it directly, leaving countSetBits for non-constexpr contexts.

> Source/WTF/wtf/MathExtras.h:601
> +        return __popcnt(number);

https://docs.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64?view=vs-2019 warns that it is undefined behavior to call __popcnt() on a machine that does not have this instruction.
So in particular any old x86 platform (before SSE4 approximately), any non-x86 platform, etc.. would likely break in that case, and silently.
I am not entirely sure how to deal with it properly, running __cpuid every time would be obviously too costly.

> Source/WTF/wtf/MathExtras.h:616
> +        return __popcnt64(number);

Ditto.

> Source/WTF/wtf/MathExtras.h:619
> +        return __popcnt(static_cast<UnsignedType>(number) >> 32) + __popcnt(number & 0xFFFFFFFF);

Ditto.
Also I think that the static cast is in the wrong place: shifting by 32 after having casted to a 32-bit integer is undefined behavior.
I would rather do __popcnt(static_cast<UnsignedType>(number >> 32)) + __popcnt(static_cast<UnsignedType>(number & 0xFFFFFFFF));

> Source/WTF/wtf/OptionSet.h:124
> +    constexpr unsigned count() const

Probably not constexpr if it uses builtins.

[Alex Christensen]

Comment on attachment 350281 [details]
Patch

This has been requesting review for more than one year.  If this is still needed, please rebase and re-request review.