6 ms·

Parallel garbage collection for SBCL [pdf]

159 points by slyrus 3y ago

rayiner 3y ago
Very cool! Here is the paper: https://zenodo.org/record/7816398 https://zenodo.org/record/7816398. It uses the well known Immix heap layout/algorithm. https://users.cecs.anu.edu.au/~steveb/pubs/papers/immix-pldi-2008.pdf https://users.cecs.anu.edu.au/~steveb/pubs/papers/immix-pldi... The old gencgc was pretty cool for the single core era, and it sounds like it still holds up well. If I recall correctly, it was based on the Bartlett Mostly Copying paper, which is an elegant and practical GC design. https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-TN-12.pdf https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-TN-12.pdf. I miss these old papers that described this stuff in a way you didn’t have to be a math major to understand. I think the first version of that paper had the C++ code as an appendix: https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-88-2.pdf https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-88-2.pdf. Clarity in your technical communications matters. The Immix papers are similarly well written and clear. I don’t think it’s a surprise that both GC designs have also been independently implemented over and over. The Chaitin-Briggs register allocator is another example where I’d attribute at least some of the success in widespread industrial implementation to Briggs’ excellent and approachable PhD thesis describing the algorithm: https://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-thesis-1992.pdf https://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-th...
- sctb 3y ago
  For more Lisp+Immix action there's also Andy Wingo's article and talk about a new GC for Guile from earlier this year: Article: https://wingolog.org/archives/2023/02/07/whippet-towards-a-new-local-maximum https://wingolog.org/archives/2023/02/07/whippet-towards-a-n... Talk: https://fosdem.org/2023/schedule/event/whippet https://fosdem.org/2023/schedule/event/whippet
  - latenightcoding 3y ago
    Good to know, it never sat right with me that Guile depended on BDW-GC for so long. That's what you use when you are implementing a toy language and don't have time to write your own GC.
    - bjoli 3y ago
      It was never the biggest hurdle for guile performance. I do believe guix has the potential to hit the GC wall, but for most programs I think it has served guile well. With that said, the upcoming immix collector is really friggin exciting.
- mgsouth 3y ago
  I'm getting "connection reset by peer" for the Immix link. Wayback link instead: https://web.archive.org/web/20230313182036/https://users.cecs.anu.edu.au/~steveb/pubs/papers/immix-pldi-2008.pdf https://web.archive.org/web/20230313182036/https://users.cec...
- dang 3y ago
  (As the paper was posted in a more accessible form a few hours ago (thanks slyrus!), I reupped that submission and merged the comments from https://news.ycombinator.com/item?id=37295611 https://news.ycombinator.com/item?id=37295611 hither.)
- amno 3y ago
  > Clarity in your technical communications matters. Indeed; it does. I wish more people watched that Steels talk, where he speaks about importance to use accessible language. One-syllabus words all the way would be perhaps a bit tedious read, but he makes a very good point about clarity in connection to simplicity. Thanks for all the links Raiyner.
ducktective 3y ago
Nice, good to see activity in SBCL dev. Does anyone know how difficult implementing a Real-Time GC would be for SBCL or ECL. I know of that paper by Rodney Brooks (L -- A Common Lisp for Embedded Systems)
- aidenn0 3y ago
  You'll need to be more specific. From a technical (i.e. useless) point of view SBCL very nearly already has a real-time GC, with a few modifications it would qualify since already: 1. The amount of work in a GC operation is bounded by the heap size 2. SBCL has a fixed maximum heap size Two things would need to be done: 1. Ensure the areas where GC is inhibited are bounded 2. Call GC operations on a timer, and when they are done, ensure there is sufficient free space; RTGC cannot exist without specific bounds on the mutator, so you could almost certainly invent bounds on the mutator that would make the gencgc qualify as real-time for. #1 would need to be done for any actually useful RTGC anyways. A slightly less snarky answer is that a non-toy GC is a lot of work. Different choices in GC will affect code-generation (e.g. read and/or write barriers GC, and forwarding-pointers for incremental GC[1]). There's a reason the gencgc has been around as long as it has, and it's because it's "good enough" for a lot of people and the work needed to replace it (with any non stop-the-world GC anyways) is rather large. Even TFA is neither incremental nor concurrent, just parallel. 1: Stop the World GCs may also use forwarding pointers, but codegen doesn't need to know about them because they are fully resolved before the mutator continues.
  - ducktective 3y ago
    thanks
  - mananaysiempre 3y ago
    > From a technical (i.e. useless) point of view SBCL very nearly already has a real-time GC If your technical (theoretical) definitions are useless, you need to use different definitions. A practical definition of “real-time” GC is a minimum mutator utilization bound for any program given sufficent RAM, but the only GC I’m aware of that does this (despite the abundance of papers on GC wirh “real-time” in the title) is Klock’s regional collector[1]. Unfortunately, it seems to be impractically complex. [To be fair, I don’t think any implementation of malloc() in common use would satisfy this constraint either.] [1] https://eschew.wordpress.com/2016/09/02/summarizing-gc/ https://eschew.wordpress.com/2016/09/02/summarizing-gc/
dang 3y ago
Recent and related (but we merged the comments hither): Steel Bank Common Lisp 2.3.8 released: “a mark-region parallel GC is available” - https://news.ycombinator.com/item?id=37295611 https://news.ycombinator.com/item?id=37295611
- hayley-patton 3y ago
  Please note that the paper was published before I implemented incremental compaction; the GC in SBCL 2.3.8 can compact.
  - amno 3y ago
    Thank you for the paper, and for the work! Can I ask a newbish question: will this new GC be available on all OS:s and CPU architectures, or only on some? I don't see anything in the paper about being limiting to some certain platform, so my hopes are high :).
    - hayley-patton 3y ago
      It should be pretty portable, porting is just a matter of time and interest. The main thing is that the compiler needs to use a (more precise, lower overhead) software write barrier rather than using the (coarser, slower) hardware write barrier which was around the longest. I also have to wonder how well the bit-scanning algorithms fare on big-endian, or is that taking "all CPU architectures" too far?
  - dmpk2k 3y ago
    Does this have much effect on Kandria’s latency results? Shirakumo tries to put a positive spin on things, but her results show that SBCL’s existing GC isn’t up to the task for real-time games (or many networked apps, for that matter). As an aside, thanks for your efforts. Adding a new GC is a major effort, which improves things for all of us! :D
    - hayley-patton 3y ago
      I have yet to benchmark it again; my setup was sloppy as I had to run the same part of the game over and over, because record/replay didn't work. (Nor do I have the time and energy now; have to survive the last semester of university now.) But I suspect it should help, by reducing the sweeping and scavenging times which were pretty bad. I'm not sure I agree with the comment about "up to the task for real-time games", but maybe my standards are low for video games, and I have an abnormally fast machine and am likely biased there too.
vindarel 3y ago
Other great achievements from last year [0]: - SBCL is callable as a shared library (see sbcl-librarian) - sb-simd - prebuilt binaries for Android (termux, unofficial) - better image compression using zstd - I'll add https://github.com/sionescu/sbcl-goodies https://github.com/sionescu/sbcl-goodies, binaries with "goodies" inside (OpenSSL, libfixposix) yay! [0]: https://lisp-journey.gitlab.io/blog/these-years-in-common-lisp-2022-in-review/#implementations https://lisp-journey.gitlab.io/blog/these-years-in-common-li... bonus from 2021: true static binaries are coming https://www.timmons.dev/posts/static-executables-with-sbcl-v2.html https://www.timmons.dev/posts/static-executables-with-sbcl-v...
- deleted 3y ago
  [deleted]
- corinroyal 3y ago
  OMG! I read the SBCL release notes every month, but when you put together recent highlights like this, I'm blown away. Android binaries? True static executables? Yes, please! This is impressive progress, especially for a language so many have written off as moribund. And that's just one implementation of the spec. ECL, ABCL, and Clasp are all progressing at a brisk pace too. Maybe the only good language is a dead language.
  - ducktective 3y ago
    >True static executables Correct me if I'm wrong but this has not happened yet.
    - CyberDildonics 3y ago
      It has only been 64 years, you can't expect static executables to happen overnight.
- koito17 3y ago
  I cannot emphasize how much of a game changer SB-SIMD has been for writing performant numeric code in SBCL. Being able to experiment with AVX intrinsics in a REPL has been quite the experience for me.
nicechianti 3y ago
[dead]
Alifatisk 3y ago
What would having a parallel GC mean in the practical sense? That there is no pauses happening during the runtime?
- hayley-patton 3y ago
  There are still pauses, but the pauses are faster by using multiple cores to collect, which is nice for both throughput- and latency-sensitive apps. No-pause ("on-the-fly") collectors exist, but sufficiently-short pause ("concurrent") collectors still do wonders with sub-millisecond latency.
  - simiones 3y ago
    The new GC is not concurrent, it is still a stop-the-world collector. The improvement is that it can do the collection and compaction work in parallel on a multi-core machine. As such, it will greatly increase throughput if given multiple cores, and will lead to lower pause times based on this improvement in throughput.
    - guenthert 3y ago
      > As such, it will greatly increase throughput if given multiple cores, and will lead to lower pause times based on this improvement in throughput. If given many cores or perhaps in a later revision with improved efficiency. Today throughput on a four core CPU seems to be lower.
      - hayley-patton 3y ago
        The mark-region GC has worse throughput with really large heaps compared to the live set (as the cost model doesn't work out), and always had* worse latency on Kandria. But generally throughput with more than two cores tends to be better. * I expect latency to be better with compacting, but I haven't benchmarked, so I haven't a clue.
- simiones 3y ago
  No, it simply means that it can better utilize multiple cores to do the GC work faster, so pauses will be proportionally shorter. With the current SBCL collector (or the old one, since this one is already released), even if you ran on a 16-core system, the GC would still only use a single core to reclaim memory (in practice, to move some of/all your live objects to a different address, as it was a copying collector).
CyberDildonics 3y ago
A pattern I've noticed is that in languages with garbage collection, the garbage collection aspect is never finished. It is always a pain point and people are constantly waiting for promised future features and refinements.
- deleted 3y ago
  [deleted]

159 points by slyrus 3y ago

Very cool! Here is the paper: https://zenodo.org/record/7816398 https://zenodo.org/record/7816398. It uses the well known Immix heap layout/algorithm. https://users.cecs.anu.edu.au/~steveb/pubs/papers/immix-pldi-2008.pdf https://users.cecs.anu.edu.au/~steveb/pubs/papers/immix-pldi... The old gencgc was pretty cool for the single core era, and it sounds like it still holds up well. If I recall correctly, it was based on the Bartlett Mostly Copying paper, which is an elegant and practical GC design. https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-TN-12.pdf https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-TN-12.pdf. I miss these old papers that described this stuff in a way you didn’t have to be a math major to understand. I think the first version of that paper had the C++ code as an appendix: https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-88-2.pdf https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-88-2.pdf. Clarity in your technical communications matters. The Immix papers are similarly well written and clear. I don’t think it’s a surprise that both GC designs have also been independently implemented over and over. The Chaitin-Briggs register allocator is another example where I’d attribute at least some of the success in widespread industrial implementation to Briggs’ excellent and approachable PhD thesis describing the algorithm: https://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-thesis-1992.pdf https://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-th...

sctb 3y ago
For more Lisp+Immix action there's also Andy Wingo's article and talk about a new GC for Guile from earlier this year: Article: https://wingolog.org/archives/2023/02/07/whippet-towards-a-new-local-maximum https://wingolog.org/archives/2023/02/07/whippet-towards-a-n... Talk: https://fosdem.org/2023/schedule/event/whippet https://fosdem.org/2023/schedule/event/whippet
- latenightcoding 3y ago
  Good to know, it never sat right with me that Guile depended on BDW-GC for so long. That's what you use when you are implementing a toy language and don't have time to write your own GC.
  - bjoli 3y ago
    It was never the biggest hurdle for guile performance. I do believe guix has the potential to hit the GC wall, but for most programs I think it has served guile well. With that said, the upcoming immix collector is really friggin exciting.
mgsouth 3y ago
I'm getting "connection reset by peer" for the Immix link. Wayback link instead: https://web.archive.org/web/20230313182036/https://users.cecs.anu.edu.au/~steveb/pubs/papers/immix-pldi-2008.pdf https://web.archive.org/web/20230313182036/https://users.cec...
dang 3y ago
(As the paper was posted in a more accessible form a few hours ago (thanks slyrus!), I reupped that submission and merged the comments from https://news.ycombinator.com/item?id=37295611 https://news.ycombinator.com/item?id=37295611 hither.)
amno 3y ago
> Clarity in your technical communications matters. Indeed; it does. I wish more people watched that Steels talk, where he speaks about importance to use accessible language. One-syllabus words all the way would be perhaps a bit tedious read, but he makes a very good point about clarity in connection to simplicity. Thanks for all the links Raiyner.

ducktective 3y ago

Nice, good to see activity in SBCL dev. Does anyone know how difficult implementing a Real-Time GC would be for SBCL or ECL. I know of that paper by Rodney Brooks (L -- A Common Lisp for Embedded Systems)

aidenn0 3y ago
You'll need to be more specific. From a technical (i.e. useless) point of view SBCL very nearly already has a real-time GC, with a few modifications it would qualify since already: 1. The amount of work in a GC operation is bounded by the heap size 2. SBCL has a fixed maximum heap size Two things would need to be done: 1. Ensure the areas where GC is inhibited are bounded 2. Call GC operations on a timer, and when they are done, ensure there is sufficient free space; RTGC cannot exist without specific bounds on the mutator, so you could almost certainly invent bounds on the mutator that would make the gencgc qualify as real-time for. #1 would need to be done for any actually useful RTGC anyways. A slightly less snarky answer is that a non-toy GC is a lot of work. Different choices in GC will affect code-generation (e.g. read and/or write barriers GC, and forwarding-pointers for incremental GC[1]). There's a reason the gencgc has been around as long as it has, and it's because it's "good enough" for a lot of people and the work needed to replace it (with any non stop-the-world GC anyways) is rather large. Even TFA is neither incremental nor concurrent, just parallel. 1: Stop the World GCs may also use forwarding pointers, but codegen doesn't need to know about them because they are fully resolved before the mutator continues.
- ducktective 3y ago
  thanks
- mananaysiempre 3y ago
  > From a technical (i.e. useless) point of view SBCL very nearly already has a real-time GC If your technical (theoretical) definitions are useless, you need to use different definitions. A practical definition of “real-time” GC is a minimum mutator utilization bound for any program given sufficent RAM, but the only GC I’m aware of that does this (despite the abundance of papers on GC wirh “real-time” in the title) is Klock’s regional collector[1]. Unfortunately, it seems to be impractically complex. [To be fair, I don’t think any implementation of malloc() in common use would satisfy this constraint either.] [1] https://eschew.wordpress.com/2016/09/02/summarizing-gc/ https://eschew.wordpress.com/2016/09/02/summarizing-gc/

dang 3y ago

Recent and related (but we merged the comments hither): Steel Bank Common Lisp 2.3.8 released: “a mark-region parallel GC is available” - https://news.ycombinator.com/item?id=37295611 https://news.ycombinator.com/item?id=37295611

hayley-patton 3y ago
Please note that the paper was published before I implemented incremental compaction; the GC in SBCL 2.3.8 can compact.
- amno 3y ago
  Thank you for the paper, and for the work! Can I ask a newbish question: will this new GC be available on all OS:s and CPU architectures, or only on some? I don't see anything in the paper about being limiting to some certain platform, so my hopes are high :).
  - hayley-patton 3y ago
    It should be pretty portable, porting is just a matter of time and interest. The main thing is that the compiler needs to use a (more precise, lower overhead) software write barrier rather than using the (coarser, slower) hardware write barrier which was around the longest. I also have to wonder how well the bit-scanning algorithms fare on big-endian, or is that taking "all CPU architectures" too far?
- dmpk2k 3y ago
  Does this have much effect on Kandria’s latency results? Shirakumo tries to put a positive spin on things, but her results show that SBCL’s existing GC isn’t up to the task for real-time games (or many networked apps, for that matter). As an aside, thanks for your efforts. Adding a new GC is a major effort, which improves things for all of us! :D
  - hayley-patton 3y ago
    I have yet to benchmark it again; my setup was sloppy as I had to run the same part of the game over and over, because record/replay didn't work. (Nor do I have the time and energy now; have to survive the last semester of university now.) But I suspect it should help, by reducing the sweeping and scavenging times which were pretty bad. I'm not sure I agree with the comment about "up to the task for real-time games", but maybe my standards are low for video games, and I have an abnormally fast machine and am likely biased there too.

vindarel 3y ago

Other great achievements from last year [0]: - SBCL is callable as a shared library (see sbcl-librarian) - sb-simd - prebuilt binaries for Android (termux, unofficial) - better image compression using zstd - I'll add https://github.com/sionescu/sbcl-goodies https://github.com/sionescu/sbcl-goodies, binaries with "goodies" inside (OpenSSL, libfixposix) yay! [0]: https://lisp-journey.gitlab.io/blog/these-years-in-common-lisp-2022-in-review/#implementations https://lisp-journey.gitlab.io/blog/these-years-in-common-li... bonus from 2021: true static binaries are coming https://www.timmons.dev/posts/static-executables-with-sbcl-v2.html https://www.timmons.dev/posts/static-executables-with-sbcl-v...

deleted 3y ago
[deleted]
corinroyal 3y ago
OMG! I read the SBCL release notes every month, but when you put together recent highlights like this, I'm blown away. Android binaries? True static executables? Yes, please! This is impressive progress, especially for a language so many have written off as moribund. And that's just one implementation of the spec. ECL, ABCL, and Clasp are all progressing at a brisk pace too. Maybe the only good language is a dead language.
- ducktective 3y ago
  >True static executables Correct me if I'm wrong but this has not happened yet.
  - CyberDildonics 3y ago
    It has only been 64 years, you can't expect static executables to happen overnight.
koito17 3y ago
I cannot emphasize how much of a game changer SB-SIMD has been for writing performant numeric code in SBCL. Being able to experiment with AVX intrinsics in a REPL has been quite the experience for me.

nicechianti 3y ago

[dead]

Alifatisk 3y ago

What would having a parallel GC mean in the practical sense? That there is no pauses happening during the runtime?

hayley-patton 3y ago
There are still pauses, but the pauses are faster by using multiple cores to collect, which is nice for both throughput- and latency-sensitive apps. No-pause ("on-the-fly") collectors exist, but sufficiently-short pause ("concurrent") collectors still do wonders with sub-millisecond latency.
- simiones 3y ago
  The new GC is not concurrent, it is still a stop-the-world collector. The improvement is that it can do the collection and compaction work in parallel on a multi-core machine. As such, it will greatly increase throughput if given multiple cores, and will lead to lower pause times based on this improvement in throughput.
  - guenthert 3y ago
    > As such, it will greatly increase throughput if given multiple cores, and will lead to lower pause times based on this improvement in throughput. If given many cores or perhaps in a later revision with improved efficiency. Today throughput on a four core CPU seems to be lower.
    - hayley-patton 3y ago
      The mark-region GC has worse throughput with really large heaps compared to the live set (as the cost model doesn't work out), and always had* worse latency on Kandria. But generally throughput with more than two cores tends to be better. * I expect latency to be better with compacting, but I haven't benchmarked, so I haven't a clue.
simiones 3y ago
No, it simply means that it can better utilize multiple cores to do the GC work faster, so pauses will be proportionally shorter. With the current SBCL collector (or the old one, since this one is already released), even if you ran on a 16-core system, the GC would still only use a single core to reclaim memory (in practice, to move some of/all your live objects to a different address, as it was a copying collector).

CyberDildonics 3y ago

A pattern I've noticed is that in languages with garbage collection, the garbage collection aspect is never finished. It is always a pain point and people are constantly waiting for promised future features and refinements.

deleted 3y ago
[deleted]