6 ms·

GC makes hard real time harder. Way worse than malloc. GC usually works by amortization. 99.99% of allocations are hella fast and then there’s that one that tr

GC makes hard real time harder. Way worse than malloc. GC usually works by amortization. 99.99% of allocations are hella fast and then there’s that one that triggers a one second GC that stops the world. There are algorithms to “spread out” the GC cycle over some span of time during which you interleave the GC and your actual code. But then proving that this is schedulable in the worst case is hell. So much hell. I get that real time is hard anyway already. GC just makes it worse.

lisper 4y ago
Malloc has the exact same structure: it's hella fast until you run out of RAM and it returns an allocation failure. The only difference between the two is that with GC you expect to run out of RAM and you expect the system to not just go down in screaming flames when that happens. And yes, that is harder to arrange. But it's not because there is anything inherently harder about GC. The only difference is the expectations about what will happen in the long run, and how much work the programmer has to do to prevent running into the worst-case scenario.
- KerrAvon 4y ago
  I can’t make any sense out of your equivalency assertion. GC won’t magically reclaim memory that is still referenced; there still comes a point where if you can’t demand-page new memory in, you’re going to fail. Are you assuming the malloc-based system hasn’t been debugged and has severe memory leaks? Are you assuming a compacting collector will allow space to be reclaimed that free() wouldn’t.
  - lisper 4y ago
    > GC won’t magically reclaim memory that is still referenced I never said it would. What I said that making GC hard-real-time is no more difficult than making malloc/free hard-real-time. You can do manual memory management in a GC'd system. If you do that, the two systems are literally the same. The only difference between GC and manual memory management is that in a GC'd system, unreferenced memory will eventually be reclaimed and in a manual system it won't. If you lose all references to an allocated block in a manual system, it's gone forever, whereas in a GC'd system you can get it back. This enables a programming style that puts less burden on the coder to prevent memory leaks. But none of this has anything to do with being hard-real-time. Hard-real-time is hard, period, end of story. GC is completely orthogonal to this. Hard-real-time is hard in a GC'd system and it is exactly as hard in a non-GC'd system. The only difference between the two is the same in both hard-real-time and non-hard-real-time cases: in a non-GC'd system, the coder has an extra burden to write code that doesn't leak. That's it.
- silon42 4y ago
  In a real time system you probably shouldn't run out of RAM (or it should be a recoverable error, like dropping a packet). But GC pause is inevitable if the GC can't reliably keep up (like a spike in workload).
  - lisper 4y ago
    > GC pause is inevitable No, it isn't. That's the magic of hard-real-time GC. It isn't easy, but it is possible. [EDIT: A more accurate claim is that GC pause is no more inevitable than an allocation failure in a malloc/free system.]
    - pizlonator 4y ago
      GC pauses are inevitable unless: - you think it’s ok to crash your program with an OOM just because the GC couldn’t keep up with allocation rate. To my knowledge, nobody ever thinks this is ok, so: - you inevitably pause. Maybe it’s rare. Maybe you are “real time” only in the sense that you want responsiveness 99.99% of the time rather than 100% of the time. - you prove schedulability. The “good” alternative that I would assume few people do is prove that the GC can keep up (I.e. prove that it is schedulable). To do that you need to have WCET and WCAR (worst case allocation rate) analyses and you need to feed those into a schedulability analysis. Then there’s a bunch of ridiculous math. If you’re lucky, you can prove you’re schedulable, but it seems like a strictly worse dev plan than just writing C/Ada/Rust/whatever code that doesn’t GC. I list the third option because I know it’s theoretically possible to do it, but I don’t recommend it and I don’t consider it to be a serious option if you’re building something that lives will depend on.
      - tlb 4y ago
        I agree it's very hard to do that when your code needs 90% of the CPU to keep up. But lots of systems need less than 10% for the real-time code. Or less than 1%. In that case, it can be easy to convince yourself that straightforward incremental GCs can keep up. Perhaps you'd argue those systems are over-provisioned, if their CPU is under 10% busy. But there may be good reasons to have extra speed, like supporting a management UI (running at non-RT priority). Or it may be a worthwhile tradeoff for reduced engineering effort. Gigaflop CPUs are like $50 these days, so if your realtime code only needs a megaflop you're likely to end up with very low CPU utilization.
- pizlonator 4y ago
  GC is inherently harder. It has nothing to do with expectations. You have all the proof burden of using malloc (total size of live objects must fit in memory and WCET of allocation can’t suck) plus the additional proof burden that the collector’s cycle is schedulable.
  - admax88qqq 4y ago
    Malloc does not have constant nor guaranteed runtime. It leads to memory fragmentation and requires non constant searches to find a free spot for the next malloc.
    - pizlonator 4y ago
      It’s extremely difficult to make anything in GC have constant time guarantees. Although non real time GCs can defrag the heap, it’s a huge problem to do it in a real time GC.
      - admax88qqq 4y ago
        Sane problems as malloc and free. And due to GC being abstracted and faster amortized time per allocation you have more resources to work with. Look at the Metronome GC from IBM You basically have to guarantee a certain level of resources or a certain allocation rate. Things you have to do anyways in non GCd languages. This whole conversation is moot. Hard real time does not mesh with dynamic allocation, unless your allocation behaviour is very well understood and predictable, in which case it ain't hard to design a GC that works for it. Malloc/free are not free. They have their own limitations and performance characteristics.
  - lisper 4y ago
    > GC is inherently harder. You need to pay closer attention to the claim I am actually making. Of course GC is harder than malloc/free. But malloc/free is not hard-real-time by default [1], and making malloc/free hard-real-time is just as hard as (indeed is pretty much the same problem as) making GC hard-real-time. Hard-real-timeness is a hard problem that is almost entirely independent of the allocation/deallocation strategy. [1] https://militaryembedded.com/avionics/safety-certification/justifiably-apis-militaryaerospace-embedded-code https://militaryembedded.com/avionics/safety-certification/j...
- adwn 4y ago
  > with GC you expect to run out of RAM and you expect the system to not just go down in screaming flames when that happens No, you don't. The main point of GC is that you don't have to think about memory as much as with manual memory management. In fact, most GC languages don't even have an API to explicitly handle an out-of-memory condition: the program or thread will just crash or abort. With malloc(), you can at least properly react to allocation failures [1], which is crucial for hard real-time systems. [1] Like storing the runtime state to flash and restarting the software.
  - p_l 4y ago
    That's not a property of malloc()/free()[1], that's a property of the runtime system which can be satisfied both in GC'ed languages and those with manual memory management. [1] To the point that porting code originating from Linux is rife with bugs when you run on systems that have the possibility of malloc() failing (99.9% setups of linux never report malloc() failure)
  - kaba0 4y ago
    You can only react to OOM when the OS gives you the necessary tools - under ordinary OSs malloc will not fail, even if it couldn’t actually allocate - actual allocation only happens when one writes to the location. But it doesn’t really apply to the topic at hand, just wanted to add.
- alfiedotwtf 4y ago
  > Malloc has the exact same structure: it's hella fast until you run out of RAM and it returns an allocation failure. Doesn't that depend on the allocator though? Some malloc()s will perform some cleanup depending on their internal structure, which is not deterministic
  - lisper 4y ago
    Sure. But in general both malloc and cons are pretty zippy most of the time.

lisper 4y ago

Malloc has the exact same structure: it's hella fast until you run out of RAM and it returns an allocation failure. The only difference between the two is that with GC you expect to run out of RAM and you expect the system to not just go down in screaming flames when that happens. And yes, that is harder to arrange. But it's not because there is anything inherently harder about GC. The only difference is the expectations about what will happen in the long run, and how much work the programmer has to do to prevent running into the worst-case scenario.

KerrAvon 4y ago
I can’t make any sense out of your equivalency assertion. GC won’t magically reclaim memory that is still referenced; there still comes a point where if you can’t demand-page new memory in, you’re going to fail. Are you assuming the malloc-based system hasn’t been debugged and has severe memory leaks? Are you assuming a compacting collector will allow space to be reclaimed that free() wouldn’t.
- lisper 4y ago
  > GC won’t magically reclaim memory that is still referenced I never said it would. What I said that making GC hard-real-time is no more difficult than making malloc/free hard-real-time. You can do manual memory management in a GC'd system. If you do that, the two systems are literally the same. The only difference between GC and manual memory management is that in a GC'd system, unreferenced memory will eventually be reclaimed and in a manual system it won't. If you lose all references to an allocated block in a manual system, it's gone forever, whereas in a GC'd system you can get it back. This enables a programming style that puts less burden on the coder to prevent memory leaks. But none of this has anything to do with being hard-real-time. Hard-real-time is hard, period, end of story. GC is completely orthogonal to this. Hard-real-time is hard in a GC'd system and it is exactly as hard in a non-GC'd system. The only difference between the two is the same in both hard-real-time and non-hard-real-time cases: in a non-GC'd system, the coder has an extra burden to write code that doesn't leak. That's it.
silon42 4y ago
In a real time system you probably shouldn't run out of RAM (or it should be a recoverable error, like dropping a packet). But GC pause is inevitable if the GC can't reliably keep up (like a spike in workload).
- lisper 4y ago
  > GC pause is inevitable No, it isn't. That's the magic of hard-real-time GC. It isn't easy, but it is possible. [EDIT: A more accurate claim is that GC pause is no more inevitable than an allocation failure in a malloc/free system.]
  - pizlonator 4y ago
    GC pauses are inevitable unless: - you think it’s ok to crash your program with an OOM just because the GC couldn’t keep up with allocation rate. To my knowledge, nobody ever thinks this is ok, so: - you inevitably pause. Maybe it’s rare. Maybe you are “real time” only in the sense that you want responsiveness 99.99% of the time rather than 100% of the time. - you prove schedulability. The “good” alternative that I would assume few people do is prove that the GC can keep up (I.e. prove that it is schedulable). To do that you need to have WCET and WCAR (worst case allocation rate) analyses and you need to feed those into a schedulability analysis. Then there’s a bunch of ridiculous math. If you’re lucky, you can prove you’re schedulable, but it seems like a strictly worse dev plan than just writing C/Ada/Rust/whatever code that doesn’t GC. I list the third option because I know it’s theoretically possible to do it, but I don’t recommend it and I don’t consider it to be a serious option if you’re building something that lives will depend on.
    - tlb 4y ago
      I agree it's very hard to do that when your code needs 90% of the CPU to keep up. But lots of systems need less than 10% for the real-time code. Or less than 1%. In that case, it can be easy to convince yourself that straightforward incremental GCs can keep up. Perhaps you'd argue those systems are over-provisioned, if their CPU is under 10% busy. But there may be good reasons to have extra speed, like supporting a management UI (running at non-RT priority). Or it may be a worthwhile tradeoff for reduced engineering effort. Gigaflop CPUs are like $50 these days, so if your realtime code only needs a megaflop you're likely to end up with very low CPU utilization.
pizlonator 4y ago
GC is inherently harder. It has nothing to do with expectations. You have all the proof burden of using malloc (total size of live objects must fit in memory and WCET of allocation can’t suck) plus the additional proof burden that the collector’s cycle is schedulable.
- admax88qqq 4y ago
  Malloc does not have constant nor guaranteed runtime. It leads to memory fragmentation and requires non constant searches to find a free spot for the next malloc.
  - pizlonator 4y ago
    It’s extremely difficult to make anything in GC have constant time guarantees. Although non real time GCs can defrag the heap, it’s a huge problem to do it in a real time GC.
    - admax88qqq 4y ago
      Sane problems as malloc and free. And due to GC being abstracted and faster amortized time per allocation you have more resources to work with. Look at the Metronome GC from IBM You basically have to guarantee a certain level of resources or a certain allocation rate. Things you have to do anyways in non GCd languages. This whole conversation is moot. Hard real time does not mesh with dynamic allocation, unless your allocation behaviour is very well understood and predictable, in which case it ain't hard to design a GC that works for it. Malloc/free are not free. They have their own limitations and performance characteristics.
- lisper 4y ago
  > GC is inherently harder. You need to pay closer attention to the claim I am actually making. Of course GC is harder than malloc/free. But malloc/free is not hard-real-time by default [1], and making malloc/free hard-real-time is just as hard as (indeed is pretty much the same problem as) making GC hard-real-time. Hard-real-timeness is a hard problem that is almost entirely independent of the allocation/deallocation strategy. [1] https://militaryembedded.com/avionics/safety-certification/justifiably-apis-militaryaerospace-embedded-code https://militaryembedded.com/avionics/safety-certification/j...
adwn 4y ago
> with GC you expect to run out of RAM and you expect the system to not just go down in screaming flames when that happens No, you don't. The main point of GC is that you don't have to think about memory as much as with manual memory management. In fact, most GC languages don't even have an API to explicitly handle an out-of-memory condition: the program or thread will just crash or abort. With malloc(), you can at least properly react to allocation failures [1], which is crucial for hard real-time systems. [1] Like storing the runtime state to flash and restarting the software.
- p_l 4y ago
  That's not a property of malloc()/free()[1], that's a property of the runtime system which can be satisfied both in GC'ed languages and those with manual memory management. [1] To the point that porting code originating from Linux is rife with bugs when you run on systems that have the possibility of malloc() failing (99.9% setups of linux never report malloc() failure)
- kaba0 4y ago
  You can only react to OOM when the OS gives you the necessary tools - under ordinary OSs malloc will not fail, even if it couldn’t actually allocate - actual allocation only happens when one writes to the location. But it doesn’t really apply to the topic at hand, just wanted to add.
alfiedotwtf 4y ago
> Malloc has the exact same structure: it's hella fast until you run out of RAM and it returns an allocation failure. Doesn't that depend on the allocator though? Some malloc()s will perform some cleanup depending on their internal structure, which is not deterministic
- lisper 4y ago
  Sure. But in general both malloc and cons are pretty zippy most of the time.