5 ms·

This. Said much better than my other posts, but this is exactly what I was trying to say. Naive ARC vs GC... a good GC will kill it, so don't make the ARC naive

This. Said much better than my other posts, but this is exactly what I was trying to say. Naive ARC vs GC... a good GC will kill it, so don't make the ARC naive...cheat and find ways to skip most ref. counter bumps. It became amazingly clear when I started coding Rust: you only have to bump ref count when you get a new owner. Most RC objects die with just a few counter bumps. Most objects don't need RC at all (most objects can be single owner). Now imagine a lang (lobster given as an example above) that does this automatically. Sweet spot.

nu11ptr 4y ago
Two more interesting ways to speed it up: - Make threads a "special" tracked API call (for example, like Rust) so that you know when something will or won't be passed between threads. If it never "escapes" the thread, you can use non-atomic ref counts for the lifetime of that object (NOTE: I should add this is something I've been thinking on - I don't know how hard/feasible it is to do in practice) - Use biased RC - don't have link to paper handy, but idea is that most multithreaded objects spend most of their life on one thread and when they are on that thread, can use non-atomic ref counts by using a separate counter. When on any other thread they use an atomic counter. When both counts hit zero, object is destroyed.
- verdagon 4y ago
  Definitely! Vale, Lobster, and Cone all require explicit annotations for anything that could cross thread boundaries. Vale's design bends the rules a little bit, it blends structured concurrency with region borrow checking to allow things to temporarily escape the current thread. [0] I believe Lobster spawns a new VM per thread, and has some special abilities to share data between them, but I'm vague on the details. Cone requires an explicit permission to allow crossing thread boundaries, which I think will work pretty well. [1] I've read about biased RC before, but have been skeptical because of the branching involved. How has it worked out in practice? [0] https://verdagon.dev/blog/seamless-fearless-structured-concurrency https://verdagon.dev/blog/seamless-fearless-structured-concu... [1] https://cone.jondgoodwin.com/safety.html https://cone.jondgoodwin.com/safety.html
  - nu11ptr 4y ago
    I've just read about it, never actually used it verbatim tbh, but just found it kinda fascinating. I wrote a somewhat modified version (I don't track local thread ID, I use Rust's type system and Send/Sync properties instead) of the algorithm for a very different purpose: I use it to allow safe moves back and forth between (non-atomic) Rc and (atomic) Arc objects. For this purpose, it is very useful. The actual Rc/Arc operations are no more expensive than regular Rust Rc/Arc (except for the last decrement on Rc - slightly more expensive) I got the idea from this person (I didn't use their algorithm though - they probably do it similar to how I do it though): https://crates.io/crates/hybrid-rc https://crates.io/crates/hybrid-rc
  - rfoo 4y ago
    Biased GC is implemented the "nogil" Python fork. It worked okay-ish.
- elcritch 4y ago
  Nim's ARC memory management uses the first strategy. Non-atomic refs combined with moves really speed things up! Moving data across threads requires the data be of a special type `Isolate`. It can be a bit tricky to prove to the compiler that the data is isolated, e.g. single ownership.
thesz 4y ago
"Garbage collection can be faster than stack allocation" is actual title of this paper: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.2064&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84... However non-naive your automatic counting scheme can be, it still has to touch object at least twice. However non-naive your automatic counting scheme can be, it still has twice as much overhead per object compared to GC - structure and count vs just structure. Sometimes you can factor structure out - by saying "the allocator page contains pointer to structure at the very start", - but this can be done for GC too. I guess in that case GC wins even more. And you need structure (virtual methods table, actual object structure, etc) because release of object should decrease counts of referenced objects. Finally, reference counting can and will fragment heap.
- astrange 4y ago
  Heap fragmentation is a real issue, but "GC is fast if you throw physical memory at it" is actually a very bad argument for it on personal computers, especially if they have to fit on your wrist, and especially if you've invented technologies that make scanning memory more expensive like swap since 1986. ObjC/Swift have some tricks to avoid allocating refcounts, mainly relying on storing them in unused pointer bits.
  - thesz 4y ago
    On the other hand I would like to present to you an LMAX Disruptor: https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/ Software based on this intra-program message bus usually follows "throw memory at it". That software is written in Java (hence GC) and process millions of transactions per second. The memory amount is so high that GC is not triggered at all during operations hours. Nevertheless, this is not achevable with refcounting because, well, refcounting has to keep counts. Refcounts, having non-local access patterns, do not play well with caches, let alone something that have much higher latency like swap. Garbage collection can be used to improve locality: https://safari.ethz.ch/architecture/fall2017/lib/exe/fetch.php?media=p332-chen.pdf https://safari.ethz.ch/architecture/fall2017/lib/exe/fetch.p... Refcounts have troubles with cyclic structures. I guess these tricks of refcount allocation avoidance will work fine unless there's a scale-invariant graph with several tens of thousands nodes. In scale-invariant graphs there is some number of nodes that have links from almost all other nodes. Actually, I've got exactly that experience: typical weighted finite state transducer's HCLG graph for automatic speech recognition is scale-invariant. Analysis over it (in C++ using OpenFST) usually was done reasonably quickly, but there was a substantial delay between final printf and actual program exit, when all these pescy refcounted smart-pointed structures finally got freed. I write all that for other readers to have more unbiased view of the problem. As for me, I greatly prefer arenas - much like "automatic regions with reference counting" mentioned above. Arenas allow for cyclic structures, easy to implement even in C and allow for garbage collection algorithms.
amelius 4y ago
> Naive ARC vs GC... a good GC will kill it, so don't make the ARC naive...cheat and find ways to skip most ref. However, what if you applied that same principle to a GC'd language ...

nu11ptr 4y ago

Two more interesting ways to speed it up: - Make threads a "special" tracked API call (for example, like Rust) so that you know when something will or won't be passed between threads. If it never "escapes" the thread, you can use non-atomic ref counts for the lifetime of that object (NOTE: I should add this is something I've been thinking on - I don't know how hard/feasible it is to do in practice) - Use biased RC - don't have link to paper handy, but idea is that most multithreaded objects spend most of their life on one thread and when they are on that thread, can use non-atomic ref counts by using a separate counter. When on any other thread they use an atomic counter. When both counts hit zero, object is destroyed.

verdagon 4y ago
Definitely! Vale, Lobster, and Cone all require explicit annotations for anything that could cross thread boundaries. Vale's design bends the rules a little bit, it blends structured concurrency with region borrow checking to allow things to temporarily escape the current thread. [0] I believe Lobster spawns a new VM per thread, and has some special abilities to share data between them, but I'm vague on the details. Cone requires an explicit permission to allow crossing thread boundaries, which I think will work pretty well. [1] I've read about biased RC before, but have been skeptical because of the branching involved. How has it worked out in practice? [0] https://verdagon.dev/blog/seamless-fearless-structured-concurrency https://verdagon.dev/blog/seamless-fearless-structured-concu... [1] https://cone.jondgoodwin.com/safety.html https://cone.jondgoodwin.com/safety.html
- nu11ptr 4y ago
  I've just read about it, never actually used it verbatim tbh, but just found it kinda fascinating. I wrote a somewhat modified version (I don't track local thread ID, I use Rust's type system and Send/Sync properties instead) of the algorithm for a very different purpose: I use it to allow safe moves back and forth between (non-atomic) Rc and (atomic) Arc objects. For this purpose, it is very useful. The actual Rc/Arc operations are no more expensive than regular Rust Rc/Arc (except for the last decrement on Rc - slightly more expensive) I got the idea from this person (I didn't use their algorithm though - they probably do it similar to how I do it though): https://crates.io/crates/hybrid-rc https://crates.io/crates/hybrid-rc
- rfoo 4y ago
  Biased GC is implemented the "nogil" Python fork. It worked okay-ish.
elcritch 4y ago
Nim's ARC memory management uses the first strategy. Non-atomic refs combined with moves really speed things up! Moving data across threads requires the data be of a special type `Isolate`. It can be a bit tricky to prove to the compiler that the data is isolated, e.g. single ownership.

thesz 4y ago

"Garbage collection can be faster than stack allocation" is actual title of this paper: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.2064&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84... However non-naive your automatic counting scheme can be, it still has to touch object at least twice. However non-naive your automatic counting scheme can be, it still has twice as much overhead per object compared to GC - structure and count vs just structure. Sometimes you can factor structure out - by saying "the allocator page contains pointer to structure at the very start", - but this can be done for GC too. I guess in that case GC wins even more. And you need structure (virtual methods table, actual object structure, etc) because release of object should decrease counts of referenced objects. Finally, reference counting can and will fragment heap.

astrange 4y ago
Heap fragmentation is a real issue, but "GC is fast if you throw physical memory at it" is actually a very bad argument for it on personal computers, especially if they have to fit on your wrist, and especially if you've invented technologies that make scanning memory more expensive like swap since 1986. ObjC/Swift have some tricks to avoid allocating refcounts, mainly relying on storing them in unused pointer bits.
- thesz 4y ago
  On the other hand I would like to present to you an LMAX Disruptor: https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/ Software based on this intra-program message bus usually follows "throw memory at it". That software is written in Java (hence GC) and process millions of transactions per second. The memory amount is so high that GC is not triggered at all during operations hours. Nevertheless, this is not achevable with refcounting because, well, refcounting has to keep counts. Refcounts, having non-local access patterns, do not play well with caches, let alone something that have much higher latency like swap. Garbage collection can be used to improve locality: https://safari.ethz.ch/architecture/fall2017/lib/exe/fetch.php?media=p332-chen.pdf https://safari.ethz.ch/architecture/fall2017/lib/exe/fetch.p... Refcounts have troubles with cyclic structures. I guess these tricks of refcount allocation avoidance will work fine unless there's a scale-invariant graph with several tens of thousands nodes. In scale-invariant graphs there is some number of nodes that have links from almost all other nodes. Actually, I've got exactly that experience: typical weighted finite state transducer's HCLG graph for automatic speech recognition is scale-invariant. Analysis over it (in C++ using OpenFST) usually was done reasonably quickly, but there was a substantial delay between final printf and actual program exit, when all these pescy refcounted smart-pointed structures finally got freed. I write all that for other readers to have more unbiased view of the problem. As for me, I greatly prefer arenas - much like "automatic regions with reference counting" mentioned above. Arenas allow for cyclic structures, easy to implement even in C and allow for garbage collection algorithms.

amelius 4y ago

> Naive ARC vs GC... a good GC will kill it, so don't make the ARC naive...cheat and find ways to skip most ref. However, what if you applied that same principle to a GC'd language ...