6 ms·

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 Bro

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/
  - User23 3y ago
    The customary way to improve GC performance in Common Lisp is to avoid consing. Which, incidentally, is the customary way to write high performance C code too. Allocate your memory in a piece up front and arrange the data in a way that's friendly to your architecture and then do stuff. Nice thing about Common Lisp is that DISASSEMBLE makes it a fairly smooth process to check that the optimizer is actually doing what you want. And the new SBCL release aids this approach by expanding the cases where the compiler will stack allocate.
  - aidenn0 3y ago
    > If your technical (theoretical) definitions are useless, you need to use different definitions... The question of "what is a real-time GC" is academic because nobody actually wants a real-time GC. They want a real-time system. And some GC algorithms can be used to construct a real-time system. Indeed, as others have noted, SBCL can be used to construct a real-time system if you don't do any allocations.
  - aidenn0 3y ago
    > A practical definition of “real-time” GC is a minimum mutator utilization bound for any program given sufficent RAM I'm going to push back against that definition since: 1) RAM is usually bounded 2) A "never free" allocation strategy meets this requirement. 3) The "minimum mutator utilization bound" needs to be at a given time-slice anyways; e.g. "No more than 50% utilization in any 10ms window" rather than just "No more than 50% utilization." Throughput optimized GCs already give a very low utilization over a very long window; it's narrow windows that they struggle with. I think a practical definition gives minimum bounds for: M: fraction mutator utilization over a narrow time window T (where narrow depends on the problem domain; the orders of magnitude from 10us to 100ms are all reasonable depending on the domain) O: heap size overhead (as a greater than unity multiple of live data) And conditions them on peak allocation rate R, and heap size S, which each may have some reasonable maximum value. If you pick non-reasonable values for R, T, and S then "obviously not realtime" GCs can be made to qualify. If you don't condition your GC on R, T, and S then actual shipping real-time systems using GC don't qualify (e.g. Metronome/Stacatto based systems).
mannycalavera42 3y ago
> 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 https://www.sbcl.org/all-news.html
- agumonkey 3y ago
  Maybe he meant he's happy to see regular activity.

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/
- User23 3y ago
  The customary way to improve GC performance in Common Lisp is to avoid consing. Which, incidentally, is the customary way to write high performance C code too. Allocate your memory in a piece up front and arrange the data in a way that's friendly to your architecture and then do stuff. Nice thing about Common Lisp is that DISASSEMBLE makes it a fairly smooth process to check that the optimizer is actually doing what you want. And the new SBCL release aids this approach by expanding the cases where the compiler will stack allocate.
- aidenn0 3y ago
  > If your technical (theoretical) definitions are useless, you need to use different definitions... The question of "what is a real-time GC" is academic because nobody actually wants a real-time GC. They want a real-time system. And some GC algorithms can be used to construct a real-time system. Indeed, as others have noted, SBCL can be used to construct a real-time system if you don't do any allocations.
- aidenn0 3y ago
  > A practical definition of “real-time” GC is a minimum mutator utilization bound for any program given sufficent RAM I'm going to push back against that definition since: 1) RAM is usually bounded 2) A "never free" allocation strategy meets this requirement. 3) The "minimum mutator utilization bound" needs to be at a given time-slice anyways; e.g. "No more than 50% utilization in any 10ms window" rather than just "No more than 50% utilization." Throughput optimized GCs already give a very low utilization over a very long window; it's narrow windows that they struggle with. I think a practical definition gives minimum bounds for: M: fraction mutator utilization over a narrow time window T (where narrow depends on the problem domain; the orders of magnitude from 10us to 100ms are all reasonable depending on the domain) O: heap size overhead (as a greater than unity multiple of live data) And conditions them on peak allocation rate R, and heap size S, which each may have some reasonable maximum value. If you pick non-reasonable values for R, T, and S then "obviously not realtime" GCs can be made to qualify. If you don't condition your GC on R, T, and S then actual shipping real-time systems using GC don't qualify (e.g. Metronome/Stacatto based systems).

mannycalavera42 3y ago

> 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 https://www.sbcl.org/all-news.html

agumonkey 3y ago
Maybe he meant he's happy to see regular activity.