Garbage Collectors Are Scary

You have to instigate a GC torture test as part of your testing, combined with a way of detecting use-after-free. (An obvious way is to reset the type of freed objects, so any use of such an object runs into type mismatches.)

A GC torture tests causes the collection routine to be called often, like after every allocation. If an object is allocated, and now held only in an unspilled register, and then another object is allocated; that first object will be wrongly freed. This is what we want: reproduce the problem, and then hopefully detect it.

If you're garbage collecting underneath a compiler that doesn't know about garbage collection, you have to worry about not only values held in registers not being spilled, but values that are optimized away entirely, which your garbage collector has to see.

For instance:

  obj foo_create(obj param)
  {
     struct foo_object *foo = malloc(sizeof *fo);
     foo->bar_attribute = param;
     return create_heap_object(foo_type, foo);
  }

Let's assume our garbage collector is conservative only w.r.t. stack scanning. Heap objects are traced precisely. We are not scanning every malloc object in existence, in other words, and so, the bar_attribute is not visible to the garbage collector.

Once we call create_heap_object(foo_type, foo), the foo_object structure becomes hooked up to a garbage-collected heap object, and then it is visible to the garbage collector. The foo_type has garbage collector hooks for traversing the "struct foo_object".

Problem is, create_heap_object calls into the garbage collection module to allocate a new heap object, and that can trigger GC. When GC runs, it can wrongly collect the param object.

This can happen if the function has a caller which itself has let go of the param object, like:

  obj caller(obj cparam)
  {
     obj tparam = transform_somehow(cparam);
     obj foo = foo_create(tparam); 
     return foo;
  }

Great lad to work with as well, open minded to various angles and whole stack from browser experience to deployment.

Reference counting is a lot more complicated! It turns every read into a write.

> [...] if my goal is performance and predictable latency?

Reference counters don't have predictable latency: a single reference decrement can lead to an arbitrary amount of follow up work, like more decrements and deallocations.

Performance of reference counting isn't generally better than that of garbage collectors. (Especially since you still need a backup solution to deal with cycles.)

Figuring out a lot of your memory management at compile time is definitely a win. But doesn't really have much to do with reference counting.

Problems with refcounting:

1. You leak cycles. Given the point of a memory management scheme is to reliably not leak, this is a major weakness. Cycles are very common and natural things to find in heaps, and even if you avoid them they can easily be introduced years later by people you will never meet who weren't aware of the entire heap topology. You say you'd just "forbid cyclic references": how will you do that? Require everything to be written in Rust?

2. Every object gets bigger, as it must store a reference. This increases memory usage and reduces locality. With a GC it's possible to squeeze the overhead down to a vtable pointer (required anyway in most cases) and then a few bits on top!

3. All the incs/decs bloat your code, creating a form of pervasive slowness that doesn't show up in profilers except in hot loops. This tempts you to micro-optimize add/decrefs, but that increases the chance of mistakes.

4. Requires a very consistent protocol for how and when references are taken and released. The details here can get complicated. For example do containers add/decref for you, or do they expect you to do that?

5. You are exposed to use-after-free bugs, which are a major source of security holes.

There are probably more. And obviously the restriction to not use threads is catastrophic for any system that cares about performance.

The problem with having the ability to hold managed pointers from kernel<->userspace (whether using rc or gc) is that a process might be malicious or arbitrarily buggy, in the standard OS model. It means you have to be able to kill the process and release all its resources, which means the kernel must know where all the references to kernel-side objects are coming from so they can be removed on kill.

To allow object graphs to span the user/kernel space boundary therefore requires the kernel to mandate the use of a specific compiler that's a part of the TCB (i.e. a part of the kernel itself). That radically changes the design of the whole OS. In particular you cannot implement a UNIX that way.

Additionally, data can be borrowed from inside the refcounted wrapper, and used freely within a scope without touching the reference count.

If you want predictable, you want your GC to run either in constant time slice, or an upper-bounded timeslice.

Deferred refcounts can become quite complex if you want to avoid "I have just released last reference to something that contained a lot of other referenced" (there are some funny threads where Rust users discover that they sometimes need to spin an extra thread to not have effective "stop the world" XD).

So instead common approach is tracing GC with some form timesliced running collector, guaranteeing that time taken from mutator will be upper-bounded. For example, instead of stopping the world, concurrent GC will usually only require a synchronization point. Sometimes it also means that the collector will be given explicit timeslice to ensure that there's certain amount of work being done - it's all tradeoffs based on how much throughput and latency you want.

You can speed up tracing collectors through things like escape analysis and 1bit reference counting (for example, you set a bit if a new reference is passed outside of current scope, every object without bit set can be assumed to have all referenced contained in given scope, etc).

You can elide some of them using a sort of borrow analysis. But borrowed refs can only be used in certain ways, and so this analysis isn't perfect and can't eliminate all of the unnecessary overhead. This was all hashed out in the 80s and 90s IIRC, before multithreading even became a big issue.

The complex analyses needed to make RC perform well end up destroying the simplicity argument, and even after they still aren't competitive with tracing.