1005500 - Use a separate linear scan pass to mark nodes white in ScanRoots

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Andrew McCreight [:mccr8]]

Doing some profiling with ICC, the largest slice is the one that does ScanRoots+CollectWhite.  On a TechCrunch page close CC, this takes about 11ms total.  About 3ms of this is WalkFromRoots() in ScanRoots().

That code has this comment:
    // On the assumption that most nodes will be black, it's
    // probably faster to use a GraphWalker than a
    // NodePool::Enumerator.

Thanks to cycle collector optimizations, this assumption is no longer true.  Aside from the case of leaking pages, large graphs are mostly garbage.  For instance, the TechCrunch page close CC is 96% garbage.

I wrote a prototype graph coloring pass that does the following:
1. Look at every node in order, and mark gray ones white or black, depending on the refcount.
2. Look at every node in order, and flood black from any black nodes.

Doing that reduces the time for this phase of graph coloring from 3ms to 0.3ms, a 10x improvement.  This reduces the max pause on TechCrunch page close to 8ms (with patches for bug 861449 and bug 1005396 also applied, and the slice budget lowered to 5ms).

This could probably be tweaked a bit by doing the black flooding first (as mentioned in bug 722089), but that first pass is fast enough it probably doesn't matter.

Comment 1

[Andrew McCreight [:mccr8]]

I think this works better if step 1 only marks nodes white, not black.  Then in step 2, we flood black on any gray node.  With this approach, we know that if a node is marked black that all of its children are also marked black, so we don't need to look at it at all.

I think flooding black first doesn't really buy you anything.  We have to scan every object first before we flood black, so we can check that the refcounts are sensible, except that we don't check anything that was marked black by the incremental roots pass, because we know they are likely to be messed up anyways.  So we might as well mark things white at the same time to avoid an additional later pass.  And in any event, scanning all nodes in order seems to be quite cheap, probably because there's very good cache locality.  The first pass doesn't even look at the edges array.

Comment 2

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

(In reply to Andrew McCreight [:mccr8] from comment #1)
> I think this works better if step 1 only marks nodes white, not black.  Then
> in step 2, we flood black on any gray node.
But white can become black, if something in the graph is black. But ok.


>  With this approach, we know
> that if a node is marked black that all of its children are also marked
> black, so we don't need to look at it at all.
Ah, yes, this is nice.

Comment 3

[Andrew McCreight [:mccr8]]

> But white can become black, if something in the graph is black. But ok.
Yeah, it is wasted work, but I think we have to read from that node anyways, so doing a write should be cheap.

It might be worthwhile to see why graph flooding is so expensive, but for now I think it is okay to just avoid using it much when the graph is mostly garbage.

Comment 4

[Andrew McCreight [:mccr8]]

Attachment: Speed up ScanRoots() graph coloring when there's lot of garbage. WIP.

Comment 5

[Andrew McCreight [:mccr8]]

try run: https://tbpl.mozilla.org/?tree=Try&rev=402159c706d6

Comment 6

[Andrew McCreight [:mccr8]]

Attachment: Use a separate linear scan pass to mark nodes white in ScanRoots.

The problem with the previous version of my patch is that I wasn't skipping
nodes that had been deleted from the graph (mParticipant is null).
The current behavior of WalkFromRoots() already does that. I think when
you forget to do that, you end up with nodes that would have been set
as incremental roots, and they are in some weird state in the graph,
but because they were deleted, they are no longer in the purple buffer,
and thus don't get set as incremental roots.

This patch removes the last use of WalkFromRoots(), but Olli said he
has a patch that uses it, so I'm leaving it here.

try run: https://tbpl.mozilla.org/?tree=Try&rev=f12ca07e3803

The L64 debug try run looks good, but this patch is pretty scary, so I think
I'll do a full try run.  This code hasn't changed much since the original landing
of the cycle collector.  It is only a perf bottleneck now due to ICC.

There's probably some improvements that could be made to the flooding
algorithm, but I think for ScanRoots this is good enough.

Comment 7

[Andrew McCreight [:mccr8]]

Comment on attachment 8418987 [details] [diff] [review]
Use a separate linear scan pass to mark nodes white in ScanRoots.

all try run looks good: https://tbpl.mozilla.org/?tree=Try&rev=589afd500c26

This code is a bit tricky so please review carefully. ;)

Comment 8

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

Comment on attachment 8418987 [details] [diff] [review]
Use a separate linear scan pass to mark nodes white in ScanRoots.

I would rename ScanWhiteAndCheckNodes to ScanWhiteNodes.
The fact that it does some refcnt checks is a small-ish side effect.

Comment 9

[Andrew McCreight [:mccr8]]

(In reply to Olli Pettay [:smaug] from comment #8)
> I would rename ScanWhiteAndCheckNodes to ScanWhiteNodes.

Good point.

https://hg.mozilla.org/integration/mozilla-inbound/rev/2cc0d0171da6

Comment 10

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/2cc0d0171da6