RESOLVED FIXED 204562
Add DefaultHash<OptionSet<T>> and HashTrait<OptionSet<T>> specializations
https://bugs.webkit.org/show_bug.cgi?id=204562
Summary Add DefaultHash<OptionSet<T>> and HashTrait<OptionSet<T>> specializations
Fujii Hironori
Reported 2019-11-24 19:34:32 PST
Add DefaultHash<OptionSet<T>> and HashTrait<OptionSet<T>> specializations
Attachments
Patch (4.80 KB, patch)
2019-11-24 19:50 PST, Fujii Hironori
no flags
Patch (4.49 KB, patch)
2019-11-24 19:51 PST, Fujii Hironori
no flags
Patch (4.74 KB, patch)
2019-11-24 20:00 PST, Fujii Hironori
no flags
Patch (4.61 KB, patch)
2019-11-24 20:06 PST, Fujii Hironori
no flags
Patch for landing (9.05 KB, patch)
2019-11-25 02:32 PST, Fujii Hironori
no flags
Fujii Hironori
Comment 1 2019-11-24 19:50:39 PST
Fujii Hironori
Comment 2 2019-11-24 19:51:55 PST
Fujii Hironori
Comment 3 2019-11-24 20:00:12 PST
Fujii Hironori
Comment 4 2019-11-24 20:06:06 PST
Daniel Bates
Comment 5 2019-11-24 22:01:19 PST
Comment on attachment 384268 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=384268&action=review This patch looks good. It can be made a tiny bit better by moving all the templates to a separate file, say OptionSetHash.h, that includes <wtf/HashTraits.h> And <wtf/HashFunctions.h> because: 1. It keeps this file focused on the data structure. 2. A separate header just for the hash stuff can include <wtf/HashTraits.h> instead of relying on that already being included. 3. Because of (2), no need to forward declare HashTraits, GenericHashTraits, etc etc, which adds noise to the implementation. 4. Putting the hash stuff in a separate file will speed up the build a tiny bit compared to not doing it since a developer will only pay the parsing cost for the hash stuff if they #include it. > Source/WTF/wtf/OptionSet.h:168 > +template<typename T> struct DefaultHash<OptionSet<T>> { This is ok as-is. The optimal solution would be to have this be a specialized IntHash<OptionSet<T>> and then defining a specialized DefaultHash whose Hash = IntHash<OptionSet<T>> because: 1. An OptionSet<> is just an unsigned integer. 2. Because of (1) it seems like a specialization of IntHash. > Source/WTF/wtf/OptionSet.h:170 > + static unsigned hash(const OptionSet<T>& key) This is ok as-is. It would be slightly better to take the argument by value because: 1. An OptionSet<> is a small value that fits in a register. 2. It avoids a deference. > Source/WTF/wtf/OptionSet.h:173 > + return DefaultHash<decltype(value)>::Hash::hash(value); This is a ok as-is. The optimal solution is to implement this in terms of IntHash<typename OptionSet<T>::StorageType>. > Source/WTF/wtf/OptionSet.h:176 > + static bool equal(const OptionSet<T>& a, const OptionSet<T>& b) This is ok as-is. It would be slightly better to take the arguments by value for the same reasons as above. > Source/WTF/wtf/OptionSet.h:188 > +template<typename T> struct HashTraits<OptionSet<T>> : GenericHashTraits<OptionSet<T>> { This is ok as-is. The optimal solution would be to have these traits be a specialized UnsignedWithZeroKeyHashTraits<OptionSet<T>> because: 1. An OptionSet<> is just an unsigned integer. 2. Defining under UnsignedWithZeroKeyHashTraits provides future expansion possibility for introducing an alternative, space-saving, HashTrait for OptionSet<> that treats the empty value as 0 (but doing so means you can never store OptionSet<T> {} in a hashed structure). > Source/WTF/wtf/OptionSet.h:193 > + return OptionSet<T>::fromRaw(std::numeric_limits<StorageType>::max()); This is ok as-is. The optimal solution is to implement this in terms of UnsignedWithZeroKeyHashTraits<typename OptionSet<T>::StorageType>. > Source/WTF/wtf/OptionSet.h:198 > + slot = OptionSet<T>::fromRaw(std::numeric_limits<StorageType>::max() - 1); This is ok as-is. The optimal solution is to also implement this in terms of UnsignedWithZeroKeyHashTraits<typename OptionSet<T>::StorageType>. > Source/WTF/wtf/OptionSet.h:203 > + return value == OptionSet<T>::fromRaw(std::numeric_limits<StorageType>::max() - 1); This is ok as-is. The optimal solution is to also implement this in terms of UnsignedWithZeroKeyHashTraits<typename OptionSet<T>::StorageType>.
Daniel Bates
Comment 6 2019-11-24 22:07:42 PST
Just to clarify, **everything** I wrote above is optional. The patch is okay to land as-is.
Fujii Hironori
Comment 7 2019-11-24 23:42:16 PST
Comment on attachment 384268 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=384268&action=review >> Source/WTF/wtf/OptionSet.h:168 >> +template<typename T> struct DefaultHash<OptionSet<T>> { > > This is ok as-is. The optimal solution would be to have this be a specialized IntHash<OptionSet<T>> and then defining a specialized DefaultHash whose Hash = IntHash<OptionSet<T>> because: > > 1. An OptionSet<> is just an unsigned integer. > 2. Because of (1) it seems like a specialization of IntHash. In your proposed approach, I need to specialize both IntHash and DefaultHash. It seems just unnecessary to me. I can't believe it is better. >> Source/WTF/wtf/OptionSet.h:170 >> + static unsigned hash(const OptionSet<T>& key) > > This is ok as-is. It would be slightly better to take the argument by value because: > > 1. An OptionSet<> is a small value that fits in a register. > 2. It avoids a deference. Will fix. >> Source/WTF/wtf/OptionSet.h:173 >> + return DefaultHash<decltype(value)>::Hash::hash(value); > > This is a ok as-is. The optimal solution is to implement this in terms of IntHash<typename OptionSet<T>::StorageType>. Will fix. >> Source/WTF/wtf/OptionSet.h:176 >> + static bool equal(const OptionSet<T>& a, const OptionSet<T>& b) > > This is ok as-is. It would be slightly better to take the arguments by value for the same reasons as above. Will fix. >> Source/WTF/wtf/OptionSet.h:188 >> +template<typename T> struct HashTraits<OptionSet<T>> : GenericHashTraits<OptionSet<T>> { > > This is ok as-is. The optimal solution would be to have these traits be a specialized UnsignedWithZeroKeyHashTraits<OptionSet<T>> because: > > 1. An OptionSet<> is just an unsigned integer. > 2. Defining under UnsignedWithZeroKeyHashTraits provides future expansion possibility for introducing an alternative, space-saving, HashTrait for OptionSet<> that treats the empty value as 0 (but doing so means you can never store OptionSet<T> {} in a hashed structure). In your proposed approach, I need to specialize both HashTraits and UnsignedWithZeroKeyHashTraits. It seems just unnecessary to me. I can't believe it is better. >> Source/WTF/wtf/OptionSet.h:198 >> + slot = OptionSet<T>::fromRaw(std::numeric_limits<StorageType>::max() - 1); > > This is ok as-is. The optimal solution is to also implement this in terms of UnsignedWithZeroKeyHashTraits<typename OptionSet<T>::StorageType>. Yeah, it'd be nice the implementation can be shared with UnsignedWithZeroKeyHashTraits. However, constructDeletedValue can't be implemented by using UnsignedWithZeroKeyHashTraits::constructDeletedValue because OptionSet doesn't have a method to get StorageType& type. Should I add a method just to do so? > Tools/TestWebKitAPI/Tests/WTF/OptionSet.cpp:442 > + HashSet<OptionSet<ExampleFlags>> hashSet; I should add a test case of OptionSet<T> {}.
Daniel Bates
Comment 8 2019-11-25 00:23:42 PST
Comment on attachment 384268 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=384268&action=review >>> Source/WTF/wtf/OptionSet.h:168 >>> +template<typename T> struct DefaultHash<OptionSet<T>> { >> >> This is ok as-is. The optimal solution would be to have this be a specialized IntHash<OptionSet<T>> and then defining a specialized DefaultHash whose Hash = IntHash<OptionSet<T>> because: >> >> 1. An OptionSet<> is just an unsigned integer. >> 2. Because of (1) it seems like a specialization of IntHash. > > In your proposed approach, I need to specialize both IntHash and DefaultHash. It seems just unnecessary to me. I can't believe it is better. Well, that's my strong opinion. It's weakly held. So, you can do what you want. >>> Source/WTF/wtf/OptionSet.h:188 >>> +template<typename T> struct HashTraits<OptionSet<T>> : GenericHashTraits<OptionSet<T>> { >> >> This is ok as-is. The optimal solution would be to have these traits be a specialized UnsignedWithZeroKeyHashTraits<OptionSet<T>> because: >> >> 1. An OptionSet<> is just an unsigned integer. >> 2. Defining under UnsignedWithZeroKeyHashTraits provides future expansion possibility for introducing an alternative, space-saving, HashTrait for OptionSet<> that treats the empty value as 0 (but doing so means you can never store OptionSet<T> {} in a hashed structure). > > In your proposed approach, I need to specialize both HashTraits and UnsignedWithZeroKeyHashTraits. It seems just unnecessary to me. I can't believe it is better. Well, that's my strong opinion. It's weakly held. So, you can do what you want. >>> Source/WTF/wtf/OptionSet.h:198 >>> + slot = OptionSet<T>::fromRaw(std::numeric_limits<StorageType>::max() - 1); >> >> This is ok as-is. The optimal solution is to also implement this in terms of UnsignedWithZeroKeyHashTraits<typename OptionSet<T>::StorageType>. > > Yeah, it'd be nice the implementation can be shared with UnsignedWithZeroKeyHashTraits. > However, constructDeletedValue can't be implemented by using UnsignedWithZeroKeyHashTraits::constructDeletedValue because OptionSet doesn't have a method to get StorageType& type. > Should I add a method just to do so? My strong opinion. weakly held is no, adding a lvalue reference getter is not needed. It is possible to implement it using UnsignedWithZero... here's two ways off the top of my head: 1. Use a local. 2. Friend this struct.
Fujii Hironori
Comment 9 2019-11-25 02:29:35 PST
Comment on attachment 384268 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=384268&action=review >>>> Source/WTF/wtf/OptionSet.h:198 >>>> + slot = OptionSet<T>::fromRaw(std::numeric_limits<StorageType>::max() - 1); >>> >>> This is ok as-is. The optimal solution is to also implement this in terms of UnsignedWithZeroKeyHashTraits<typename OptionSet<T>::StorageType>. >> >> Yeah, it'd be nice the implementation can be shared with UnsignedWithZeroKeyHashTraits. >> However, constructDeletedValue can't be implemented by using UnsignedWithZeroKeyHashTraits::constructDeletedValue because OptionSet doesn't have a method to get StorageType& type. >> Should I add a method just to do so? > > My strong opinion. weakly held is no, adding a lvalue reference getter is not needed. It is possible to implement it using UnsignedWithZero... here's two ways off the top of my head: > > 1. Use a local. > 2. Friend this struct. Oh, right. Will take #1.
Fujii Hironori
Comment 10 2019-11-25 02:32:14 PST
Created attachment 384283 [details] Patch for landing
Fujii Hironori
Comment 11 2019-11-25 17:57:20 PST
Radar WebKit Bug Importer
Comment 12 2019-11-25 17:58:18 PST
Note You need to log in before you can comment on or make changes to this bug.