Javascript:SpiderMonkey:ProjectGenerationGarbageCollection

Wiki conversion of original Google Document: https://docs.google.com/a/jamsni.com/document/d/1-GZ8F0ZabvdpCnRQaecId0yuu4QFYr5pAvnRC_KFchc/edit

Objective

Implement Generational Garbage collection in Spider Monkey. <Some goal based off V8 performance delta % on Earley Boyer benchmark>

Accountable: Naveed
Responsible: Terrence, Steve, Jon, Nicholas, evilpie and Ms2ger
Consulted: bhackett billm
Informed: Product Marketing

Tracking Bug: [meta] Implement generational garbage collection - bug 619558

Milestones

Status	Milestone	Task	Deliverable	Assigned	Estimate	Due Date
pending	1	Rooting analysis in the shell	green on mozilla-inbound	sfink, jonco, evilpie, Ms2ger	2 weeks	2013-03-07
in progress	2	Exactly rooted shell	green on mozilla-inbound	sfink, jonco, evilpie, Ms2ger	2 weeks	2013-03-14
not started	3	Rooting analysis in the browser	green on mozilla-inbound	sfink, jonco, evilpie, Ms2ger, terrence	2 - 3 months	2013-06-01
not started	4	Exactly rooted browser	green on mozilla-inbound	sfink, jonco, evilpie, Ms2ger, terrence	2 - 4 month	2013-07-01
in progress	5	GGC no-jit shell only build on TBPL	green on mozilla-inbound	terrence	1 month	2013-02-21
not started	6	JIT support	Ion+GGC displayed on AWFY	bhackett	1 - 2 months	2013-05-01
not started	7	Optimized GGC in shell	Ion+GGC faster than Ion-GGC on AWFY	bhackett	2 - 3 months	2013-06-01
not started	8	GGC in the browser	green on AWFY	terrence	3 - 4 months	2013-10-01

Steps

Exact Rooting done in JS Shell bug 753203

12 weeks started

• Rooting Analysis on TinderBox (sfink) - done
  • Still need to unhide it for inbound - get it green, keep it green
• Get the root analysis build green - two weeks?
  • Get jit-tests green bug 745742
  • Get js ref tests green
  • Get jsapi-tests green bug 831376
• Rooting analysis fuzz bugs bug 773746
  • Rely on static analysis to make this not be a whack-a-mole game
• Remove E4X - done
• Do something about JSD
• Add exact roots to stack structures - 2 weeks
• AddRoot/RemoveRoot for Heap structures - 4 weeks
• Static code analysis bug 831409
  • Fix all discovered rooting hazards (~800) (sfink,jonco) - 4 weeks
  • Optimize all discovered over-rooting (~100)
  • Automate static analysis bug 834912 (sfink)
    • Need a server (dm-sixgill01?)
    • http://people.mozilla.org/~sfink/data/rootingHazards.txt
    • http://people.mozilla.org/~sfink/data/gcFunctions.txt
    • http://people.mozilla.org/~sfink/data/allFunctions.txt

JIT Integration with post barriers - 4 weeks, parallelized

• IonMonkey bug 831506 - 1 week (bhackett)
• JaegerMonkey bug 764876 - 2 days (bhackett)
• Baseline JIT bug 831507 - <ask jandem/djvj for an estimate>

Generational Garbage Collection in the Shell

• Implement prototype algorithm (terrence) - 1 week
• This is a potential milestone: we would need to build it and test it on TBPL similar to how |r| works now -- |GGCJS|.
• Re-implement HashTable rekeying
  • We undid this code because it was a perf regression and was still a bit buggy. (terrence) - 3 weeks
  • at least part of this is bug 726687

Exactly Root the Browser bug 831379 - 10 weeks

• This is a potential milestone: we would turn on exact rooting for release FF at this point. We would not get a performance boost from this (necessarily), but it would lock in our work to this point.

Performance Tuning - 4 weeks (This should probably start asap)

• Implement a Nursery bug 706885 - 1 week
• Test against V8 Earley-Boyer benchmark.
  • Also v8 deltablue, raytrace
• We may need to Implement Bill’s Pools/Zones idea to get the nursery to the requisite perf bug 759585 - 6 weeks
• Refactor code to avoid rooting on hot paths and keep rooter overhead acceptable bug 831886 (bhackett) - done

Make the Post Barrier Verifier Green in the browser bug 764882

• Investigate how long it will take to do generational barriers - 1 week
• We may need to rewrite the maps in xpconnect and the browser in terms of HashTable: this could be a bunch of work.
• Make JS_IsAboutToBeFinalized indirect bug 765432 - 10 weeks

Other

• Should we establish a new benchmark specifically for GGC. (sfink votes yes)
  • What would it measure? there are multiple goals, e.g. throughput/MMU/pause time
  • Should we make it a public benchmark?
  • What workloads should we consider?
  • compartmental GC very important to us, not necessarily applicable to other implementations
  • allocation rate (broken down into live vs garbage), steady behavior vs swapping between allocation + computation modes, etc.

• How can we keep our advantage on Splay benchmark
  • possible to do with TI --- look at types of objects promoted from nursery to major heap, eventually start allocating them directly in the major heap

• Compacting GC - Revisit in Febuary/March - 1 Month
  • Delayed until exact rooting is fully done. We can add this in if we have time in the schedule that we cannot parallelize.

Risks

• Team is responsible for many top crashers
• External rooting API has not been designed
• GGC algorithm has not been decided on - it may not be faster
• JSD1 exact rooting is lurking

Parallelizable Sub-tasks

• Exactly rooting the browser.
• Milestone 1 - 4
• evilpie, jonco, Ms2ger, sfink
• 2 - 3 months
• JIT integration and optimization.
• Milestone 6 - 7
• bhackett
• 1 - 2 months
• Preparing the browser to GGC.
• No Milestone - Postbarrier verifier too slow for TBPL
• terrence
• 2 - 3 months