Closed Bug 666417 Opened 9 years ago Closed 6 years ago

generational purple buffer for the cycle collector


(Core :: XPCOM, defect)

Not set





(Reporter: mccr8, Unassigned)


(Blocks 1 open bug)


(Whiteboard: [Snappy:P3])


(1 file)

When an object is suspected by the cycle collector, it is traced in the very next cycle collection.  In Appendix A of "Efficient On-the-Fly Cycle Collection" by Paz et al, they mention a technique for "mature candidates" in the purple buffer.  Instead of tracing them all right away, the CC waits for objects to be left alone for a certain number of cycle collections before tracing from them.  Very active objects won't be traced, because they will keep getting bumped back to the youngest generation.  Objects that survive more than one CC, but less than the number it takes to mature, will be freed before the CC even has to look at them.

Implmenting this can potentially reduce the size of the collector graph, reducing memory usage, improving speed, etc.  The tradeoff is that it will take longer for cycles to be collected, but this tradeoff can be tuned.

The advantage of this approach in our setting is not entirely clear, because non-suspected roots (from JS and XPCOM, I think) may comprise a large percentage of total objects.

Anyways, it turns out it is easy to hack up an implementation of purple buffers, so I've done that.  That will at least let me explore the effect on the graph.
This is how my hacky implementation works:
1. add a generation field to nsPurpleBufferEntry
2. reset this field to 0 in incr and decr
3. when the CC scans the purple buffer, only add objects that have a generation > some threshold, and increment the generation for the rest.

This could be improved in a few ways (only really need a "dirty bit" in the purple buffer entries, and we need to compact the purple buffers), but it should have reasonable behavior for testing.

This patch won't actually apply, because it relies on another patch that adds some logging to the CC.  If anybody wants, I can upload that patch, too.
Blocks: 638299
So, this is my current 
Guess which one of these is a conventional CC and which one only adds nodes from the runtime?  (I elided shutdown CCs that clear out the purple buffers)

22090 nodes, 38651 edges
27257 nodes, 55616 edges
26853 nodes, 55243 edges
26117 nodes, 54546 edges
25896 nodes, 54302 edges
15661 nodes, 29865 edges

10565 nodes, 22348 edges
2137 nodes, 130610 edges
15607 nodes, 42001 edges
20087 nodes, 46586 edges
23278 nodes, 50691 edges

They basically look identical!  The second one is conventional, and the first one never visits any suspected nodes.  In fact, in this particular run, the conventional CC looks better for whatever random reason.  Kind of disturbing.  I should do a more detailed analysis of what the nodes in the graph are.  Maybe the workload I used (techcrunch + v8) is just dominated by JS, which won't be reduced by this approach.
Blocks: 698919
Whiteboard: [Snappy]
Andrew, can you snappy-prioritize this?
Assigning it P3 because the CC probably needs other work done to it before this will be particularly useful.
Whiteboard: [Snappy] → [Snappy:P3]
Comment on attachment 541204 [details] [diff] [review]
generational purple buffer

>+++ b/xpcom/glue/nsISupportsImpl.h
>@@ -120,16 +120,17 @@ struct nsPurpleBufferEntry {
>   union {
>     nsISupports *mObject;                 // when low bit unset
>     nsPurpleBufferEntry *mNextInFreeList; // when low bit set
>   };
>   // When an object is in the purple buffer, it replaces its reference
>   // count with a (tagged) pointer to this entry, so we store the
>   // reference count for it.
>   nsrefcnt mRefCnt;
>+  PRUint8 mGen;
> };
This takes quite a bit memory, no? There can be thousands, or even millions
purplebuffer entries.
(In reply to Olli Pettay [:smaug] from comment #5)
> This takes quite a bit memory, no? There can be thousands, or even millions
> purplebuffer entries.
My patch was really just a hack to see what the effect would be without changing much.  The "right" way to do it is probably to have multiple purple buffers.
No longer blocks: 698919
Blocks: 698919
The CC used to do this, then it was removed.  Anyways, the CC graph is so tiny nowadays this probably doesn't help much.
Closed: 6 years ago
Resolution: --- → WONTFIX
You need to log in before you can comment on or make changes to this bug.