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.

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.

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.

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.

The CC used to do this, then it was removed. Anyways, the CC graph is so tiny nowadays this probably doesn't help much.