Bug 190792 – topPrivatelyControlledDomain is slow

• Status: RESOLVED
• Resolution: FIXED
• Component: Page Loading

[Antti Koivisto]

It calls into some slowish CFNetwork code and ends up showing up in profiles.

[Antti Koivisto]

Created attachment 352888 [details]
patch

[Antti Koivisto]

Created attachment 352890 [details]
patch

[Alex Christensen]

Comment on attachment 352890 [details]
patch

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

> Source/WebCore/platform/mac/PublicSuffixMac.mm:51
> +    static NeverDestroyed<HashMap<String, AtomicString, ASCIICaseInsensitiveHash>> cache;

Is there really a benefit to using AtomicString here?

[Antti Koivisto]

> Is there really a benefit to using AtomicString here?

At least in theory. Many domains may map into the same top domain. It shouldn't hurt.

[Chris Dumez]

Comment on attachment 352890 [details]
patch

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

>> Source/WebCore/platform/mac/PublicSuffixMac.mm:51
>> +    static NeverDestroyed<HashMap<String, AtomicString, ASCIICaseInsensitiveHash>> cache;
> 
> Is there really a benefit to using AtomicString here?

Have you confirmed that this method is not called from multiple threads? I suspect it could be (e.g. for ITP).

[Chris Dumez]

Comment on attachment 352890 [details]
patch

At the very least, it seems we should ASSERT.

[Chris Dumez]

Comment on attachment 352890 [details]
patch

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

> Source/WebCore/platform/mac/PublicSuffixMac.mm:55
> +        cache.get().clear();

Seems very aggressive to clear the whole cache? Why not simply kick one value out like we usually do?

[Antti Koivisto]

> Seems very aggressive to clear the whole cache? Why not simply kick one
> value out like we usually do?

I tested and it turns out it is a terrible strategy for this sort of thing at least in the usual 'map.remove(map.begin())' form. Since the table is never rehashed we always end up removing keys that hash to the early part of the table and the rest are stuck forever.

[Antti Koivisto]

> Have you confirmed that this method is not called from multiple threads? I
> suspect it could be (e.g. for ITP).

Ok, I'll just switch to String.

[Chris Dumez]

(In reply to Antti Koivisto from comment #9)
> > Have you confirmed that this method is not called from multiple threads? I
> > suspect it could be (e.g. for ITP).
> 
> Ok, I'll just switch to String.

Switching to String would not be sufficient as you'd still have HashMap operations from multiple threads. That said, I do not know for sure we have multithreaded access and an assertion would suffice. If we do have multi threaded access though, then I'd suggest using String + Locks.

[Chris Dumez]

(In reply to Antti Koivisto from comment #8)
> > Seems very aggressive to clear the whole cache? Why not simply kick one
> > value out like we usually do?
> 
> I tested and it turns out it is a terrible strategy for this sort of thing
> at least in the usual 'map.remove(map.begin())' form. Since the table is
> never rehashed we always end up removing keys that hash to the early part of
> the table and the rest are stuck forever.

That's good to know. Sounds like we may want a method that returns a random iterator inside the HashMap? e.g. HashMap::random() or HashMap::any()

[Antti Koivisto]

> Switching to String would not be sufficient as you'd still have HashMap
> operations from multiple threads. That said, I do not know for sure we have
> multithreaded access and an assertion would suffice. If we do have multi
> threaded access though, then I'd suggest using String + Locks.

Yep. I'll see if it is being used.

[Antti Koivisto]

> That's good to know. Sounds like we may want a method that returns a random
> iterator inside the HashMap? e.g. HashMap::random() or HashMap::any()

Or more explicit support for this pattern:

HashMap::shrinkRandomlyToSize(size_t)

[Geoffrey Garen]

(In reply to Antti Koivisto from comment #8)
> > Seems very aggressive to clear the whole cache? Why not simply kick one
> > value out like we usually do?
> 
> I tested and it turns out it is a terrible strategy for this sort of thing
> at least in the usual 'map.remove(map.begin())' form. Since the table is
> never rehashed we always end up removing keys that hash to the early part of
> the table and the rest are stuck forever.

Why doesn't the table rehash?

[Chris Dumez]

(In reply to Geoffrey Garen from comment #14)
> (In reply to Antti Koivisto from comment #8)
> > > Seems very aggressive to clear the whole cache? Why not simply kick one
> > > value out like we usually do?
> > 
> > I tested and it turns out it is a terrible strategy for this sort of thing
> > at least in the usual 'map.remove(map.begin())' form. Since the table is
> > never rehashed we always end up removing keys that hash to the early part of
> > the table and the rest are stuck forever.
> 
> Why doesn't the table rehash?

My understanding is that we only rehash when shrinking / expanding the HashTable capacity. In this kind of pattern, we have a max entries (in this case 100) so we never need to expand / shrink. We reach 100 entries, remove HashTable::begin() then add the new entry.

[Geoffrey Garen]

(In reply to Chris Dumez from comment #15)
> (In reply to Geoffrey Garen from comment #14)
> > (In reply to Antti Koivisto from comment #8)
> > > > Seems very aggressive to clear the whole cache? Why not simply kick one
> > > > value out like we usually do?
> > > 
> > > I tested and it turns out it is a terrible strategy for this sort of thing
> > > at least in the usual 'map.remove(map.begin())' form. Since the table is
> > > never rehashed we always end up removing keys that hash to the early part of
> > > the table and the rest are stuck forever.
> > 
> > Why doesn't the table rehash?
> 
> My understanding is that we only rehash when shrinking / expanding the
> HashTable capacity. In this kind of pattern, we have a max entries (in this
> case 100) so we never need to expand / shrink. We reach 100 entries, remove
> HashTable::begin() then add the new entry.

I see. If we always remove one and add one, then the table never rehashes. Yeah, an explicit idiom to select a random entry would be nice.

[Antti Koivisto]

Created attachment 352960 [details]
patch

[EWS Watchlist]

Comment on attachment 352960 [details]
patch

Attachment 352960 [details] did not pass mac-debug-ews (mac):
Output: https://webkit-queues.webkit.org/results/9703747

Number of test failures exceeded the failure limit.

[EWS Watchlist]

Created attachment 352965 [details]
Archive of layout-test-results from ews117 for mac-sierra

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

[Antti Koivisto]

Created attachment 352967 [details]
with locking

[Antti Koivisto]

Created attachment 352969 [details]
with locking

[Chris Dumez]

We should update the code to use https://bugs.webkit.org/show_bug.cgi?id=190814 when it lands.

[WebKit Commit Bot]

Comment on attachment 352969 [details]
with locking

Clearing flags on attachment: 352969

Committed r237357: <https://trac.webkit.org/changeset/237357>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/45492955>

[Truitt Savell]

After the changes in https://trac.webkit.org/changeset/237357/webkit

The API test is now failing

Log:
https://build.webkit.org/builders/Apple%20Sierra%20Release%20WK1%20%28Tests%29/builds/13555/steps/run-api-tests/logs/stdio

build:
https://build.webkit.org/builders/Apple%20Sierra%20Release%20WK1%20%28Tests%29/builds/13555

Failed

    TestWebKitAPI.PublicSuffix.TopPrivatelyControlledDomain
        
        /Volumes/Data/slave/sierra-release/build/Tools/TestWebKitAPI/Tests/WebCore/PublicSuffix.cpp:159
        Expected equality of these values:
          String()
            Which is: 
          topPrivatelyControlledDomain("")
            Which is:

[Truitt Savell]

Reverted r237357 for reason:

API test is now failing on all platforms.

Committed r237366: <https://trac.webkit.org/changeset/237366>

[Antti Koivisto]

Created attachment 353026 [details]
patch

[Antti Koivisto]

https://trac.webkit.org/changeset/237379/webkit