Garbage collection thoughts
sebastiansylvan.com
sebastiansylvan.com
How would this work? Unless all values are immutable, this isn't generally true. If all values are immutable then you've got a pure functional language and a lot of these ideas don't apply any more.
Rust almost has this. Only shared (immutable) references can be obtained to values owned by a reference-counted pointer (which is nothing fancy -- just not implementing mutably dereferencing RCs). Since mutability is inherited, this freezes all reference counted data and everything it can reach.
However Rust also provides types which specifically can be mutated in a shared context (a Mutex being the most obvious case), so you can indeed make reference-counted cycles and leak.
Still, by default you can't leak. You have to opt into these "interior mutability" types.
Basically, "shared XOR mutable" does not necessitate forbidding mutability universally. It just requires a way to freeze data when it is shared. You can even unfreeze it whenever you can prove it isn't actually shared (e.g. reference count = 1).
But maybe that's just rationalization.
http://www.catb.org/jargon/html/koans.html (see "Moon instructs a student")
It stopped being considered proper garbage collection long ago because of the inability to collect circular references without help, which of course is the subject of that story. Apple is doing decently well with their version of it, but they're essentially reinventing ancient history.
Other GCs often have weak pointers too. You just use them less, because with a GC that can deal with circular references you don't need them nearly as often.
Garbage Collection is not very good with a C-language. C is simply the wrong language to be used with GC - same for Objective C. Personally I would also not use a 'conservative GC' in this context. Additionally GC has some overhead and it is not going away: memory usage, responsiveness, etc..
Apple would need to switch to a real higher-level language with managed memory and a precise GC.
GC, Swift and more RAM might have more chances.
What proponents of ARC miss, is that Apple gave up on GC because they didn't managed to make it work with Objective-C semantics, not due to merits of RC over GC.
Also Swift is also ARC based, because the goal is for a smooth integration with the Objective-C runtime, not due to merits of RC over GC.
I don't believe there's any algorithm in existence that requires circular references.
This isn't the point though. A general purpose programming language shouldn't impose arbitrary restrictions on data structures like this. Even if such a restriction was in place it would have to be enforced at runtime which doesn't sound like a trivial problem from a performance point of view.
But that's not really the question here. Any linked list is not an algorithm, it's a data structure.
The question is what operations can you do using circular references cannot be done without. I think otabdeveloper1 is right, because you can use a garbage collection type process to 'run' any other algorithm on a graph with cycles in it, using temporary lists and stacks to do whatever the algorithm would use circular references for.
The question is whether it's a reasonable constraint for real-world programs. In theory, Malbolge can be used to perform any algorithm, but few people would actually want to.
Circular references are really convenient in many cases. For example, view hierarchies typically have a pointer from a view back to its parent view. This means you can walk up the view hierarchy as well as down, so you can find sibling views, remove a view from its parent, invalidate a parent's layout when the view's sizing needs change, and stuff like that. Without circular references you could still accomplish all this, it just becomes slower and more painful.
In practice, reference cycles are a big problem for ARC. One of the most common questions I see with Objective-C and Swift programmers is when it's necessary to use a weak reference to self in a block, and when it's necessary to use a strong reference. It's difficult enough that I've seen a lot of people just punt on the entire question and go for "always capture self as a weak reference no matter what." Which works most of the time, and occasionally creates entertaining bugs. Even for experienced developers it's easy to miss a spot occasionally, and end up with a silent leak or a subtle bug.
Not really, no. There's no reason why the backlink should increment the reference count.
Realistically, circular references are only a deal-breaker for Lisps, and only due to some very specific design decisions of Lisp. E.g., circular references are never a problem in C++.
> A general purpose programming language shouldn't impose arbitrary restrictions on data structures like this.
Really? Why not? "We don't support refcounted circular references, please rewrite your code if you use them" is a perfectly valid design decision. Personally, I'd rather have that than some rube-goldberg type monstrocity of a memory management system just to support a very obscure corner case.
How so?
If the weak references are safe (as in, their pointer is assigned to 0 when the target object is collected) then I think there can be performance issues (compared to the competition of a tracing GC).
If the weak references aren't safe, then you have a data structure that's more in the realm of manual memory management, so it's hard to draw a fair comparison with fully memory-managed objects.
With an eager implementation, you need to ensure that deallocation and zeroing is atomic. The entire operation of decrement refcount -> deallocate -> zero weak references can't be interrupted by looking up a weak reference. In a multithreaded environment that means there's locking needed.
However, you can do a lazy implementation which doesn't suffer so much. Here, you keep a separate weak reference count in the object itself. When the normal reference count reaches zero, you deinitialize the object (decrement the refcount of anything it refers to, run custom deinitialization code if any), but leave the memory for the object itself intact. Then, upon accessing a weak reference, you can just check to see if the target is in this "zombie" state, and zero out the weak reference at that point. Once the weak reference count also reaches zero, the object memory can be deallocated.
Objective-C uses the eager approach for weak references, which is necessary because of compatibility concerns. Swift uses the lazy approach with native Swift objects, although it still has to use the eager approach for subclasses of Objective-C classes.
Assume you have an algorithm that does make use of circular references. Then, you could replace all pointers by integers. And you could put all referenced data into a large array.
That way you would have "broken up" all circular references. However, from another point of view, you could argue that your algorithm still makes use of circular references, they are just expressed differently.
(Also, now no garbage collector will help you cleaning up that thing, other than releasing that large array at once. So that's not really an improvement.)
Otherwise, you can avoid parent pointers by reversing pointers while you traverse, but this requires using a bit per node (which you can generally steal from a pointer in practice) to indicate whether a visited node was the left or right child of its parent. Getting rid of the extra bit is trickier, but it can be done, e.g. Robson traversal that uses the links of leaf nodes to store the stack.
A typical RC implementation suffers from either requiring to do AddRef/Release calls manually (what Apple had in pre-ARC era), or blindly doing too many automatic calls. That's ancient history and can not complete with a moderately decent modern GC.
ARC has neither of those disadvantages and so provides convincing alternative to GC, and AFAIK is the first and unique to do so.
BTW, the correct term to use here is "automatic memory management" (AMM), not garbage collection, and there is no such thing as "proper" AMM. Handling circular references is not a must-have property of AMM, it is just the price RC pays, in GC, that will be pauses and higher footprint, and other approaches exist too: for example, to disallow in compile time to create a structure that can be potentially circular.
pointer->ref_count += 1
obj = pointer->ptr
//...do something with obj...
pointer->ref_count -= 1
if pointer->ref_count == 0:
free(pointer->ptr)
What I'd like to know, though, is whether the `ref_count == 0` check could get optimised away as well. To you and me it's obvious that the count is positive at the start (as a precondition for the pointer access being correct), but I can't really see how an optimising compiler could know that.
I love what Apple has done with ARC: they've taken a very inefficient approach to garbage collection, one which has repeatedly shown to be the "worst case" algorithm with the worst performance characteristics, and then proceeded to convince legions of developers that that same approach is actually the best one.
There is a possibility that better whole-program optimization (potentially combined with annotations for function parameters) can reduce this overhead, but it's a bit of an unknown.
Also I'd expect that GCs should experience a slowdown in the contention scenario, due to write barriers; is it so?
In a concurrent card-marking write barrier you would generally set bytes rather than individual bits so that you can avoid the use of atomic instructions. You still have the problem of false sharing. If this were really a problem, you could emit a conditional write barrier that checks the existing value (with a racy unsynchronized load) before setting the byte.
The usual use of a write barrier for generational GC will produce fewer stores than automatic reference counting anyways, because a write barrier is only emitted for potential stores of a reference to a younger generation in an older generation. Automatic reference counting requires reference count adjustments for function parameters and local variables.
More like up to 20x slower; atomic reference counting has to hit the L3 cache at least. A quick benchmark seems to confirm that. Also, there are still some nasty corner cases with pointers that are shared between threads (because reading/writing a pointer and updating its associated reference count are not a single atomic operation).
> Also I'd expect that GCs should experience a slowdown in the contention scenario, due to write barriers; is it so?
Write barriers only come into play when pointers on the heap or in static memory are being modified. Reference counting means that you need to update the reference count whenever you assign references, even from one local variable to another (much of the work that Apple's done is to use compiler optimizations to get rid of those that are provably unnecessary). For example, having multiple threads traversing a tree in parallel can generate a lot of contention in the RC case, but none for a GC with a write barrier.
Deferred reference counting is closer in performance to GC, but then you have to write most of the machinery of a tracing GC, too.
The problem is that you only think you have such a thing. If you're wrong, you're screwed. :)
> The third and maybe most important optimization is to make garbage collection a per-thread operation. You simply don’t allow garbage collected heap allocations to transfer between threads.
This takes away much of the point of threads, leaving you better off with processes---and process boundaries will better enforce this model. You cannot cons up a message, pop it in a queue, and have another thread pick that object out the other end: thus you have to use some IPC based on bytes in a pipe or shared memory buffer.
In other words, you might as well fork a bunch of children that have not just their own heaps but their own address spaces to enforce the containment of those heaps. There is a lot of good in it: fault isolation, more virtual memory footprint to each little worker. There is a degree of attractiveness in multiple processes with just one thread in each one, and single-threaded garbage collection (which doesn't have to deal with hairy concurrency problems, and so is faster and more robust).
> To figure out which region a pointer refers to in this scheme, we simply loop through the different region sizes that our allocator allows, mask the appropriate number of bits from the pointer to get the start of the proposed region, read the region index in the first DWORD of this memory area (this may be garbage if we have the wrong size) use this to index into the region pointer array (taking care to avoid buffer overruns from garbage indices) and ensure that the pointer stored in that element refers right back to the proposed region. We also must ensure that the size of the region at this address actually contains the original pointer.
The problem of mapping a pointer to a region is already solved very well with existing data structures. For instanc, the Linux kernel uses a red-black tree to map a virtual memory pointer to a "struct vm_area". (These are the regions allocated by mmap). The regions don't overlap and so a binary search tree ordered by their base address works fine.
Solving the problem of "does this pointer refer to a heap, and which one" in a garbage collector is only necessary when we are doing conservative garbage collection: we are given some pointer-sized value from somewhere (like a scan of some raw memory area such as a C stack), and we have no idea whether or not the value is a pointer to an object in the GC world. An always-precisely-tracing garbage collector never has to solve this problem. It starts with root values, which are known to be objects in the GC world. If they are heap values, they point to objects whose structure is known to the collector. They are precisely traversed to reach other objects and so on.
Not really true; a lot depends on the implementation here. In a multi-threaded setup you can often avoid context switches and kernel calls (the really expensive part) and deep copying with a bump allocator is generally cheaper than deserializing/serializing [1]. Often, you can also avoid copying if you do it right.
On top of that, while you can't manipulate pointers on the heap safely under such a concurrency model, you can manipulate integers and floats across heaps (which is relevant for a large number of concurrent algorithms) if you do it right (i.e. by ensuring that you don't deallocate the objects containing the data).
[1] Keep also in mind that any actual shared data that goes from one thread to another will generally go through main memory or the L3 cache at one point or another.
Sadly the market choosed to ignore them.
Most of the market probably did not know about it, which is different from ignoring something.
ETHZ also created a spin off, Oberon microsystems, that sold BlackBox Component Builder, based on Component Pascal, an evolution of Oberon-2. Featuring a Delphi style IDE.
My conviction is that programming with GC requires a generation change and companies like Apple, Google and Microsoft pushing for them. As they are already doing on their OSes.
Sadly this is an area where FOSS doesn't seem to pick any steam, mostly likely due to the research effort that is required.
First, the main cost a GC -- any GC -- always has is significantly increased RAM overhead. Whether RAM is cheap (and can be traded off for things like throughput/latency or convenience) or not depends a lot on the environment. If RAM is expensive -- a GC is not the answer. If it isn't, it may well be the best answer. OTOH, GCs at least potentially have an advantage that's very hard to achieve by other means, which is compaction. Everything else is a tradeoff.
Second, I think the author jumps the gun when discussing various solutions (ownership, stack allocation, reference counting) without first trying to understand the problem, and the problem is -- first and foremost -- RAM overhead. Whether or not that's a serious problem really depends on the environment.
Also, before discussing solutions, we need to understand the domain. I think that the domain is as follows. Objects belong in one of four lifecycles:
1. Permanent -- objects live for the duration of the program
2. Stack -- objects live for the duration of a single function (and the functions it calls, of course)
3. Arbitrary -- objects live for an undetermined lifetime
4. Transaction -- objects live for a well-defined, time-bounded domain scope, be it a request in a web server, a frame in a game, or a transaction in a DB.
Now, in spite of what some may think, very little of a serious program's data can live on the stack. Server machines today come with hundreds of GBs of RAM, and if you do the math, only a very, very, small portion of that can be exploited by kernel-thread stacks. Lightweight threads require growable stacks and those stacks are therefore heap objects themselves, with either arbitrary or transaction lifetime. The cost of allocating stack-scoped objects on the heap is quite low, as those are very short-lived objects that don't become tenured by the GC, but allocating on the stack is better because we'd like to avoid triggering young-gen collections, too, of we can help it (and, indeed, Java is getting value types, although mostly for a different reason[1]).
With so much available RAM, the best use an application can make of it is to cache as large a working-set from the DB in RAM. Those objects have an arbitrary lifetime and often require scalable concurrent access (or sharding, but that opens a whole new can of worms). Reference counting is not a good solution here.
Finally, transaction-scoped objects are best handled by arenas. GCs, like HotSpot's G1 can attempt to automatically determine those transaction-scoped objects, but the results are not as good. This is a tradeoff: a global GCs simplicity, vs. arenas' utility and low latency.
Personally, I think that the solution first depends on whether or not you're targeting high-performance in constrained environments (like C/C++ and Rust do). If so, a solution like ref-couting is a great one. If not, I see no room whatsoever for ref-counting (what scope do they target, and what advantage do they have over a GC in an unconstrained environment?)
In unconstrained environments I think the best approach is as follows:
1. Stack allocation (value objects) where possible.
2. A global GC for the arbitrary and permanent scope (no need to separate permanent objects as they place a relatively low burden on a GC).
3. Arenas for transaction scopes, if you're willing to sacrifice some simplicity for latency.
I don't see absolute necessity for ownership types (and certainly not reference counting) in such unconstrained environments, but they may certainly be useful in statically verifying that heap objects never reference an arena object (or arenas with wider scopes never reference shorter-lived arenas).
In constrained environments where manual memory management is required because the GC's RAM overhead is onerous, ownership types are invaluable, as is reference counting. You don't get compaction, but this may not matter as such applications are usually much more careful with managing their allocations and deallocations.
RTSJ -- Java for hard-realtime and safety-critical systems (which is getting a new spec these days) -- makes the simplicity tradeoff, and introduces arenas (scoped memory): https://www.aicas.com/cms/en/rtsj It also makes permanent objects explicit, because it can't tolerate any additional cost, even if it mostly limited to program startup.
Finally, the author mentions both immutability and large objects, but the two are often at odds. Persistent data structures that are popular in immutable-by-default languages like Clojure rely on small object with lots of pointers to reduce memory and performance costs.
[1]: Cache friendliness of arrays and other data structures.
Then again, my first interview question is "what's wrong with garbage collection?" and if you can't give me three specific use cases where it's a non-starter then that's usually the end of the loop.
Language is an imprecise tool and interpretation is fluid. Why pick the least charitable interpretation by default?
If it makes you feel any better, in the early 90s the question was "what's wrong with malloc?" And I'm sure you'd do just fine. Amazing how many people don't, though. Better predictor of success than any of this "walk a tree" nonsense and no whiteboard required.
Indeed, it is better to have a more general discussion about the foundations one is to work on, then to solve random riddles.