3 ms·
Reference counting is fast with one CPU core. But it gets worse and worse as you add cores. Inter-CPU synchronization is slow and the buses can saturate. With e
by vardump 10y ago
Reference counting is fast with one CPU core. But it gets worse and worse as you add cores. Inter-CPU synchronization is slow and the buses can saturate. With enough cores, at some point that'll be all the system is doing.
As far as I know, reference counting also requires you to have a heap with "alloc" and "free". Memory allocation is a slow operation, because it involves searching for the best matching free span to avoid heap fragmentation.
On the other hand, GC can scale across any number of CPU cores.
- sklogic 10y agoReference counting is never fast. Even on a single core.
- chipsy 10y agoDon't describe it as "fast". Use "latency" or "throughput". RC is a useful building block for making real-time latency guarantees, and for many apps that is more important than peak throughput.
- sklogic 10y agoIt is really hard to get real time guarantees with RC - given that time for cleaning up depends on a size of a structure. Just imagine it freeing a 10Gb linked list. Real time pure mark and sweep GCs are easier.
- NickPollard 10y agoYou don't have to clean up everything at once - it's possible to put items on a queue to be cleaned up when refcounts hit zero, and you can then control at what rate the queue is emptied.
- sklogic 10y agoWhich makes it already far too complicated, more complex than a real time mark&sweep. Especially if there are loop checks - you cannot just empty the queue gradually, it's all or nothing.
- gpderetta 10y agoThat's not how cpu synchronization work. Reference count updates by themselves are purely CPU local even when atomic. Cross CPU synchronization happens only if an object is actually shared. It is true that, if an object is actually shared, reference counting would 'upgrade' a read only sharing to writable which is expensive; there are ways around that though, look for differential reference counting. Re alloc and free, that's completely orthogonal with refcounting.
- vardump 10y agoYou're more exact, I tried to simplify. Whether they're CPU local depends on cache line state. It's fast in MESI protocol exclusive or modified state. Slow in invalid and shared states. However real systems have contended objects pretty much always. I'm vaguely aware about differential reference counting, but don't know any systems that use it. A bit like fast multicore counters, that break one counter into multiple uncontended "sub-counters". Read operation adds all sub-counters together to get the "real" value. > Re alloc and free, that's completely orthogonal with refcounting. Technically true, but in real systems those go hand in hand almost always. Yeah, I have written firmware for embedded devices that do refcounting and don't allocate memory. But that's not the usual case.
- gpderetta 10y agoI guess that the reason that existing systems do not use advanced refcount modes is that they simply that either they are not meant for high performance (e.g. python, perl) or just don't do much refcount traffic (i.e. only long lived objects are refcounted and new references are not created often). Re alloc and free, I meant that you do not need to use the system malloc and free, you can be allocating and deallocating from a simple thread local bump allocator plus free list. At the limit you can have a fully generational GC behind and use the rerfcount only to decide when to run destructors or as an optimization.
- nwalfield 10y agoCheck out sloppy counters: https://pdos.csail.mit.edu/papers/linux:osdi10.pdf https://pdos.csail.mit.edu/papers/linux:osdi10.pdf