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.
No comments:
Post a Comment