If you are assuming GC does not need to stop the world, you can also assume that the freeing of memory (including the O(n) calls to free()) will not be done in a critical path; all memory could be handed off to a separate dedicated thread that actually calls free(). Or in a RPC or HTTP server all memory can be freed after the request has been served.
It's very easy to make a reference counting scheme not stop the world. It's a bit more difficult to make a GC implementation so.
> all memory could be handed off to a separate dedicated thread that actually calls free()
That only works when you have infinite memory (or infinite CPU resources).
> It's very easy to make a reference counting scheme not stop the world. It's a bit more difficult to make a GC implementation so.
Only if by "not stopping the world" you mean your previous suggestion (leaking unbounded amount of memory to free() everything at some later point). When your memory is bounded, you will eventually have to stop/crash once you have run out of it.
AFAIK, the best modern state of art garbage collectors have stop-the-world pauses, proportional to size of root set and/or thread count. I'd love to see an RC implementation, that does not have stop-the-world pauses at all, but that sounds as audacious as claims of perpetual motion machine.
I don't think the gp is describing the null garbage collector, rather one that can work incrementally and concurrently with the program doing its thing. Whereas a concurrent tracing gc has the problem of data changing while it runs and so special care has to be taken not to corrupt memory.
I don't think you understood my point. So let me give you a more concrete example.
The Linux kernel uses RCU to manage data structures that are concurrently read and updated. When an old value (after an update) is no longer needed, a thread can either:
Now, moving the concepts to user space, a typical user space implementation will just launch a dedicated thread to free all memory that is no longer needed by any RCU data structures.
> all memory could be handed off to a separate dedicated thread that actually calls free().
You could go a bit further and have multiple concurrent threads mark the references, then sweep them up in a separate thread, too. Some sort of concurrent sweep and mark reference count system.
With concurrency you need atomics or locks to synchronize reference counts between cores, unless you can somehow guarantee that ref counts only decrement and can never increment.
It's very easy to make a reference counting scheme not stop the world. It's a bit more difficult to make a GC implementation so.