News for hackers. Stuff that matters.
Re:Garbage Collection in a Large Lisp System (1984) [pdf] by gumby on Monday August 21, 2023 @12:47PM (#37212107)
Is anyone still using transporting (copying) collectors these days? Without forwarding pointers you can only do it via stop and copy.

I’m not sure I’d want to implement forwarding pointers without hardware support for transparency.

Re:Garbage Collection in a Large Lisp System (1984) [pdf] by kryptiskt on Monday August 21, 2023 @01:27PM (#37212660)
It's quite common with generational GCs, The nursery is small and many objects die early, so not a lot has to copied in minor collections. I've never seen one without forwarding pointers, it seems to me that they are necessary for updating all references.
Re:Garbage Collection in a Large Lisp System (1984) [pdf] by hayley-patton on Monday August 21, 2023 @08:53PM (#37217236)
For what it's worth, compaction with my mark-region GC for SBCL follows "An algorithm for parallel incremental compaction" <https://dl.acm.org/doi/10.1145/773039.512442> which instead logs all references to the objects we want to move while tracing, rather than using forwarding pointers. Well, not quite - the runtime likes to eagerly copy lists to get them contiguous after copying, and so we still use forwarding pointers to avoid copying cons cells twice.

(The mutator also won't ever see forwarding pointers regardless, if you have a STW GC. And if that GC works.)

Re:Garbage Collection in a Large Lisp System (1984) [pdf] by monocasa on Monday August 21, 2023 @01:19PM (#37212559)
Yeah, because you need a copying collector to be generational and to compact. You do have to stop, but you don't have to stop normal execution threads for very long (under a millisecond for ZGC, and the time doesn't scale with heap size).
Re:Garbage Collection in a Large Lisp System (1984) [pdf] by chubot on Monday August 21, 2023 @02:09PM (#37213208)
??? Just about all high performance GCs use moving GCs for the young/fast generation, to get bump allocation

Examples:

The whole v8 lineage of VMs, and SpiderMonkey followed shortly thereafter

Java Hotspot and most fast alternatives

Femtolisp used to bootstrap Julia is a moving GC with no generations

Forwarding is not really a problem, the algorithm is well known

Rooting is a difficult problem in many contexts — both C and webassembly.

You need precise rooting to implement moving GC, that’s the main implementation issue

(On my phone, sorry no links)

Re:Garbage Collection in a Large Lisp System (1984) [pdf] by sph on Tuesday August 22, 2023 @03:17AM (#37219641)
If you find the time to share links, it would be much appreciated. Thanks for the pointers (heh) anyway.
Re:Garbage Collection in a Large Lisp System (1984) [pdf] by chubot on Tuesday August 22, 2023 @01:32PM (#37226007)
Sure, most of the links are in the posts I wrote about it:

https://www.oilshell.org/blog/2022/10/garbage-collector.html

https://www.oilshell.org/blog/2023/01/garbage-collector.html

AFAIK, the Cheney algorithm is the only way to do copying/moving GC. It's tiny and elegant, and I took a picture of it for a contributor:

https://app.oilshell.org/picdir/resize?name=193n849__4477C23...

The GC handbook explanation was better than anything I found online, including in wikipedia.

But GC handbook is also not engineering-focused (see blog posts). It surprisingly difficult to write a GC -- I have new respect for this problem!

As mentioned, we ended up going to a non-moving collector, mainly because debugging is harder, it breaks tools, and it involves even more rooting. And rooting problem is hard, especially in C/C++.

The GCs in C++ like v8 and SpiderMonkey are a bit hard to read -- it is almost like a special dialect of C++. I found the plain C femtolisp and es shell easier to read. And some toy examples on Github, but many of them (even from engineers I know to be great) were VERY incomplete, and not designed in context.

Don't trust an example GC that hasn't been used in production! It probably has bugs or a bad API for rooting!

femtolisp is probably the closest thing to "small" and "used in production" that I found (since it's used to bootstrap Julia)

Re:Garbage Collection in a Large Lisp System (1984) [pdf] by mananaysiempre on Tuesday August 22, 2023 @06:07AM (#37220651)
> Forwarding is not really a problem, the algorithm is well known

I understand it’s not a problem to make forwarding work, but making it not suck doesn’t seem easy. My impression from the literature was that a moving collector requires either an O(heap) pause + write barrier (to rewrite all pointers at once), or a read barrier (to catch stale pointers on the fly), and neither of these options is all that pleasant—read barriers in particular are often decried as expensive.

On the other hand, the articles doing the decrying are usually using a SPARC or the like as their reference point for up-to-date powerful hardware, so I’ve no idea how true any of this is in today’s superscalar world.

Re:Garbage Collection in a Large Lisp System (1984) [pdf] by kaba0 on Tuesday August 22, 2023 @07:07AM (#37221052)
Can’t tell you much about the performance impact of a write barrier, but Java’s new ZGC went with read barriers (trading off some throughput) while making the pause times independent of heap size, not sure if that’s what you were referencing, but if not you might find it interesting.
Re:Garbage Collection in a Large Lisp System (1984) [pdf] by chubot on Tuesday August 22, 2023 @01:36PM (#37226052)
Right, that's why moving collectors are only used in the young/fast generation, for reasons of space and time.

- you don't want the 2x space overhead for your entire heap

- I don't know that any copying/moving GCs are incremental. You just collect the young objects all at once -- the CLR says they aim to make it cost as much as a page fault.

I don't know the common policies offhand, but I imagine the young generation is like 512 KB to 4 MB, so it will fit in caches. The whole point is bump allocation and locality

I don't have experience with GCs where the mutator dereferences through a pointer -- my impression is that's rare, but I'm not sure.

In the normal Cheney collector, the forwarding pointers are only used during the algorithm itself. It has to update pointers for the mutator, but after that, the mutator does normal dereferencing.

Re:Garbage Collection in a Large Lisp System (1984) [pdf] by aardvark179 on Monday August 21, 2023 @05:11PM (#37215420)
A lot of engineering has gone into GCs over the years to avoid the need to stop the world when copying objects around, and no hardware support is needed for the pointer chasing. You do need support for atomic swaps and sometimes some MMU tricks but other than that you’re good.
Re:Garbage Collection in a Large Lisp System (1984) [pdf] by rurban on Tuesday August 22, 2023 @12:48AM (#37218797)
I'm using copying with forwarding pointers. Compacting and no stop-the world mess.