3 ms·

From a certain perspective, isn't it more important that pause times be known ahead of time rather than how long they might be?

naasking 4y ago
Real-time just requires bounded pause times, but higher pause times necessarily excludes applications that require latencies below that threshold. There are probably at least a dozen GC algorithms that provide sub-1ms pause times though, so very few applications wouldn't fit the latency requirements, as long as the other requirements are acceptable (typically higher memory use for forwarding pointers, copying, or delayed collection).
- Blackthorn 4y ago
  > There are probably at least a dozen GC algorithms that provide sub-1ms pause times though I'd be interested to know more about which ones provide this guarantee. This has been surprisingly difficult to Google for.
  - pebal 4y ago
    SGCL is a real-time garbage collector for C++ without any pauses. https://github.com/pebal/sgcl https://github.com/pebal/sgcl
  - kaba0 4y ago
    https://news.ycombinator.com/item?id=35027935 https://news.ycombinator.com/item?id=35027935 But as mentioned, boundedness is the important property, hard real time systems are not really fast in any way or shape (e.g. for a modern chip to calculate a missile trajectory you really barely need any time, but it not replying in the necessary time window which may be like half a sec, because GC/JIT compiler/OS interrupt is a no-go).
  - naasking 4y ago
    There's the classic Metronome GC. They say they're currently pushing pause times down to 250usecs: https://researcher.watson.ibm.com/researcher/view_group_subpage.php?id=175 https://researcher.watson.ibm.com/researcher/view_group_subp... The Recycler GC is measured around 2ms on old hardware, so it's surely less now because IIRC that pause time is only to copy the stack to a buffer to scan in a separate thread: Java without the Coffee Breaks: A Nonintrusive Multiprocessor Garbage Collector, https://sites.cs.ucsb.edu/~ckrintz/racelab/gc/papers/bacon-concurrent.pdf https://sites.cs.ucsb.edu/~ckrintz/racelab/gc/papers/bacon-c... A study of 3 realtime concurrent copying collectors, CHICKEN, CLOVER and STOPLESS, all of which seem to "response times" less than 10 usecs: A Study of Concurrent Real-Time Garbage Collectors, https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.353.9594 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.353... Parallel realtime collector, hard to quantify exact pause time because it's configurable and they make a good point that MMU is a better measure: http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/rtg.pdf http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/rtg.pdf Then you have various compile-time GC analyses you can apply to your language, like Perceus: https://www.microsoft.com/en-us/research/uploads/prod/2020/11/perceus-tr-v1.pdf https://www.microsoft.com/en-us/research/uploads/prod/2020/1... The problem with maximum pause times is that it's not necessarily a feature of all realtime collectors, which try to do work incrementally and so don't necessarily introduce pauses in the same way as traditional tracing GCs. As you can see above, some of them quantify realtime behaviour in various ways so you can trade off memory use, CPU utilization and max latency.

naasking 4y ago

Real-time just requires bounded pause times, but higher pause times necessarily excludes applications that require latencies below that threshold. There are probably at least a dozen GC algorithms that provide sub-1ms pause times though, so very few applications wouldn't fit the latency requirements, as long as the other requirements are acceptable (typically higher memory use for forwarding pointers, copying, or delayed collection).

Blackthorn 4y ago
> There are probably at least a dozen GC algorithms that provide sub-1ms pause times though I'd be interested to know more about which ones provide this guarantee. This has been surprisingly difficult to Google for.
- pebal 4y ago
  SGCL is a real-time garbage collector for C++ without any pauses. https://github.com/pebal/sgcl https://github.com/pebal/sgcl
- kaba0 4y ago
  https://news.ycombinator.com/item?id=35027935 https://news.ycombinator.com/item?id=35027935 But as mentioned, boundedness is the important property, hard real time systems are not really fast in any way or shape (e.g. for a modern chip to calculate a missile trajectory you really barely need any time, but it not replying in the necessary time window which may be like half a sec, because GC/JIT compiler/OS interrupt is a no-go).
- naasking 4y ago
  There's the classic Metronome GC. They say they're currently pushing pause times down to 250usecs: https://researcher.watson.ibm.com/researcher/view_group_subpage.php?id=175 https://researcher.watson.ibm.com/researcher/view_group_subp... The Recycler GC is measured around 2ms on old hardware, so it's surely less now because IIRC that pause time is only to copy the stack to a buffer to scan in a separate thread: Java without the Coffee Breaks: A Nonintrusive Multiprocessor Garbage Collector, https://sites.cs.ucsb.edu/~ckrintz/racelab/gc/papers/bacon-concurrent.pdf https://sites.cs.ucsb.edu/~ckrintz/racelab/gc/papers/bacon-c... A study of 3 realtime concurrent copying collectors, CHICKEN, CLOVER and STOPLESS, all of which seem to "response times" less than 10 usecs: A Study of Concurrent Real-Time Garbage Collectors, https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.353.9594 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.353... Parallel realtime collector, hard to quantify exact pause time because it's configurable and they make a good point that MMU is a better measure: http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/rtg.pdf http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/rtg.pdf Then you have various compile-time GC analyses you can apply to your language, like Perceus: https://www.microsoft.com/en-us/research/uploads/prod/2020/11/perceus-tr-v1.pdf https://www.microsoft.com/en-us/research/uploads/prod/2020/1... The problem with maximum pause times is that it's not necessarily a feature of all realtime collectors, which try to do work incrementally and so don't necessarily introduce pauses in the same way as traditional tracing GCs. As you can see above, some of them quantify realtime behaviour in various ways so you can trade off memory use, CPU utilization and max latency.