5 ms·

The delay is still non-deterministic, meaning that there is no upper bound that the pause can be guaranteed not to exceed.

by bjourne 10y ago

rwmj 10y ago
This is simply not true! There exist deterministic garbage collectors suitable for realtime applications. For hard real time you probably don't want to be using dynamic allocation at all -- after all, malloc/free (or kmalloc) is non-deterministic too (unless you're using something like TLSF).
- bjourne 10y ago
  Correct, malloc and free (one or both) have non-deterministic running times. A gc, which is a malloc/free + a lot of extras, exacerbates the problem.
  - jepler 10y ago
    Nonsense. Here is one implementation of the pair of functions which have deterministic running times, and may even comply with the C standard: void *malloc(size_t _) { return NULL; } void free(void *ptr) {} More seriously, I bet there are useful allocators that have bounded runtimes; for instance, if you use a multimap to track free blocks as {size: base address} you can find the best-fit block in O(log n) time for malloc (but this doesn't solve the problem of coalescing adjacent blocks in free, you'll need a different, hopefully log-time structure, for this; and you'll need to keep the two in synch; etc). In the kind of embedded I typically think of, there's no need to worry that malloc() has to call sbrk(), which might do things like need to access disk to swap out pages from another process. You're right, if you have sbrk() that takes unbounded time, malloc() will have to take unbounded time if it sometimes calls sbrk().
    - bjourne 10y ago
      Notice how your suggested algorithm's complexity is a function of the amount of memory available. In other words, it is not any more deterministic than the absolutely worst O(n^n) mark&sweep collector you can find. Unless you impose a bound on n, both n^n and log(n) -> inf as n-> inf. In other words, no upper bound on the pause time.
      - bzbarsky 10y ago
        While that's true in theory, in practice n, if it's your memory size, is bounded above by things like "number of atoms in the universe". In other words, log(n) < 300 (doing log base 2 here). Now it may be that plugging in "300" into your pause time formula where log(n) appears leads to unacceptably long pauses. That's a separate discussion and if you're at that point you care not only about O(log n) vs O(1) but also about constants and non-asymptotic behavior and whatnot. An algorithm that gives you a running time of 1ms for all values of n except n == 1, when the running time is 1000ms, is O(1) and even has "1" as the relevant asymptotic constant, but in practice that 1000ms thing might be a problem. The same argument really doesn't work for anything that is linear (or really most sorts of polynomial), simply because the range of possible values becomes so much larger. But if you're ok with your worst-case pause being two orders of magnitude longer than your best-case pause, then a log(n) algorithm works just fine.
        jepler 10y ago
        Yup, a hidden assumption that I didn't state is that 'n' is modest and of course 'log n' is very modest. For example, n = 256 might be the case on a microcontroller doing realtime activities. proving you never exhaust the heap is probably harder than proving your allocator never takes more than X ns, once you've decided to do runtime allocation on your embedded RTOS.
        bjourne 10y ago
        If n is bounded, then log(n) is bounded, yes. But so is n^n. You can claim that a log(n) algorithm runs quickly or almost always fast enough and I'll agree with you. But that is not the same as it being bounded. In practice, log(n) is no guarantee for an algorithm being quick. A tree search is log(n) but for a big enough n it will begin to cause thousands of really slow page faults. In other words it doesn't matter if you pick theory or practice, for strict enough real time guarantees and for large enough values of n, log(n) is too slow. Which is exactly the reason why many real time systems only use static memory.
  - rwmj 10y ago
    The GC I'm writing at the moment for my own mini-OS doesn't use malloc or free (it grabs physical memory by updating a pointer, and it's never freed).
- monocasa 10y ago
  All of the VMs I've seen with hard real time guarantees also have more than an order of magnitude overall performance degradation over native.
  - gmfawcett 10y ago
    As long as you're meeting your guarantees, is raw performance a concern in a hard real-time system?
    - adrianN 10y ago
      Not very much, but performance correlates with the price of the components and the energy consumption.
  - nickpsecurity 10y ago
    I don't have enough experience to speak with authority here. Just an observation from reading on lots of different implementations of stuff. There might be a general rule that gaining more determinism often trades away throughput or vice versa. I remember specific choices of algorithm where this was true. Your claim about hard, real-time GC's having performance degradation was also true for early ones. I know lots of people were focusing on improving performance, though. It's worth surveying the field again to see what the current losses are. And, as another person replied, it might not even matter at all or with a different choice of hardware.
nickpsecurity 10y ago
All of you arguing with rwmj seem to have missed over a decade of research and deployed software in real-time embedded. Here's one product from 2005 whose company is well known in those circles: http://www.businesswire.com/news/home/20050307005203/en/Aonix-Proves-Hard-Real-Time-Java-Technology-Reaches http://www.businesswire.com/news/home/20050307005203/en/Aoni... The first was in 2003 according to IBM work trying to improve on it in 2007: http://researcher.watson.ibm.com/researcher/files/us-bacon/Frampton07Generational.pdf http://researcher.watson.ibm.com/researcher/files/us-bacon/F... I haven't checked on multicore research in a while. A quick Google implies that they're either there or part of the way there for one project on JamaicaVM: https://www.researchgate.net/publication/221032857_Concurrent_Parallel_Real-Time_Garbage-Collection https://www.researchgate.net/publication/221032857_Concurren... So, yeah, you can do deterministic, hard-real-time GC's. They've been done since 2003 with products shipping since about 2005 for use in safety-critical applications. The DO-178B stuff in particular requires high rigour in how software is designed, coded, analyzed, and tested. That an implementation passed that indicates it can be built with high confidence. Research continues on them. Use in FOSS or popular embedded? Almost nothing.
- Kenji 10y ago
  I just have to smile. Parallel realtime garbage collector. What do you do, start threads? On an embedded system? What if all the other cores are already occupied with doing something? Do you preempt those threads? There, you lost a couple dozen microseconds until your garbage collector even started doing something (also see: Translation Lookaside Buffer flushes and its costs). I am sorry, I do not believe it. I need to hit timings within that time, accurately. I don't have any time for garbage, I need to get stuff done on the CPU, then and there!
  - nickpsecurity 10y ago
    I knew you'd focus on the one I Googled as evidence they're doing something in multicore that's not embedded. It's part of why I left it there. You predictably ignored ones for embedded systems that are hard, real-time along with those I cited deployed in industry for hard, real-time. You continue not believing in hard, real-time GC's despite them in production in real systems that aren't crashing or falling out of the sky. You continue to avoid any exploration of the significant amount of published designs you get just Googling "hard real-time GC" to focus on any peripheral, barely-related point you can. There's no reason to doubt hard, real-time GC's exist or can work at this point. You should've moved to another goalpost like what tradeoffs were required as others did. You're either trolling us or dodging all evidence due to beliefs only rooted in faith. That is, ignoring all facts contrary to your belief that hard, real-time GC's don't exist or can't work in embedded. So, I'm done arguing with you since nobody can argue against religion that twists or dismisses real-world things to maintain its faith-based ones.

The delay is still non-deterministic, meaning that there is no upper bound that the pause can be guaranteed not to exceed.

by bjourne 10y ago

The delay is still non-deterministic, meaning that there is no upper bound that the pause can be guaranteed not to exceed.

rwmj 10y ago

This is simply not true! There exist deterministic garbage collectors suitable for realtime applications. For hard real time you probably don't want to be using dynamic allocation at all -- after all, malloc/free (or kmalloc) is non-deterministic too (unless you're using something like TLSF).

bjourne 10y ago
Correct, malloc and free (one or both) have non-deterministic running times. A gc, which is a malloc/free + a lot of extras, exacerbates the problem.
- jepler 10y ago
  Nonsense. Here is one implementation of the pair of functions which have deterministic running times, and may even comply with the C standard: void *malloc(size_t _) { return NULL; } void free(void *ptr) {} More seriously, I bet there are useful allocators that have bounded runtimes; for instance, if you use a multimap to track free blocks as {size: base address} you can find the best-fit block in O(log n) time for malloc (but this doesn't solve the problem of coalescing adjacent blocks in free, you'll need a different, hopefully log-time structure, for this; and you'll need to keep the two in synch; etc). In the kind of embedded I typically think of, there's no need to worry that malloc() has to call sbrk(), which might do things like need to access disk to swap out pages from another process. You're right, if you have sbrk() that takes unbounded time, malloc() will have to take unbounded time if it sometimes calls sbrk().
  - bjourne 10y ago
    Notice how your suggested algorithm's complexity is a function of the amount of memory available. In other words, it is not any more deterministic than the absolutely worst O(n^n) mark&sweep collector you can find. Unless you impose a bound on n, both n^n and log(n) -> inf as n-> inf. In other words, no upper bound on the pause time.
    - bzbarsky 10y ago
      While that's true in theory, in practice n, if it's your memory size, is bounded above by things like "number of atoms in the universe". In other words, log(n) < 300 (doing log base 2 here). Now it may be that plugging in "300" into your pause time formula where log(n) appears leads to unacceptably long pauses. That's a separate discussion and if you're at that point you care not only about O(log n) vs O(1) but also about constants and non-asymptotic behavior and whatnot. An algorithm that gives you a running time of 1ms for all values of n except n == 1, when the running time is 1000ms, is O(1) and even has "1" as the relevant asymptotic constant, but in practice that 1000ms thing might be a problem. The same argument really doesn't work for anything that is linear (or really most sorts of polynomial), simply because the range of possible values becomes so much larger. But if you're ok with your worst-case pause being two orders of magnitude longer than your best-case pause, then a log(n) algorithm works just fine.
      - jepler 10y ago
        Yup, a hidden assumption that I didn't state is that 'n' is modest and of course 'log n' is very modest. For example, n = 256 might be the case on a microcontroller doing realtime activities. proving you never exhaust the heap is probably harder than proving your allocator never takes more than X ns, once you've decided to do runtime allocation on your embedded RTOS.
      - bjourne 10y ago
        If n is bounded, then log(n) is bounded, yes. But so is n^n. You can claim that a log(n) algorithm runs quickly or almost always fast enough and I'll agree with you. But that is not the same as it being bounded. In practice, log(n) is no guarantee for an algorithm being quick. A tree search is log(n) but for a big enough n it will begin to cause thousands of really slow page faults. In other words it doesn't matter if you pick theory or practice, for strict enough real time guarantees and for large enough values of n, log(n) is too slow. Which is exactly the reason why many real time systems only use static memory.
- rwmj 10y ago
  The GC I'm writing at the moment for my own mini-OS doesn't use malloc or free (it grabs physical memory by updating a pointer, and it's never freed).
monocasa 10y ago
All of the VMs I've seen with hard real time guarantees also have more than an order of magnitude overall performance degradation over native.
- gmfawcett 10y ago
  As long as you're meeting your guarantees, is raw performance a concern in a hard real-time system?
  - adrianN 10y ago
    Not very much, but performance correlates with the price of the components and the energy consumption.
- nickpsecurity 10y ago
  I don't have enough experience to speak with authority here. Just an observation from reading on lots of different implementations of stuff. There might be a general rule that gaining more determinism often trades away throughput or vice versa. I remember specific choices of algorithm where this was true. Your claim about hard, real-time GC's having performance degradation was also true for early ones. I know lots of people were focusing on improving performance, though. It's worth surveying the field again to see what the current losses are. And, as another person replied, it might not even matter at all or with a different choice of hardware.

nickpsecurity 10y ago

All of you arguing with rwmj seem to have missed over a decade of research and deployed software in real-time embedded. Here's one product from 2005 whose company is well known in those circles: http://www.businesswire.com/news/home/20050307005203/en/Aonix-Proves-Hard-Real-Time-Java-Technology-Reaches http://www.businesswire.com/news/home/20050307005203/en/Aoni... The first was in 2003 according to IBM work trying to improve on it in 2007: http://researcher.watson.ibm.com/researcher/files/us-bacon/Frampton07Generational.pdf http://researcher.watson.ibm.com/researcher/files/us-bacon/F... I haven't checked on multicore research in a while. A quick Google implies that they're either there or part of the way there for one project on JamaicaVM: https://www.researchgate.net/publication/221032857_Concurrent_Parallel_Real-Time_Garbage-Collection https://www.researchgate.net/publication/221032857_Concurren... So, yeah, you can do deterministic, hard-real-time GC's. They've been done since 2003 with products shipping since about 2005 for use in safety-critical applications. The DO-178B stuff in particular requires high rigour in how software is designed, coded, analyzed, and tested. That an implementation passed that indicates it can be built with high confidence. Research continues on them. Use in FOSS or popular embedded? Almost nothing.

Kenji 10y ago
I just have to smile. Parallel realtime garbage collector. What do you do, start threads? On an embedded system? What if all the other cores are already occupied with doing something? Do you preempt those threads? There, you lost a couple dozen microseconds until your garbage collector even started doing something (also see: Translation Lookaside Buffer flushes and its costs). I am sorry, I do not believe it. I need to hit timings within that time, accurately. I don't have any time for garbage, I need to get stuff done on the CPU, then and there!
- nickpsecurity 10y ago
  I knew you'd focus on the one I Googled as evidence they're doing something in multicore that's not embedded. It's part of why I left it there. You predictably ignored ones for embedded systems that are hard, real-time along with those I cited deployed in industry for hard, real-time. You continue not believing in hard, real-time GC's despite them in production in real systems that aren't crashing or falling out of the sky. You continue to avoid any exploration of the significant amount of published designs you get just Googling "hard real-time GC" to focus on any peripheral, barely-related point you can. There's no reason to doubt hard, real-time GC's exist or can work at this point. You should've moved to another goalpost like what tradeoffs were required as others did. You're either trolling us or dodging all evidence due to beliefs only rooted in faith. That is, ignoring all facts contrary to your belief that hard, real-time GC's don't exist or can't work in embedded. So, I'm done arguing with you since nobody can argue against religion that twists or dismisses real-world things to maintain its faith-based ones.