[WTF] Remove a smart pointer from HashTable issues two stores to the same location
Created attachment 274498 [details] Patch
Comment on attachment 274498 [details] Patch Attachment 274498 [details] did not pass mac-debug-ews (mac): Output: http://webkit-queues.webkit.org/results/1003189 Number of test failures exceeded the failure limit.
Created attachment 274504 [details] Archive of layout-test-results from ews115 for mac-yosemite The attached test failures were seen while running run-webkit-tests on the mac-debug-ews. Bot: ews115 Port: mac-yosemite Platform: Mac OS X 10.10.5
Comment on attachment 274498 [details] Patch Attachment 274498 [details] did not pass mac-ews (mac): Output: http://webkit-queues.webkit.org/results/1003199 Number of test failures exceeded the failure limit.
Created attachment 274505 [details] Archive of layout-test-results from ews101 for mac-yosemite The attached test failures were seen while running run-webkit-tests on the mac-ews. Bot: ews101 Port: mac-yosemite Platform: Mac OS X 10.10.5
Comment on attachment 274498 [details] Patch Attachment 274498 [details] did not pass mac-wk2-ews (mac-wk2): Output: http://webkit-queues.webkit.org/results/1003198 Number of test failures exceeded the failure limit.
Created attachment 274506 [details] Archive of layout-test-results from ews104 for mac-yosemite-wk2 The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews. Bot: ews104 Port: mac-yosemite-wk2 Platform: Mac OS X 10.10.5
Comment on attachment 274498 [details] Patch Attachment 274498 [details] did not pass ios-sim-ews (ios-simulator-wk2): Output: http://webkit-queues.webkit.org/results/1003202 Number of test failures exceeded the failure limit.
Created attachment 274507 [details] Archive of layout-test-results from ews122 for ios-simulator-wk2 The attached test failures were seen while running run-webkit-tests on the ios-sim-ews. Bot: ews122 Port: ios-simulator-wk2 Platform: Mac OS X 10.10.5
Created attachment 274555 [details] Patch
Created attachment 274695 [details] Patch
Comment on attachment 274695 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=274695&action=review > Source/WTF/wtf/HashTable.h:458 > - static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); } > + static void deleteBucket(ValueType& bucket) { hashTraitsDeleteBucket<Traits>(bucket); } I think there’s a simpler solution using move semantics for any type that can be moved: static void deleteBucket(ValueType&& bucket) { auto valueToBeDeleted = WTFMove(bucket); Traits::constructDeletedValue(bucket); } Will that work? Can we try doing that to avoid all the other work below? Do we need to use it only for certain types? > Source/WTF/wtf/HashTraits.h:136 > + static void customDeleteBucket(std::unique_ptr<T, Deleter>& value) > + { > + T* pointer = value.release(); > + constructDeletedValue(value); > + if (LIKELY(pointer)) > + Deleter()(pointer); > + } I would have written this: static void customDeleteBucket(std::unique_ptr<T, Deleter>&& value) { auto pointer = WTFMove(value); constructDeletedValue(value); } Does your version create more efficient code? Maybe it should be like this: static void customDeleteBucket(std::unique_ptr<T, Deleter>&& value) { auto pointer = WTFMove(value); constructDeletedValue(value); } > Source/WTF/wtf/HashTraits.h:149 > + ASSERT(!SimpleClassHashTraits<RefPtr<P>>::isDeletedValue(value)); Why did you assert here but not in the std::unique_ptr version? > Source/WTF/wtf/HashTraits.h:152 > + P* pointer = value.leakRef(); > + SimpleClassHashTraits<RefPtr<P>>::constructDeletedValue(value); > + derefIfNotNull(pointer); Again, why can't we use move semantics to do this? The leakRef function nulls out the value, so we are not doing anything to avoid the multiple stores. > Source/WTF/wtf/HashTraits.h:161 > + static void customDeleteBucket(String& value); I’d suggest leaving out the word “value”.
Sorry, I meant to omit all the comments except the first one. Those were from an earlier review before I had that idea.
Comment on attachment 274695 [details] Patch (In reply to comment #13) > Sorry, I meant to omit all the comments except the first one. Those were > from an earlier review before I had that idea. That's a good idea. I'll give it a try tomorrow. The reason the code is structured like this is to specialize cases where you can eliminate the null check. I can add what I need later if/when I have time to do that part.
Created attachment 274778 [details] Patch
The last patch is for reference only. It is actually significantly worse than the existing code. I suspect the slow down is caused by the non-trivial move constructor of some objects. C++ code segment sizes on x86_64: -Baseline: 19787776 bytes -Delete-Then-Store: 19779584 bytes -Store-Then-Delete: 19779584 bytes -Always WTFMove the bucket: 19791872 bytes The binary size of Delete->Store is smaller than Store->Delete. I am not sure why since I would not expect that to affect constant pools...
Created attachment 274805 [details] Patch
Comment on attachment 274805 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=274805&action=review I hoped I addressed everything. > Source/WTF/wtf/HashTraits.h:136 > + if (LIKELY(pointer)) > + Deleter()(pointer); I put this one back since the LIKELY(pointer) is helping keeping the codegen tight.
Comment on attachment 274805 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=274805&action=review > Source/WTF/ChangeLog:39 > + This patch removes 13kb out of x86_64 WebCore. That's a lot of unnecessary storing! >> Source/WTF/wtf/HashTraits.h:136 >> + Deleter()(pointer); > > I put this one back since the LIKELY(pointer) is helping keeping the codegen tight. Is this ever not true? If we put a nullptr std::unique_ptr into a WTF::HashTable, it will cause big problems well before this because it is equal to the empty value. Would it be safe to do without this branch altogether? > Source/WTF/wtf/text/StringHash.h:36 > + inline void HashTraits<String>::customDeleteBucket(String& value) You didn't add any tests for strings or atomic strings.
> > Source/WTF/ChangeLog:39 > > + This patch removes 13kb out of x86_64 WebCore. > > That's a lot of unnecessary storing! Yep! :) > >> Source/WTF/wtf/HashTraits.h:136 > >> + Deleter()(pointer); > > > > I put this one back since the LIKELY(pointer) is helping keeping the codegen tight. > > Is this ever not true? If we put a nullptr std::unique_ptr into a > WTF::HashTable, it will cause big problems well before this because it is > equal to the empty value. Would it be safe to do without this branch > altogether? That's a sad story. Initially, I had made so that all the null check are removed. But, there is code doing things like: iterator = set.find(foobar); Value myValue = WTFMove(*iterator); set.remove(iterator); So yep, it is possible to have a nullptr one you remove despite not being a valid thing to add in a table. :((In reply to comment #19)
Comment on attachment 274805 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=274805&action=review Unfortunate this ended up being so complicated, but it does seem worthwhile to to this. > Source/WTF/wtf/HashTraits.h:133 > + T* pointer = value.release(); Seems like there should be brief a comment explaining that we want to make sure the nulling and overwriting with the deleted value are not separated by a function call so we can avoid the dead store. Hard to make the comment brief, but I consider this non-obvious. >>> Source/WTF/wtf/HashTraits.h:136 >>> + Deleter()(pointer); >> >> I put this one back since the LIKELY(pointer) is helping keeping the codegen tight. > > Is this ever not true? If we put a nullptr std::unique_ptr into a WTF::HashTable, it will cause big problems well before this because it is equal to the empty value. Would it be safe to do without this branch altogether? Should add a comment explaining the non-obvious fact that the pointer can be null if someone just moved the value out of a set before deleting the bucket. > Source/WTF/wtf/HashTraits.h:150 > + ASSERT(!SimpleClassHashTraits<RefPtr<P>>::isDeletedValue(value)); I suggest writing isDeletedValue(value) instead of SimpleClassHashTraits<RefPtr<P>>::isDeletedValue(value). > Source/WTF/wtf/HashTraits.h:152 > + auto pointer = WTFMove(value); > + SimpleClassHashTraits<RefPtr<P>>::constructDeletedValue(value); Seems like this needs that same brief comment explaining that we want to make sure the nulling and overwriting with the deleted value are not separated by a function call so we can avoid the dead store. I think the local should be called smartPointerToBeDestroyed or valueToBeDestroyed or something like that. Otherwise the technique here is non-obvious. I suggest writing constructDeletedValue(value) instead of SimpleClassHashTraits<RefPtr<P>>::constructDeletedValue(value). > Source/WTF/wtf/HashTraits.h:195 > + HashTraitsCustomDeleteBucketChecker<Traits, Traits::hasCustomDeleteBucketFunction>::deleteBucket(value); We don’t need hasCustomDeleteBucketFunction because we can use instead use the SFINAE technique <http://en.cppreference.com/w/cpp/language/sfinae> to automatically chose the right version of deleteBucket based on the presence or absence of a customDeleteBucket function. Or we can do the even better and easier solution of just putting deleteBucket in GenericHashTraitsBase and overriding it instead of having customDeleteBucket. Either way, we don’t need the boolean. > Source/WTF/wtf/HashTraits.h:260 > + static_assert(std::is_trivially_destructible<KeyValuePair<int, int>>::value, > + "The wrapper itself has to be trivially destructible for customDeleteBucket() to make sense, since we do not destruct the wrapper itself."); Since this assertion is about the validity of the algorithm of customDeleteBucket, why not put it inside that function? Since it’s a compile time assertion it should be OK to have it in there instead of out here. > Source/WTF/wtf/text/AtomicStringHash.h:61 > + ASSERT(!SimpleClassHashTraits<AtomicString>::isDeletedValue(value)); I suggest writing isDeletedValue(value) instead of SimpleClassHashTraits<AtomicString>::isDeletedValue(value). > Source/WTF/wtf/text/AtomicStringHash.h:62 > + AtomicString valueToBeDeleted = WTFMove(value); Seems like this needs that same brief comment explaining that we want to make sure the nulling and overwriting with the deleted value are not separated by a function call so we can avoid the dead store. Otherwise the technique here is non-obvious. Also, thinking about C++ terminology, I think valueToBeDestroyed is accurate and valueToBeDeleted is inaccurate. > Source/WTF/wtf/text/AtomicStringHash.h:63 > + SimpleClassHashTraits<AtomicString>::constructDeletedValue(value); I suggest writing constructDeletedValue(value) instead of SimpleClassHashTraits<AtomicString>::constructDeletedValue(value). > Source/WTF/wtf/text/StringHash.h:38 > + ASSERT(!SimpleClassHashTraits<String>::isDeletedValue(value)); I suggest writing isDeletedValue(value) instead of SimpleClassHashTraits<String>::isDeletedValue(value). > Source/WTF/wtf/text/StringHash.h:39 > + String valueToBeDeleted = WTFMove(value); Seems like this needs that same brief comment explaining that we want to make sure the nulling and overwriting with the deleted value are not separated by a function call so we can avoid the dead store. Otherwise the technique here is non-obvious. Also, thinking about C++ terminology, I think valueToBeDestroyed is accurate and valueToBeDeleted is inaccurate. > Source/WTF/wtf/text/StringHash.h:40 > + SimpleClassHashTraits<String>::constructDeletedValue(value); I suggest writing constructDeletedValue(value) instead of SimpleClassHashTraits<String>::constructDeletedValue(value).
Comment on attachment 274805 [details] Patch All those places I suggested using f instead of SimpleHashTraits<xxx>::f, I might have been wrong because of template rules, but maybe we can at least just write HashTraits::f without the explicit template arguments? Do we really need to write it out like that?
I am familiar with SFINAE but I have never used it with functions. What trick do you use to do type substitution based on a static function?
I’m not entirely sure it can be done based on a static function, but I think it can. I don’t have time to work out the details myself right now, but I will do it at some point when I get a chance. I might find I was mistaken. But I think we should do the better solution just after mentioning SFINAE. Unless I was mistaken about both.
(In reply to comment #24) > But I think we should do the better solution just after mentioning SFINAE. The better solution *I suggested* just after...
(In reply to comment #25) > (In reply to comment #24) > > But I think we should do the better solution just after mentioning SFINAE. > > The better solution *I suggested* just after... I cannot define deleteBucket() before constructDeletedValue() is defined. That's the reason customDeleteBucket() exists.
Created attachment 275097 [details] Example of SFINAE used to detect the presence of a static member function OK, here’s how to use SFINAE to detect the presence of a static member function. There may be a more elegant version, but this is an existence proof that it can be done.
I did a search for "SFINAE static member function" and found various discussions of this. I attached an example that I got working. Can probably be streamlined and improved a bit.
Created attachment 275163 [details] Patch
Comment on attachment 275163 [details] Patch Clearing flags on attachment: 275163 Committed r198827: <http://trac.webkit.org/changeset/198827>
All reviewed patches have been landed. Closing bug.