News for hackers. Stuff that matters.
Re:Garbage Collection in a Large Lisp System (1984) [pdf] by the-smug-one on Monday August 21, 2023 @06:41PM (#37216325)
>Kandria, a commercial game written in Common Lisp [14 ], is used in a more complex benchmark. The game uses a mixture of object-oriented code and numerical code with unboxed arrays. The game is configured identically to the retail version, using a 4GB heap. We played the same part of the game for a few minutes with each collector configuration10, and record the distribution of how long it takes to produce each frame (frame times), and the distribution of pause times in the kandria benchmark.

That's a fun benchmark to have. Seems like gencgc is better than the new GC anyway wrt pause times?

>Very few objects survive garbage collection in Kandria, with less than a megabyte surviving out of a 200 megabyte nursery.

From this sentence I'm going to guess that Kandria performs a lot of per-frame allocations. Having a bump-pointer arena for this which is reset per-frame would probably be quite nice.

The Acknowledgements section is crazy haha, with mentions such as Cliff Click (OG Hotspot JIT compiler architect) and Larry Masinter (Xerox PARC Interlisp) along with the nice SBCL and Kandria devs.

Re:Garbage Collection in a Large Lisp System (1984) [pdf] by r9550684 on Monday August 21, 2023 @08:40PM (#37217144)
I find it odd that Common Lisp implementations for c machines never experimented with region-based memory management. even allegro Common Lisp doesn't support it. regions have been extensively explored by the ml family of languages, with at least ML Kit implementing them, but I guess ml people (for example MLTon provides rationale for why they don't support them) concluded that they are bad for you. still for systems that require hard realtime guarantees, like video games, it's a handy feature.

personally I fist encountered this idea in a video game: Abuse, a 2d side scroller for dos, had its own lisp interpreter, which had separate "spaces" for objects of various permanence, with EVAL, that ran per-frame, discarding its garbage upon completion.

years later I learned that lisp machines also used "areas" extensively to great effect[0]. by allocating to specific area you could affect paging, improve paging locality, have custom gc behavior and of course invalidated an area in a single call.

[0]https://tumbleweed.nu/r/lm-3/uv/chinual.html#Areas

Re:Garbage Collection in a Large Lisp System (1984) [pdf] by hayley-patton on Monday August 21, 2023 @08:49PM (#37217207)
> That's a fun benchmark to have. Seems like gencgc is better than the new GC anyway wrt pause times?

At that time the GC didn't compact, and so much time was wasted scavenging and sweeping the old objects. Old objects aren't contiguous due to not moving objects, though we try to avoid reading from the heap; we only twiddle metadata tables when sweeping and only read objects that we must scan for old->new references while scavenging. Here that wasn't sufficient:

> As a result, scavenging took 2.9 milliseconds on average, tracing took 1.9 milliseconds, and sweeping took 1.6 milliseconds.

Ideally scavenging and sweeping would take much less time than tracing. I think it should behave better now with compaction, but haven't benchmarked; and my approach to benchmarking Kandria is pretty sloppy in any case.

> Having a bump-pointer arena for this which is reset per-frame would probably be quite nice.

Indeed SBCL has support for arenas (though AIUI no stable user-facing interface at the moment), but it still takes some effort to work out what goes in the arena, and the current interface in SBCL also requires all libraries to know about arenas which isn't great for retrofitting.

> The Acknowledgements section is crazy haha, with mentions such as Cliff Click (OG Hotspot JIT compiler architect) and Larry Masinter (Xerox PARC Interlisp) along with the nice SBCL and Kandria devs.

I can't take much of the blame for much of the design; much of it was collaborated in the #lispcafe channel on Libera, which ostensibly is the "off topic" channel. Well. Also worth mentioning that Cliff Click also worked on parallel/concurrent GC and other parallel algorithms, so he was most helpful with interpreting the performance of this GC.

Re:Garbage Collection in a Large Lisp System (1984) [pdf] by lispm on Tuesday August 22, 2023 @04:25AM (#37220002)
very cool!