1488413 - Investigate if CycleCollector could use a cache on top of the graph's hashtable

Status: RESOLVED FIXED

(Core :: XPCOM, enhancement)

Description

[Olli Pettay [:smaug][[e-mail]]]

Hashtable lookups are slow. Especially the access in CCGraphBuilder::AddNode shows up in profiles (these days it is inlined, but it is still there).

Initial results hint that a cache on top of hashtable could reduce hashtable usage. This is based on the guess that when traversing the objects, we often end up dealing with same objects during a short period of time.

The cache would use some memory, but only while CC is running.

Comment 1

[Olli Pettay [:smaug][[e-mail]]]

Attachment: graph_cache.diff

Based on local testing this helps quite a bit.
Cache hit rate in child process is > 50% and >40% in parent and performance profiles look quite different with this.


Hopefully the static_assert is ok for all the platforms.

remote: View your change here:
remote:   https://hg.mozilla.org/try/rev/8b5bedad2300830b45a2a63ed6b9b054233f3141
remote: 
remote: Follow the progress of your build on Treeherder:
remote:   https://treeherder.mozilla.org/#/jobs?repo=try&revision=8b5bedad2300830b45a2a63ed6b9b054233f3141
remote: recorded changegroup in replication log in 0.012s

Comment 2

[Andrew McCreight [:mccr8]]

Comment on attachment 9006277 [details] [diff] [review]
graph_cache.diff

Review of attachment 9006277 [details] [diff] [review]:
-----------------------------------------------------------------

This is a neat idea! I never thought about how there might be this kind of pattern we could take advantage of.

Did you see any performance improvement on something like the big CC you get when cleaning up the HTML spec or TechCrunch?

It looks like the patch is more or less implementing an ad-hoc fixed-size hash table. Is the expected benefit of the patch because the memory locality is a lot better when looking up in a small inline hash table rather than the big hash table?

Is there some existing standard data structure that we could use here? I guess you can't just use a regular hash table because you want to displace existing entries rather than extending out a bucket or growing the table. Failing that, I'd really like you to define a new data structure here (HashCache maybe?), with lookupForAdd() and remove() methods, so we don't have all of this hashing and lookup logic scattered around in the regular cycle collector code.

Comment 3

[Olli Pettay [:smaug][[e-mail]]]

I see AddNode often taking 25% of CC slice without the patch and ~15% with the patch.

We have exactly similar approaches elsewhere because our hashtables are slow.
There is no standard data structure for this.

Comment 4

[Andrew McCreight [:mccr8]]

(In reply to Olli Pettay [:smaug] from comment #3)
> We have exactly similar approaches elsewhere because our hashtables are slow.

If this is a common pattern, it would be worth filing a separate bug about consolidating them into a single implementation that can be shared. (That doesn't need to block this bug.)

Comment 5

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 9006277 [details] [diff] [review]
graph_cache.diff

Would you be ok taking this until we have some generic data structure for this.

Need to look at all the cases where we use the approach and figure out what the generic API would look like. At least the underlying hashtable is different, and sizes and hash calculation...
(Atoms use this, and ContentLists and something else, can't recall all cases.)

Comment 6

[Andrew McCreight [:mccr8]]

(In reply to Olli Pettay [:smaug] from comment #5)
> Would you be ok taking this until we have some generic data structure for
> this.

What I'm interested in here is something that is just the exact same code as you have now, except wrapped up in a HashCache class (no template parameters or anything).

You'd just have three methods (oops, not 2 like I said before):

  // This either returns a pointer if present, or an index, if it isn't.
  Variant<PtrInfo*, uint32_t> lookupForAdd(void* aPtr);

  void add(uint32_t aIndex, PtrInfo* aPtrInfo);

  void remove(void* aPtr);

Comment 7

[Olli Pettay [:smaug][[e-mail]]]

Attachment: graph_cache_2.diff

Ended up using Variant even though it makes code quite unreadable, since it doesn't hint what the values mean.

Comment 8

[Andrew McCreight [:mccr8]]

Comment on attachment 9006349 [details] [diff] [review]
graph_cache_2.diff

Review of attachment 9006349 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks.

Comment 9

[Olli Pettay [:smaug][[e-mail]]]

And does that still compile
remote: View your change here:
remote:   https://hg.mozilla.org/try/rev/e557aafeb0611a4a38a650f9b97bcf7ebf830688
remote: 
remote: Follow the progress of your build on Treeherder:
remote:   https://treeherder.mozilla.org/#/jobs?repo=try&revision=e557aafeb0611a4a38a650f9b97bcf7ebf830688
remote: recorded changegroup in replication log in 0.014s

Comment 10

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e1e44835bf32
To improve performance, CycleCollector could use a cache on top of the graph's hashtable, r=mccr8

Comment 11

[Eric Rahm [:erahm]]

(In reply to Olli Pettay [:smaug] from comment #5)
> Comment on attachment 9006277 [details] [diff] [review]
> graph_cache.diff
> 
> Would you be ok taking this until we have some generic data structure for
> this.
> 
> Need to look at all the cases where we use the approach and figure out what
> the generic API would look like. At least the underlying hashtable is
> different, and sizes and hash calculation...
> (Atoms use this, and ContentLists and something else, can't recall all
> cases.)

We do something similar for eTLD [1], nsNodeInfoManager [2], and as mentioned atoms [3].

[1] https://searchfox.org/mozilla-central/rev/5a18fb5aeeec99f1ca1c36a697082c221189a3b9/netwerk/dns/nsEffectiveTLDService.h#50-73
[2] https://searchfox.org/mozilla-central/rev/5a18fb5aeeec99f1ca1c36a697082c221189a3b9/dom/base/nsNodeInfoManager.h#166
[3] https://searchfox.org/mozilla-central/rev/5a18fb5aeeec99f1ca1c36a697082c221189a3b9/xpcom/ds/nsAtomTable.cpp#224-226

Comment 12

[Olli Pettay [:smaug][[e-mail]]]

And in ContentList https://searchfox.org/mozilla-central/rev/5a18fb5aeeec99f1ca1c36a697082c221189a3b9/dom/base/nsContentList.cpp#173
(I added 3 of those 4 :p )

Comment 13

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/e1e44835bf32

Comment 14

[Eric Rahm [:erahm]]

(In reply to Olli Pettay [:smaug] from comment #12)
> And in ContentList
> https://searchfox.org/mozilla-central/rev/
> 5a18fb5aeeec99f1ca1c36a697082c221189a3b9/dom/base/nsContentList.cpp#173
> (I added 3 of those 4 :p )

Filed bug 1491151.