Bug 155676 – [WTF] Removing a smart pointer from HashTable issues two stores to the same location

• Component: New Bugs
• Status: RESOLVED FIXED

[Benjamin Poulain]

[WTF] Remove a smart pointer from HashTable issues two stores to the same location

[Benjamin Poulain]

Created attachment 274498 [details]
Patch

[Build Bot]

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.

[Build Bot]

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

[Build Bot]

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.

[Build Bot]

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

[Build Bot]

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.

[Build Bot]

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

[Build Bot]

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.

[Build Bot]

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

[Benjamin Poulain]

Created attachment 274555 [details]
Patch

[Benjamin Poulain]

Created attachment 274695 [details]
Patch

[Darin Adler]

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”.

[Darin Adler]

Sorry, I meant to omit all the comments except the first one. Those were from an earlier review before I had that idea.

[Benjamin Poulain]

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.

[Benjamin Poulain]

Created attachment 274778 [details]
Patch

[Benjamin Poulain]

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...

[Benjamin Poulain]

Created attachment 274805 [details]
Patch

[Benjamin Poulain]

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.

[Alex Christensen]

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.

[Benjamin Poulain]

> > 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)

[Darin Adler]

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).

[Darin Adler]

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?

[Benjamin Poulain]

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?

[Darin Adler]

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.

[Darin Adler]

(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...

[Benjamin Poulain]

(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.

[Darin Adler]

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.

[Darin Adler]

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.

[Benjamin Poulain]

Created attachment 275163 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 275163 [details]
Patch

Clearing flags on attachment: 275163

Committed r198827: <http://trac.webkit.org/changeset/198827>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.