News for hackers. Stuff that matters.
Re:Chris Lattner on garbage collection vs. Automatic Referen... by nu11ptr on Saturday April 23, 2022 @11:05PM (#31140938)
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.
Re:Chris Lattner on garbage collection vs. Automatic Referen... by thesz on Sunday April 24, 2022 @03:24AM (#31141967)
"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...

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.

Re:Chris Lattner on garbage collection vs. Automatic Referen... by nu11ptr on Sunday April 24, 2022 @08:41AM (#31143429)
To be clear, I don't hate tracing GC, and in fact find all forms of GC fascinating. It is definitely "trade offs". I just happen to program in a space where I like the trade offs of ARC better than those of a tracing GC. This could change if I start doing different forms of coding, and in higher level languages I often do like a tracing GC, but Rust (and these new upcoming languages) are making me rethink this a bit atm.

> However non-naive your automatic counting scheme can be, it still has to touch object at least twice.

Only if the object is actually ARC. The whole goal is omit that entirely. Most objects live and die on the stack via proving single ownership. To be fair, I'm not sure why the same optimization couldn't be done for a tracing GC (many will say GC allocation and frees are already mostly 'free' because you compact live not dead objects, but by putting everything on the GC path, you force the need for a collection sooner than if it wasn't heap allocated at all).

> Finally, reference counting can and will fragment heap.

This is true, but in return we get deterministic destruction and easy FFI. If we can avoid a solid # of our allocations entirely this becomes less of an issue. When building things like trees which hit the allocator hard we use arenas, which are more like a traditional "tracing GC" minus the tracing (bump allocator + deterministic free when done, all at once).

Re:Chris Lattner on garbage collection vs. Automatic Referen... by zozbot234 on Sunday April 24, 2022 @10:20AM (#31144237)
> I just happen to program in a space where I like the trade offs of ARC better than those of a tracing GC.

Even ARC has to be augmented with some tracing in order to deterministically collect cycles. Ideally, of course, we would want to describe things like "non-cyclic ownership graph" as part of the type system, so that the compiler itself can decide where the addition of tracing infrastructure is necessary. (Delayed deallocation, as often seen in tracing, concurrent etc. GC, might be expressed as moving the ownership of finalized objects to some sort of cleanup task. But if you code carefully, the need for this ought to be very rare.)

Re:Chris Lattner on garbage collection vs. Automatic Referen... by kaba0 on Monday April 25, 2022 @09:16AM (#31154089)
> To be fair, I'm not sure why the same optimization couldn't be done for a tracing GC

I may misunderstand you here, but isn’t it just escape analysis done by basically every big GC language out there?

Re:Chris Lattner on garbage collection vs. Automatic Referen... by verdagon on Sunday April 24, 2022 @09:13AM (#31143623)
RC might not fragment the heap for long! Someone built a defragmenting malloc called Mesh [0] which uses virtual page remapping to effectively merge two non-overlapping pages. Pretty brilliant stuff!

[0] https://tiba-jrchang.medium.com/mesh-compacting-memory-manag...

Re:Chris Lattner on garbage collection vs. Automatic Referen... by astrange on Sunday April 24, 2022 @07:23AM (#31143023)
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.

Re:Chris Lattner on garbage collection vs. Automatic Referen... by thesz on Sunday April 24, 2022 @08:08AM (#31143286)
On the other hand I would like to present to you an LMAX 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.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.

Re:Chris Lattner on garbage collection vs. Automatic Referen... by astrange on Monday April 25, 2022 @07:22PM (#31162138)
> 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.

This wouldn't come up in ARC, though mostly because it doesn't detect cycles so you wouldn't use strong references between graph nodes. (Overly large refcounts can still happen other ways but usually get optimized out.)

As a quick solution, I think you'd keep a list of valid nodes and have it be the only strong references to them. This is like an arena, except it doesn't have the possibility of references escaping the arena and being deallocated.

Re:Chris Lattner on garbage collection vs. Automatic Referen... by KMag on Monday April 25, 2022 @09:12PM (#31162873)
Reference counts don't need to be a full size_t. Particularly when you're using a mark-sweep or mark-sweep-compact collector to collect reference cycles, you can use a saturating counter, and just give up on reference counting that object if the reference count ever hits its maximum value.

There are tons of applications where lots of objects only ever have one reference, so in addition to the single mark bit in your object header, you can have a single bit reference count that keeps track of if there are "one" or "more than one" references to the object. If a reference passes out of scope and it refers to an object with the reference count bit unset, then it can be immediately collected. Otherwise, you need to leave the object for the tracing collector to handle. This is useful in cases where you have a function that allocates a buffer, passes it to a function that populates the buffer (without storing a reference to the buffer into any objects), passes that buffer to a function that reads out the data (again, without storing the reference into any objects), and then returns.

In the common case of objects where a C++ unique_ptr would do, this single bit reference count never gets modified. There is more overhead in checking the bit when the reference goes out of scope, but there is never a decrement of the reference count, and the common case doesn't have an increment.

Re:Chris Lattner on garbage collection vs. Automatic Referen... by mananaysiempre on Sunday April 24, 2022 @11:27AM (#31144947)
> Finally, reference counting can and will fragment heap.

Is there anything that won’t fragment heap and simultaneously doesn’t insist on owning the world? It is really, really painful to allow references to cross the GC heap boundary in both directions (witness the GNOME Shell not-a-memory-leak), and to me that is the principal reason: in a low-level language, you can RC only a bit of stuff, but you cannot really moving-GC only a bit of stuff.

(I don’t expect an affirmative answer to this question as stated, but maybe some more basic abstraction for manual memory management would allow this?..)

Re:Chris Lattner on garbage collection vs. Automatic Referen... by nu11ptr on Saturday April 23, 2022 @11:15PM (#31141002)
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.

Re:Chris Lattner on garbage collection vs. Automatic Referen... by verdagon on Saturday April 23, 2022 @11:26PM (#31141057)
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-concu...

[1] https://cone.jondgoodwin.com/safety.html

Re:Chris Lattner on garbage collection vs. Automatic Referen... by nu11ptr on Saturday April 23, 2022 @11:35PM (#31141090)
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

Re:Chris Lattner on garbage collection vs. Automatic Referen... by rfoo on Sunday April 24, 2022 @05:17AM (#31142419)
Biased GC is implemented the "nogil" Python fork. It worked okay-ish.
Re:Chris Lattner on garbage collection vs. Automatic Referen... by elcritch on Sunday April 24, 2022 @02:18AM (#31141713)
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.
Re:Chris Lattner on garbage collection vs. Automatic Referen... by amelius on Sunday April 24, 2022 @08:42AM (#31143433)
> 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 ...