3 ms·

People recommend tracing garbage collection because it performs better than atomic reference counting, even though reference counting is much simpler. Now, sup

by sph 2y ago

People recommend tracing garbage collection because it performs better than atomic reference counting, even though reference counting is much simpler. Now, suppose I were designing a language where data is always owned by at most one thread. I can skip making the ref counter an atomic variable, and with some help of the language do reference counting at compile time: would I still benefit from the complexity of a tracing GC if my goal is performance and predictable latency? I want to have automatic memory management for both kernel and apps. Creating a concurrent tracing GC that walks the entire user and kernel space sounds incredibly more complicated than just inc/dec'ing a counter and freeing if it reaches zero (again, assuming only one thread can access a single object) I know that I would have to add language support for weak pointers or forbid cyclic references altogether, but I wonder if the dislike for reference counting only exists because it doesn't work well for data that's shared across threads. EDIT: thanks all, you have brought excellent arguments and you have convinced me. In fact, in this actor-based OS I am working on, GC+arena based allocation per actor might be the most performing approach. GC collection can happen in the scheduler between messages (so becomes virtually pauseless), and when an actor terminates, just reclaim the entire arena.

neonsunset 2y ago
Lack of multi-threading simplifies a lot, but is at odds with performance.
- wongarsu 2y ago
  You can still have multithreading, you just have to forbid shared data. You can move data between threads at thread creation and termination, and for everything else the language can provide channels/queues to move data between threads. Erlang operates under that model and is great at multithreading
  - hu3 2y ago
    "just have to forbid shared data" That's a too severe constraint to be qualified as "just".
  - sph 2y ago
    That is indeed the goal I am working towards, but a bit more relaxed than Erlang: mutability is possible only within a single actor/thread, but anything sent in a message to another actor is deep copied. So no memory is ever shared, but the language allows single-threaded mutation for performance.
  - neonsunset 2y ago
    It might be great, just not performant. CSP often locks you into a single consumer style of pattern, which is highly problematic and scales poorly for anything that isn't statically partitionable. Once you go to MPMC, you start sharing data which immediately forces you to have proper ARC with the high synchronization cost it entails (even without using atomics, RC forces cacheline eviction between cores meaning it acts as a brutal bottleneck on many-core systems per Amadhal's law).
eru 2y ago
> People recommend tracing garbage collection because it performs better than atomic reference counting, even though reference counting is much simpler. 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.
- sph 2y ago
  > Reference counting is a lot more complicated! It turns every read into a write. Why? Maybe it's crucial to the story, but I am exploring Rust-like single ownership semantics. You would have to "write" only when you create a new reference to something, or the reference is destroyed. But it wouldn't turn any read into a write, no?
  - hu3 2y ago
    https://news.ycombinator.com/item?id=32276580#:~:text=One%20of%20the%20biggest%20issues,increment%20the%20object's%20reference%20count https://news.ycombinator.com/item?id=32276580#:~:text=One%20....
    - steveklabnik 2y ago
      You don’t do this in Rust. Up u can take a normal &T into something held by an Rc<T>. The count will not be touched. It’s only when you need an additional owning reference that you call clone() and increment the count, or when one of the owners goes out of scope, and Drop decrements the count. But for non-owning cases, which are many of them in most code, the count stays the same.
      - hu3 2y ago
pornel 2y ago
Rust has this. Data can be placed in atomic or non-atomic refcounted containers, and the type system disallows sharing non-thread-safe types across threads. Additionally, data can be borrowed from inside the refcounted wrapper, and used freely within a scope without touching the reference count.
mike_hearn 2y ago
Yes you do still benefit, otherwise V8 would use refcounting for everything. 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.
- WalterBright 2y ago
  The decrement also needs to be in a "finally" exception handler. There's also a problem when taking a reference to the contents of an object - that reference can survive the release of the object.
p_l 2y ago
As sibling comment mentioned, reference counting is very much non-predictable in latency. 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).
naasking 2y ago
The dislike started earlier than the rise of pervasive threading. As another poster said, every read turns into a write, meaning, everytime you pass a reference into a function you have to increment the counter, and decrement when the function exits. It turns out, the vast majority of of inc/dec ops are pointless ones like this, which is considerable overhead for literally no benefit. 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.

by sph 2y ago

neonsunset 2y ago

Lack of multi-threading simplifies a lot, but is at odds with performance.

wongarsu 2y ago
You can still have multithreading, you just have to forbid shared data. You can move data between threads at thread creation and termination, and for everything else the language can provide channels/queues to move data between threads. Erlang operates under that model and is great at multithreading
- hu3 2y ago
  "just have to forbid shared data" That's a too severe constraint to be qualified as "just".
- sph 2y ago
  That is indeed the goal I am working towards, but a bit more relaxed than Erlang: mutability is possible only within a single actor/thread, but anything sent in a message to another actor is deep copied. So no memory is ever shared, but the language allows single-threaded mutation for performance.
- neonsunset 2y ago
  It might be great, just not performant. CSP often locks you into a single consumer style of pattern, which is highly problematic and scales poorly for anything that isn't statically partitionable. Once you go to MPMC, you start sharing data which immediately forces you to have proper ARC with the high synchronization cost it entails (even without using atomics, RC forces cacheline eviction between cores meaning it acts as a brutal bottleneck on many-core systems per Amadhal's law).

eru 2y ago

> People recommend tracing garbage collection because it performs better than atomic reference counting, even though reference counting is much simpler. 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.

sph 2y ago
> Reference counting is a lot more complicated! It turns every read into a write. Why? Maybe it's crucial to the story, but I am exploring Rust-like single ownership semantics. You would have to "write" only when you create a new reference to something, or the reference is destroyed. But it wouldn't turn any read into a write, no?
- hu3 2y ago
  https://news.ycombinator.com/item?id=32276580#:~:text=One%20of%20the%20biggest%20issues,increment%20the%20object's%20reference%20count https://news.ycombinator.com/item?id=32276580#:~:text=One%20....
  - steveklabnik 2y ago
    You don’t do this in Rust. Up u can take a normal &T into something held by an Rc<T>. The count will not be touched. It’s only when you need an additional owning reference that you call clone() and increment the count, or when one of the owners goes out of scope, and Drop decrements the count. But for non-owning cases, which are many of them in most code, the count stays the same.
    - hu3 2y ago

pornel 2y ago

Rust has this. Data can be placed in atomic or non-atomic refcounted containers, and the type system disallows sharing non-thread-safe types across threads. Additionally, data can be borrowed from inside the refcounted wrapper, and used freely within a scope without touching the reference count.

mike_hearn 2y ago

Yes you do still benefit, otherwise V8 would use refcounting for everything. 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.

WalterBright 2y ago
The decrement also needs to be in a "finally" exception handler. There's also a problem when taking a reference to the contents of an object - that reference can survive the release of the object.

p_l 2y ago

As sibling comment mentioned, reference counting is very much non-predictable in latency. 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).

naasking 2y ago

The dislike started earlier than the rise of pervasive threading. As another poster said, every read turns into a write, meaning, everytime you pass a reference into a function you have to increment the counter, and decrement when the function exits. It turns out, the vast majority of of inc/dec ops are pointless ones like this, which is considerable overhead for literally no benefit. 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.