5 ms·

Garbage Collection in a Large Lisp System (1984) [pdf]

60 points by mepian 3y ago

tekknolagi 3y ago
This is a good paper. It's the one I read some years ago that made semispace garbage collection click for me.
gumby 3y ago
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.
- monocasa 3y ago
  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).
- kryptiskt 3y ago
  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.
  - hayley-patton 3y ago
    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 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.)
- chubot 3y ago
  ??? 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)
  - sph 3y ago
    If you find the time to share links, it would be much appreciated. Thanks for the pointers (heh) anyway.
    - chubot 3y ago
      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/2022/10/garbage-collector.html https://www.oilshell.org/blog/2023/01/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__4477C231-A723-4D13-A4EC-5904428ADECE.jpeg&max-width=1000&rotation=1 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)
- aardvark179 3y ago
  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.
- rurban 3y ago
  I'm using copying with forwarding pointers. Compacting and no stop-the world mess.
smokel 3y ago
I once read that in the olden days, one would work away on a machine for some time, and when evening came, you'd start the garbage collection process to write all relevant data to tape, from which you'd start again the next morning.
- jjtheblunt 3y ago
  i'm not sure if this is related, but i think Lisp systems traditionally let you save the core image to restart in the same state.
- mepian 3y ago
  I think this was being done to the earlier versions of the system, before the GC described in the paper was implemented.
  - lispm 3y ago
    Yes, the ephemeral GC was a huge improvement.
- whartung 3y ago
  Folklore I heard was that after a long day of use it was just faster to restart than let the full GC run.
vindarel 3y ago
related: the Immix inspired parallel-mark-region GC developed by Hayley Patton got merged recently into SBCL (https://github.com/sbcl/sbcl/commit/40276b25370f2af1e1870d3b55d62846543a5b47 https://github.com/sbcl/sbcl/commit/40276b25370f2af1e1870d3b...). https://github.com/sbcl/sbcl/blob/master/doc/internals-notes/mark-region https://github.com/sbcl/sbcl/blob/master/doc/internals-notes... https://applied-langua.ge/~hayley/swcl-gc.pdf https://applied-langua.ge/~hayley/swcl-gc.pdf build with ./make.sh --without-gencgc --with-mark-region-gc (on x86-64/Linux and x86-64/macOS only at the moment).
- the-smug-one 3y ago
  >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.
  - deleted 3y ago
    [deleted]
  - hayley-patton 3y ago
    > 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.

60 points by mepian 3y ago

This is a good paper. It's the one I read some years ago that made semispace garbage collection click for me.

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.

monocasa 3y ago
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).
kryptiskt 3y ago
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.
- hayley-patton 3y ago
  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 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.)
chubot 3y ago
??? 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)
- sph 3y ago
  If you find the time to share links, it would be much appreciated. Thanks for the pointers (heh) anyway.
  - chubot 3y ago
    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/2022/10/garbage-collector.html https://www.oilshell.org/blog/2023/01/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__4477C231-A723-4D13-A4EC-5904428ADECE.jpeg&max-width=1000&rotation=1 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)
aardvark179 3y ago
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.
rurban 3y ago
I'm using copying with forwarding pointers. Compacting and no stop-the world mess.

smokel 3y ago

I once read that in the olden days, one would work away on a machine for some time, and when evening came, you'd start the garbage collection process to write all relevant data to tape, from which you'd start again the next morning.

jjtheblunt 3y ago
i'm not sure if this is related, but i think Lisp systems traditionally let you save the core image to restart in the same state.
mepian 3y ago
I think this was being done to the earlier versions of the system, before the GC described in the paper was implemented.
- lispm 3y ago
  Yes, the ephemeral GC was a huge improvement.
whartung 3y ago
Folklore I heard was that after a long day of use it was just faster to restart than let the full GC run.

vindarel 3y ago

related: the Immix inspired parallel-mark-region GC developed by Hayley Patton got merged recently into SBCL (https://github.com/sbcl/sbcl/commit/40276b25370f2af1e1870d3b55d62846543a5b47 https://github.com/sbcl/sbcl/commit/40276b25370f2af1e1870d3b...). https://github.com/sbcl/sbcl/blob/master/doc/internals-notes/mark-region https://github.com/sbcl/sbcl/blob/master/doc/internals-notes... https://applied-langua.ge/~hayley/swcl-gc.pdf https://applied-langua.ge/~hayley/swcl-gc.pdf build with ./make.sh --without-gencgc --with-mark-region-gc (on x86-64/Linux and x86-64/macOS only at the moment).

the-smug-one 3y ago
>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.
- deleted 3y ago
  [deleted]
- hayley-patton 3y ago
  > 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.