It was demonstrated in the mid 80s that the MMU could be used to implement the write barrier (when I saw that I knew lisp machines were a dead end, though I kept using them for as long as was feasible). You can use this and other compiler support to implement it in a language not designed for GC support, no problem.
The issue I think you meant is that you can’t have a transporting collector (which also compacts your working set, even allowing you to return memory to the system). A language like C++ doesn’t anticipate an object’s address ever changing, so that’s a no go.
I suppose you could write special shared_ptr / unique_ptr that supported address mutation but you’d need a compiler flag to check for an object’s address being taken… but to some degree the destructor paradigm renders a lot of this moot.
Yes, that's why I wrote about support "on the compiler or hardware side" (i.e. MMUs). That said, while this might work in theory, the BDW GC does have support for it, and in practice it doesn't actually work well. Throughput suffers and pause times can actually get worse.
By the way, another alternative way of having incremental collection without compiler support is to use fork() for snapshotting (there's an option in D for that), but that has its own issues, of course.
> The issue I think you meant is that you can’t have a transporting collector (which also compacts your working set, even allowing you to return memory to the system). A language like C++ doesn’t anticipate an object’s address ever changing, so that’s a no go.
No, I wasn't talking about a compacting collector. I very specifically meant generational and/or incremental collection.
FWIW they are orthogonal
I don't know what your domain is, but the domains I'm familiar with (especially hard real-time) deal with the underlying constraints by way of restricting how you write programs. A side effect of these restrictions is that you generally avoid use constructs that give rise to cascading deletes. But ultimately, having to deal with these restrictions is suboptimal.
I remember a talk by Gil Tene (CTO and co-founder of Azul Systems) about how the problem with writing real-time Java was that it historically required you to write non-idiomatic Java code, which came at a serious cost to reuse and where he argued that one of the benefits of Azul's GC was that you could write (mostly) idiomatic Java and still have GC noise be less than OS noise.
There is of course the actual problem that the stricter your latency requirements are, the fewer GCs actually meet them. Plenty of modern off the shelf GCs meet typical soft real time requirements, but the harder your real time requirements get, the fewer implementations actually meet them (and are increasingly more expensive).
I'll also add that depending on how strict your latency requirements are, off the shelf allocators may not meet them, either, even for a single malloc() (though there are allocators that offer hard upper bounds for allocation costs, such as TLSF).
iain
Cascading deletes are rare in practice, and if anything they are inherent to deterministic deletion, which is often a desirable property. When they're possible, one can often use arena allocation to avoid the issue altogether since arenas are managed as a single allocation.
This is true, but it's absent especially in C. Of course, as long as you can intercept writes and/or reads through pointers, you are good to go in principle. However, that solution may not be efficient.
> Cascading deletes are rare in practice
An array of objects (e.g. std::vector<std::string>) already has unbounded deallocation cost. People mostly think of tree-like structures here, but such structures only add the risk of stack blowout to the lack of an upper bound. But in principle, any container that does not have a size limit can give rise to unbounded pause times.
The above problem is about latency of stop the world collectors in a domain that requires extremely low latency. And if you think that stop the world collections are representative of garbage collection as a whole (i.e. the "bad rap"), this is just not being up to the state of the art. (It's just that generational/incremental collection is hard to impossible without having support for write barriers/read barriers/snapshotting on the compiler or hardware side, which makes that a practical no-go for a language that was never designed to have GC support.)
But in terms of throughput, the BDW GC actually performs pretty well, competitive with or beating malloc()/free() libraries. This is plenty enough for a number of applications, especially when it comes to batch processing. In fact, even the stop the world latency is (combined with parallel marking) plenty good enough for a number of types of regular GUI applications, where you don't have the fairly extreme latency requirements of standard video games.
It is also worth noting that manual deallocation (especially via RAII) isn't a panacea for latency, as that is just as prone to large pauses due to cascading deletes [1].
[1] While in theory you can do that lazily, in this case you're losing timeliness of deletion and may actually have worse worst case latency than a modern GC that can stagger its work to have bounded pause times. The benefit of RAII is that you may be able to plan these deletions, but even that can be surprisingly difficult at times, requiring extra management to keep data structures alive longer than normal. [2]
[2] Note that lazily deleting objects in RC to avoid pause times is not necessarily the answer; for one thing, you're introducing much of the complexity associated with incremental GC again (especially having to do X amount of deallocation work for each allocation), or risking considerable space overhead. https://dl.acm.org/doi/abs/10.1145/964001.964019 It also remains a difficult challenge when you're dealing with objects that aren't of bounded size (e.g. large arrays).