An interesting approach: giving each thread its own "young generation" sub-heap, so transient objects can be disposed of without coordination from other threads / CPUs and their cache pages.
We've been doing this in Manticore since 2008 or so. We couldn't really get speedups past 12 cores without it (we have a "typical" parallel GC implemented as well to test against). Hopefully we'll get the paper on the GC and associated language trickery - we don't allow pointers between young generations - in somewhere soon :)
Yes, the GHC design has certainly been influenced by Manticore (that was one of the "other designs" I referred to). Though in GHC we do have some different problems to solve, the worst of which is that we have to support a bunch of programming abstractions that use mutation.
Cool, the steamflow thing sounds interesting. Is there a top level example or test-driver somewhere in the github project showing what typical use-cases are?
The Larson and Recycle benchmarks are on github. You can read about them in the paper. Email me if you'd like to see an unpublished paper which has some more detail on the allocator's design.
Ah Haskell, the more I read about you the more impressed, curious, and scared I am. This is interesting and I wonder if things will start moving towards this approach as we near the scalability issues of 8-16 core laptops, desktops, and server architectures.
It looks at first glance like, while there are fewer periods where the whole system is stopped, those periods are substantially longer. Why would this be the case? Was the "old" generation previously being collected every time?
The pause is still very short; it doesn't look like it will cause problems for anything but the most time-critical software. Still, it's an interesting difference.
We still have lots of tuning to do, I'll be looking in detail at what is going on during those pauses. This program is slightly atypical in doing quite a lot of old-generation collections though (you can see two in the graph), it has a low infant mortality and might benefit from a larger nursery size. (don't you love GC analogies? :)
Interesting. So that's why "there are other, less picturesque examples that improve more."
Out of curiosity, does the GHC GC take advantage of the property that most data is immutable? Is it mutable from the perspective of the GC? I could easily see GHC playing with that constraint internally. Pure curiosity is at play here: I've never heard of a garbage collection scheme that takes advantage of immutability, but logically it seems like it should be possible.
GHC has a comparatively expensive write barrier. That could be seen as taking advantage of immutability. The runtime system takes more advantage of purity, though. For example, it's safe to have certain races, because they will give the same result. Too much work duplication must be avoided, though, but that's much cheaper than excessive locking.
Oh yes, immutability is crucial. Generational GC already makes you pay for mutation with a write barrier, and in our parallel GC we omit the locking when copying immutable objects, accepting that a few might get copied twice. In the new GC mutable objects become even more expensive. I don't think local GC is viable at all in a language with ubiquitous mutation.
15 comments
[ 4.5 ms ] story [ 28.2 ms ] threadA group at Intel independently came up with a similar approach as well: http://portal.acm.org/citation.cfm?id=1133967
E.g. - I have a test-driver here: http://github.com/roboprog/buzzard/blob/master/test/src/main... (although I have barely started the library I was tinkering on)
Any example client program for your allocator? I'd like to see what use cases you are handling.
The pause is still very short; it doesn't look like it will cause problems for anything but the most time-critical software. Still, it's an interesting difference.
Out of curiosity, does the GHC GC take advantage of the property that most data is immutable? Is it mutable from the perspective of the GC? I could easily see GHC playing with that constraint internally. Pure curiosity is at play here: I've never heard of a garbage collection scheme that takes advantage of immutability, but logically it seems like it should be possible.