[HN Gopher] Parallel garbage collection for SBCL [pdf]
___________________________________________________________________
Parallel garbage collection for SBCL [pdf]
Author : slyrus
Score : 38 points
Date : 2023-08-28 15:59 UTC (7 hours ago)
(HTM) web link (applied-langua.ge)
(TXT) w3m dump (applied-langua.ge)
| ducktective wrote:
| 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 wrote:
| 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.
| mananaysiempre wrote:
| > 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 provided with 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/
| ducktective wrote:
| thanks
| mannycalavera42 wrote:
| > Nice, good to see activity in SBCL dev.
|
| I mean, they release on a monthly basis... pretty much active I
| would argue? https://www.sbcl.org/all-news.html
| agumonkey wrote:
| Maybe he meant he's happy to see regular activity.
| vindarel wrote:
| 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, binaries
| with "goodies" inside (OpenSSL, libfixposix)
|
| yay!
|
| [0]: 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-v...
| rayiner wrote:
| Very cool! Here is the paper: 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...
|
| 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. 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.
|
| 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-th...
| mgsouth wrote:
| I'm getting "connection reset by peer" for the Immix link.
| Wayback link instead:
| https://web.archive.org/web/20230313182036/https://users.cec...
| sctb wrote:
| 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-n...
|
| Talk: https://fosdem.org/2023/schedule/event/whippet
| latenightcoding wrote:
| 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 wrote:
| 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.
| dang wrote:
| (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
| hither.)
| dang wrote:
| 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
___________________________________________________________________
(page generated 2023-08-28 23:00 UTC)