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.
<rdar://problem/44469944>
Created attachment 349941 [details] Patch
Created attachment 349946 [details] Patch
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?
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
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
Created attachment 349978 [details] Patch
(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.
(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.
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.
(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.
(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.
(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.
Created attachment 350056 [details] Patch
Created attachment 350081 [details] Patch
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
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
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()).
(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()).
Created attachment 350134 [details] Patch
(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()).
Created attachment 350150 [details] Patch
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().
(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?
(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.
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.
(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>
(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>.
Created attachment 350281 [details] Patch
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.
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.