Introducing Riptide: WebKit's Retreating Wavefront Concurrent Garbage Collector
webkit.org
webkit.org
A few amusing parts of this post that stood out to me:
* A single sentence containing half a dozen links to Filip's previous work on garbage collection.
* "See here for the proof", linking to a 200+ line comment in WebKit's source.
* "But since this is JavaScript, we get to have a lot more fun".
Still this looks to be some impressive work and I did enjoy this post.
I don't give a crap if a computer can read my proof.
https://www.quantamagazine.org/20130222-in-computers-we-trus...
It and others I've read on machine-checked proof showed the computer-centric one could catch quite a few problems with higher assurance of correctness. The peer review problem in science also makes me think it's important given I can't be sure the huge proofs will be adequately checked. Far as reliability on computer end, I've read on verified processors, proof assistants, compilers, and so on. Much of the risk can be knocked out but the black box that is human brains is another story.
I think you're getting it all mixed up!
Some accounting only needs to happen when visiting the
object for the first time. The complete barrier is simply:
object->field = newValue;
if (object->cellState == Old)
remember(object);
Or perhaps it is relying on the calling mutator thread necessarily holding a reference to the young object in question? Even then there is some non-trivial ordering work to be done here (in particular on weakly ordered architectures.)
I'm sure this is well handled but as this is one of the main difficulties in implementing good write barriers I am curious what they did.
However, the riptide barrier description still isn't 100% clear how it avoids terminating a sweep (I believe "drain" in your termination) in the middle of a barrier execution; in particular I'm not concerned about the data race between the field write and the mark bit, but the GC reading mark bits, believing the drain has terminated, and freeing memory while a mutator thread has written a field but not written the mark bit.
Are you just relying on the stop-the-world behavior relative to roots that you mention briefly?
Flip = term of art for when the GC terminates and decides which objects are free.
On another note, Webkit seems to be following a much more open manner, and has shift to working more towards Web App optimization rather then Web Pages.
V8 has some details about their GC (garbage collector) here[0]; ChakraCore here[1]; SpiderMonkey here[2].
Now, they are all generational, incremental and concurrent, but each with particular tweaks.
The approach detailed in this blog post is similar to one taken in ChakraCore, except it sets barriers on fixed-size blocks of memory, while Riptide uses objects.
[0]: http://v8project.blogspot.fr/2015/08/getting-garbage-collect...
[1]: https://github.com/Microsoft/ChakraCore/wiki/Architecture-Ov...
[2]: https://developer.mozilla.org/en-US/docs/Mozilla/Projects/Sp...
In principle the downsides compared to compacting collectors is reduced cache locality, fragmentation, somewhat higher allocation overhead and higher memory footprint.
On the other hand it is a lot easier to implement concurrent collectors when objects are not moved.
> The changes that transformed WebKit’s collector were landed over the past six months, starting with the painful work of removing WebKit’s previous use of copying.
It is curious that mozilla chose the opposite, doing the painful work of turning a conservative, non-moving collector into a precise, compacting one.
In actuality the downside of not copying is:
- Your allocator has to be tuned to resemble first-fit in its allocation order. This is empirically enough to control memory usage.
- You better have more virtual address space than physical address space. This means that the Robson bound for memory usage goes from M log M to M log P where M is memory size, P is page size, and log M or log P is the fragmentation wastage multiplier. People needed compaction really badly back when the state-of-the-art GCs ran on maxed-out 32-bit address spaces.
- Mark-sweep collectors have to sweep, copying collectors don't have to. But this is a fixable problem. Sweeping can be made concurrent, parallel, incremental, or very cheap. We pick the very cheap, by using bump'n'pop.
Initially we had some regressions from removing copying, but we fixed them by making sure that the first and third mitigation listed above were in place. WebKit rarely runs on a maxed-out 32-bit address space.
Do I understand correctly that the hard work was done, and this is a regression?
Riptide removes the copying because concurrent or event incremental copying is sure to introduce overhead. Are a minimum you either need a barrier on all pointer reads from the heap or all writes to the heap, and none of those barriers resemble our old generational barrier so this would be new overhead. Riptide only barriers writes of pointers to the heap, and uses a single unified barrier for both concurrency and generations to get maximum throughput. Riptide's concurrency actually improves end-to-end execution time because the overhead of the concurrency is negligible so you just get to enjoy the benefit of continuing to run while the GC runs, so you run faster overall. The speed-up was like 5% on the splay test, and I measured speed-ups in other things I cared about, like page load times.
You can also run the benchmark in Safari Technology Preview 21 and compare it to what you see in the other browsers.
"Riptide is an improvement to WebKit’s collector and retains most of the things that made the old algorithm great. The changes that transformed WebKit’s collector were landed over the past six months, starting with the painful work of removing WebKit’s previous use of copying. Riptide combines Guy Steele’s classic retreating wavefront write barrier with a mature sticky-mark-sweep collector and lots of concurrency tricks to get a useful combination of high GC throughput and low GC latency."
It's a term we use in our code to refer to that depth-first search.