A garbage collector that knows that all values are immutable will be rather interesting, I think. Typically, a garbage collector will stop the world (i.e. halt execution) to do heap defragmentation of the old generation. When all values are immutable, though, you can defragment the heap by copying a value to another fragment and just swap the internal pointer to the value.
This might actually have significant performance benefits. When everything is immutable, GC can also be inherently incremental. You just do your defrag copy faster than new object creation. Then you cam limit your stop-the-world to a small "catch-up" so your copy-from can become a copy-to. Incremental GC nirvana!
I don't see how immutability makes much difference to garbage collection. Garbage collectors don't look at the value inside memory they are collecting, only whether something live is still retaining that part of memory. Whether the value is mutable or immutable has absolutely no bearing on the performance or logic of the GC. Either something is still using the memory, or it is free to collect.
Also you've just described existing GC systems - The Java G1 collector is very similar that (it's a lot more complicated though).
Generational GC usually depends on write barriers to detect creation of references to newer generations inside older generations.
Immutability prevents the mutation of older generations, so no new references can occur.
So I expect generational GC to be easier to implement. I wouldn't expect it to be faster or slower though, because programs will need to be written differently to cope with the limitations on mutability. O(1) algorithms will likely be replaced by O(log(n)).
The actual GC of freeing memory is indeed possible (and common) without stop the world. Heap defrag is another story, though. This involves moving objects to different locations in memory, and if the memory is mutable, measures like stop the world is required since multi-byte move is not atomic.
Doesn't matter. In an immutable model, the old copy is guaranteed not to change, so you can safely copy it non-atomically. (That's one of the big benefits of immutability.)
> This might actually have significant performance benefits.
Not really. On the other hand, it makes the implementation of GCs much simpler.
(immutability semantics also tends to make memory churn much higher, so what little gain you get from a simpler implementation is often lost in the GC having to do more work)
Also, it's not like these things are unstudied FFS.
It's not just GC, but virtually pause-less GC that is the possible benefit. Yes, these things are studied, but I would challenge you to find a free high level language implementation with GC suitable for soft real time. Right now, I know of Erlang, which isn't the fastest language and running Clojure on the proprietary Azul VM.
I'm not sure what you're trying to say. If no such implementation exists, even though there are a number of languages predicated upon immutability, one would conclude "virtually pause-less GC" isn't such an obvious or easy "possible benefit" of immutable structures.
Unless you're using refcounting: since immutable structures can't create cycles, a refcounting GC won't need a cycle-breaker, and thus won't need to ever pause. But you'll be using throughput (especially for allocation I'd guess).
Also not sure what your point is re. Azul, immutability is not what enables it since Zing is first and foremost a java VM.
I was thinking about refcounting, actually, but not exclusively. My point is that there aren't that many systems where you can build in a high level language, deal elegantly with concurrency, but still have really good latency guarantees. This project might improve on that.
I don't get if you imply that Clojure has pervasive laziness or not. The contract of lazy sequences is too loose to make tying the knot not a brittle hack -- and I think it's a good thing.
"When all values are immutable, though, you can defragment the heap by copying a value to another fragment and just swap the internal pointer to the value."
Wouldn't that turn shared objects into not-shared objects? Theoretically, that doesn't make a difference in a system without mutable data (assuming you leave out 'identity check', too), but in practice, it likely will blow up memory usage tremendously.
Edit: I think the way around this is to replace the moved object with a "this object moved" object. The trick, then, will be to know when it is OK to discard that "this object moved" object. That probably is the case after a full heap scan.
Agreed. The potion/QISH implementation of the two-finger cheney loop is extremely efficient even without register values (volatile), typically 3ms pause time on a mid-sized heap. Compare that to typical java or ruby pause times, starting from 25ms to typically 150-250ms. You need more memory though, as in most lisps it's using copying, i.e. compacting, not just simple mark&sweep. Incremental is doable, but you need to add GC state then, which is a bit tricky in threads. Actually libgc is pretty good.
This might actually have significant performance benefits. When everything is immutable, GC can also be inherently incremental. You just do your defrag copy faster than new object creation. Then you cam limit your stop-the-world to a small "catch-up" so your copy-from can become a copy-to. Incremental GC nirvana!