671661 - don't always scan all nodes in CollectWhite() in the cycle collector

Status: RESOLVED WONTFIX

(Core :: XPCOM, defect)

Description

[Andrew McCreight [:mccr8]]

CollectWhite() iterates over all nodes to find white nodes.  CC telemetry (live in Nightly) says that 57% of the time, we have no white nodes at all.  Obviously, it would be better to reduce that number, but we can pretty easily improve the current case a little bit by returning right away from CollectWhite() if there are no white nodes.  This requires trusting the white node count, because right now it can be totally wrong and we'd still collect everything the CC marked white.

A refinement of this would be to bail out of the node scanning loop when we've found all of the nodes we expect to find.  In some sense, this subsumes just returning immediately, though technically we'll have to do a few extra compares.

Comment 1

[Andrew McCreight [:mccr8]]

Attachment: stop scanning nodes when we've found all white nodes

This is what I was thinking.  It just stops iterating over the nodes when we've found everything.  It adds an assertion that checks that we found everything we expected to.  Completely untested patch.

Comment 2

[Andrew McCreight [:mccr8]]

Of course, the assertion only catches when the white node count is too high, not when it is too low.  In debug mode, we could have a second loop that examines all objects (or just the rest of the objects) to see if any white nodes remain.

Comment 3

[Andrew McCreight [:mccr8]]

Some fun stats:
looked:  2332, other:  1153
looked:   106, other:  5096
looked:    20, other: 27598
looked:   171, other:  9159
looked:    37, other:  5704
looked: 92031, other:     0
looked:     2, other:    45
looked:     0, other:    89

This is from opening the browser and hitting tech crunch and a few other random sites.  "looked" is the number of nodes we had to scan before we found all of the expected white nodes.  "other" is the number of remaining nodes, that we could skip, but currently don't.  Mostly it saves quite a few nodes, but in the third from last CC, it didn't save any!  That's probably the first shutdown CC, though, given how huge it is.

The tradeoff here is between doing an extra branch each iteration of the loop, and saving some time in the loop.  The loop itself is pretty simple.  It just scans along an array of 5ish word objects, looking for objects that have a particular field set to a fixed value.

For this tiny sample, it seems to really pay off, ignoring that huge CC, but it is hard to say offhand how well it will work in general.

Comment 4

[Andrew McCreight [:mccr8]]

Oops, that's not right at all.  "looked" was really the number of white nodes found, not the number of nodes examined to find the nodes.

Here's a more correct chart.  Found is the number of white nodes, examined is the number of nodes it looked at to find those nodes, other is the number of nodes it managed to skip.  The giant streaks of 0 found is the result of me hitting "minimize memory usage" twice, I think.

found:  2449, examined: 84047, other:  1171
found:   147, examined: 55379, other:  2300
found:    11, examined: 14517, other: 62895
found:     0, examined:     0, other: 71674
found:     0, examined:     0, other: 76691
found:     0, examined:     0, other: 54812
found:    16, examined: 62172, other: 14934
found:     0, examined:     0, other: 76722
found:     0, examined:     0, other: 76676
found:     0, examined:     0, other: 56848
found:   122, examined: 57041, other:  2754
found:   198, examined: 19795, other:  9675
found: 16164, examined: 72208, other:    12
found:    24, examined: 13070, other:  7733
found:    66, examined: 53889, other:   826
found:  1442, examined: 50994, other: 12010
found: 159404, examined: 159525, other:     0
found:     6, examined:    51, other:    45
found:     0, examined:     0, other:    89

This picture is not nearly as rosy, and is more in line with what I'd expect.

Comment 5

[Andrew McCreight [:mccr8]]

Attachment: return immediately from CollectWhite if there are no white nodes

Fix the common case without adding any real overhead to larger CCs.  I guess we really care more about speeding up large CCs than small CCs (to improve responsiveness), so we shouldn't improve the latter at the cost of the former!

Comment 6

[Andrew McCreight [:mccr8]]

CollectWhite seems to take almost no time except when we're actually freeing things, so it probably isn't worth bothering with this.