Status on the Bug Collector

My last few weeks have been spent working on the DWARF-based root scanner for C and C++ which was proposed in a previous post.

Where have I come, and what I have I learned? 

MMTK today

The MMTK, a project typically associated with the Jikes RVM, is also used as part of the llvm-backed VMkit project. The goal of a common virtual machine framework seems very inspired by MMTK. It was a pleasant surprise to see that there is something to help prevent bitrot from getting to the project.

http://vmkit.llvm.org/publications/thesis.html

Polyhedral GC

Looking at polyhedral optimization at LLVM, I cannot but wonder if this might be used to optimize graph traversal in the marking phase of collection.

http://polly.llvm.org/publications/grosser-impact-2011.pdf

A Good Article about Realtime GC, from The GC Handbook

http://michaelrbernste.in/2013/06/03/real-time-garbage-collection-is-real.html

Migration from Conservative GC

https://blog.mozilla.org/javascript/2013/07/18/clawing-our-way-back-to-precision/

Sadly, conservative collection has a fatal flaw: GC things cannot move. If something moved, you would need to update all pointers to that thing — but the conservative scanner can only tell you what might be a pointer, not what definitely is a pointer. Your program might be using an integer whose value happens to look like a pointer to a GC thing that is being moved, and updating that “pointer” will corrupt the value. Or you might have a string whose ASCII or UTF8 encoded values happen to look like a pointer, and updating that pointer will rewrite the string into a devastating personal insult.

So why do we care? Well, being able to move objects is a prerequisite for many advanced memory management facilities such as compacting and generational garbage collection. These techniques can produce dramatic improvements in collection pause times, allocation performance, and memory usage. SpiderMonkey would really like to be able to make use of these techniques. Unfortunately, after years of working with a conservative collector, we have accumulated a large body of code both inside SpiderMonkey and in the Gecko embedding that assumes a conservative scanner: pointers to GC things are littered all over the stack, tucked away in foreign data structures (i.e., data structures not managed by the GC), used as keys in hashtables, tagged with metadata in their lower bits, etc.

Their solution?

Over a year ago, the SpiderMonkey team began an effort to claw our way back to an exact rooting scheme. The basic approach is to add a layer of indirection to all GC thing pointer uses: rather than passing around direct pointers to movable GC things, we pass around pointers to GC thing pointers (“double pointers”, as in JSObject**). These Handles, implemented with a C++ Handle<T> template type, introduce a small cost to accesses since we now have to dereference twice to get to the actual data rather than once. But it also means that we can update the GC thing pointers at will, and all subsequent accesses will go to the right place automatically.

This is an interesting solution to the consistency problem. It would in theory allow a realtime collector to race to copy live data, using some kind of compare-and-set. The problem with this in the context of a C/C++ conservative collector is that it changes the semantics of pointer dereferencing and the type of references returned by malloc. For a language with complete control of the collector usage, it's a nice vindication of the trite adage that "all problems in CS can be handled with another layer of indirection."

Cache locality would suffer, one might think, because the pointer to the indirection object may become quite far away from the data the object points to. Therefore every memory access requires fetching two different locations into the cache in the worst case.

If all references are stored in in a single place, different processors may contend to have the cache line holding all of the entries. This is false sharing, called so because the processors will fight to have memory addresses in their cache line that share bits with the data they actually want. They're sharing the cache line without actually sharing any addresses.

That said, the change was a step toward the runtime and collection optimizations that led to the team's recent massive performance increases and the reduction of the resident memory used by the firefox web browser.

Status Report for GC through Self-Introspection through DWARF

DWARF makes finding the functions executing based on the given program counter fairly painless. I was able to get a call stack, and figure out the variables inside the function and the associated types.

Actually getting the value of the pointers requires running a simple state machine. There are a few locations that a variable could be in, and all of the relevant ones require a degree of stack walking.

How I know that polishing dwarf-based location finding will take a while

http://www.dwarfstd.org/doc/040408.1.html

There are many ways that libdwarf can encode variable locations. In fact, it's an entire state machine. That said, C doesn't use most of them. After getting the basic parsing working, this will be something to return to and polish up.

Previous space optimizations of the BDW GC

http://www.cs.rice.edu/~javaplt/311/Readings/pldi93.pdf

- Conservative collectors have come in many shapes and sizes. Some track all pointers in heap while others are more conservative.

- Severe space leaks in conservative collectors have been noted in the past.

- Negative performance results associated with collectors likely due to space leakage and associated problems such as increased memory pressure and likelihood of thrashing.

- Removal of low-hanging fruit such as static values which point into heap area can lead to great improvements.

- Only paper(at time of this paper) analyzing pitfalls of conservative GC: http://dl.acm.org/citation.cfm?id=79028