| > 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). |
> A "never free" allocation strategy meets this requirement.
Yeah, I could have put that better. “Sufficient” probably needs to be defined as a reasonable function of the program’s working set—I’d have said “independent of the program” instead of “reasonable”, except that’d make any non-compacting malloc necessarily non-real-time, as the (Robson) bound[1] there has to depend not only on the working set but also on the ratio between the smallest and largest allocations. On the other hand, maybe forbidding non-compacting mallocs is actually reasonable, because that bound is impractically large anyway.
> 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."
No, the “minimum” in the name refers to a minimum (proportion of time) over all windows. See link in GP and the thesis referenced there for a discussion of the dependency on the window size (which is a bit funny for all allocators).
[1] https://www.sqlite.org/malloc.html