9 ms·

Real-Time Garbage Collection Is Real

119 points by Mongoose 13y ago

JulianMorrison 13y ago
I wonder if this could be improved also by "time stealing" - if the mutator is idling, it waives its slice, if the GC doesn't expect to collect much, it waives its slice. The result would be more irregular but still able to give guarantees.
- jjs 13y ago
  Should it be improved this way? A hard real-time system can fail by running a piece of code too soon as well as too late. OTOH, a soft real-time program like a video game or voice chat could profit from this.
- a-priori 13y ago
  What jjs says is true: this 'time stealing' is non-deterministic, which makes it a no-go for hard real-time systems. For soft real-time systems, it would be a good idea. It would improve the average-case performance and/or power consumption while still providing the same worst-case guarantees.
  - wtracy 13y ago
    Even in a hard real-time system, allowing the garbage collector to "catch up" whenever the mutator is idling sounds reasonable. It should make the system slightly more robust in the face of irregular heap usage.
    - a-priori 13y ago
      I'd argue that in a real-time system, the GC should be tuned such that it should never need to 'catch up' (i.e, in each round of collection, the collector always collects all garbage produced since the last round). If it does, that should be a non-fatal error condition. But I digress. Keep in mind that real-time systems are unique in that -- unlike most software -- they have well-understood requirements and limits. There shouldn't be anything 'irregular'. If there is, then you don't fully understand your system and need to do some analysis. But that said, it's not up to you or I to determine what is 'reasonable'. That's up to the certification body, and they're notoriously conservative about what they will certify (with good reason, I might add). If something causes non-deterministic behaviour, and is not necessary for the function of the system, they will almost certainly ask 'why is that there?' and you'd better have a good answer. Anecdote: I once had a similar thing happen. As a rookie, I once had to implement a search algorithm for one reason or another. I decided to use a recursive implementation of binary search. This routine was flagged during certification. The problem with recursion is that, unlike an iterative solution, as the problem size grows, a recursive algorithm grows in memory as well as time (we couldn't assume the compiler would be smart enough to use tail recursion) and it's hard to prove the maximum stack usage statically. I know, I tried and ended up replacing it with an iterative implementation of binary search.
the8472 13y ago
Or you could go for pauseless garbage collection, then you only have to concern yourself with the collector throughput keeping up with the allocations. http://paperhub.s3.amazonaws.com/d14661878f7811e5ee9c43de88414e86.pdf http://paperhub.s3.amazonaws.com/d14661878f7811e5ee9c43de884...
a-priori 13y ago
While the "Metronome" has very predictable behaviour that makes it probably the best GC collector for real-time purposes, it still has a maximum GC load before it gets backed up. If it gets backed up too far... forget about timing guarantees because the system will fail. The "Metronome" collector can guarantee a known and tunable GC capacity over time (in terms of objects collected/sec), which is good. But the flip side is that you need to be able to guarantee that your application will never exceed that capacity, at least not for any sustained period of time. In order to provide hard real-time guarantees in a garbage collected system, you need to know that there is no situation in which the system produce more garbage faster than the collector can collect. With manual deallocation, you can prove that with static analysis. With garbage collection you have to demonstrate it empirically using dynamic analysis. That requires exhaustive testing to make sure you've covered the worst-case scenario.
- hga 13y ago
  Manual deallocation of a heap???
  - a-priori 13y ago
    Sorry, I don't follow.
    - hga 13y ago
      Are you allocating from and deallocating to a heap? If so, I've heard that can result in non-optimal results, that would also require dynamic analysis to avoid unacceptable worst cases.
      - a-priori 13y ago
        By 'non-optimal results' do you mean heap fragmentation? If so then yes that's a major concern with dynamic memory allocation in real-time environments. These systems must be designed to run continuously for years at a time and have limited memory, so any allocator that causes non-zero heap fragmentation is right out. There are allocators that don't do that. One way is to use a pool allocator which allocates fixed-size blocks. Since all blocks are the same size, fragmentation can't occur.
justncase80 13y ago
Would this also be deterministic? That seems like the fatal flaw with most current GC's.
- a-priori 13y ago
  Depends what you mean by 'deterministic' I suppose. Basically the system they're describing assigns a fixed time slice to the collector. In that way, yes it is deterministic in that the application is guaranteed to have the remaining processor time. What isn't deterministic is the load on the collector. That is determined both by the rate at which your application generates garbage as it performs its work, and how that garbage generation lines up with the collector's time slices. Under normal circumstances that load should have no affect on your application's behaviour or response times. But unlike a regular collector, this one will not degrade gracefully (becoming steadily slower as GC load increases): it will work 100% normal until it reaches a breaking point, at which time it will fail catastrophically.
rayiner 13y ago
Studying garbage collection is a wonderful education in algorithm engineering. Despite decades of work, there is no "best" GC algorithm. Instead, there are different points on the space of optimizing for space/throughput/latency/completeness/etc. Moreover, the various algorithms are linked by deep correspondences (e.g. Bacon's result that all collectors lie on a spectrum between pure tracing and pure reference counting, and that things like generational collection are hybrids.)
- snprbob86 13y ago
  Saving somebody 10 seconds, here is Bacon's paper: http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf
  - apu 13y ago
    Adding the initial http links it automatically: http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf
    - snprbob86 13y ago
      Heh, fixed mine to save somebody yet one more second. Wrote this comment to waste that second that I saved. That said, I'm reading this paper now. It's absolutely fascinating and very approachable. Well worth checking out.
    - deleted 13y ago
      [deleted]
  - profquail 13y ago
    The link is returning a 403 now (perhaps too much traffic from this article). For anyone that still wants to read it, here's a citation -- you can easily find a copy by searching for the title of the paper. Bacon, David F., Perry Cheng, and V. T. Rajan. "A Unified Theory of Garbage Collection." Convergence 6, no. 17 (2004): 32.
- 13y ago
tinco 13y ago
The author starts the piece enthusiastically marvelling at the fact that Real Time Garbage Collectors exist, but the article doesn't go very deep into how this particular one does it. I myself was a bit disappointed when I read the limitations, which reveal that the simple laws still hold, you can't make these guarantees without exactly knowing the upper limit of the amount of memory you are going to allocate. In the event that you design a real time system that dynamically allocates and deallocates objects, wouldn't it be almost or just as easy to implement manual memory management (through pools or whatnot) as it would be correctly identify the maximum amount of allocated memory?
- eru 13y ago
  I guess that depends on your tools. Perahps you have an automatic tool to estimate your memory usage? Of course, programmes amenable to this kind of automatic analysis must be written in a particular style---because in general you can prove anything about arbitrary programmes---but that style might still be easier to bear than managing your own memory.
FooBarWidget 13y ago
Finally a good use of the word "real-time". This is what real-time means, not web apps that stream data over WebSockets.
- scotth 13y ago
  Can't it mean both?
  - lttlrck 13y ago
    Yes, providing it's appropriately prefixed with Soft or Hard...
    - scotth 13y ago
      Context seems good enough.
    - qznc 13y ago
      The web stuff is not even soft realtime. A better term for the web stuff would be "live" or "continuously updated" or "clickless" or whatever.
pron 13y ago
There are actually quite a lot of hard real-time, mission critical systems (mostly defense) using RTSJ (real-time specification for Java) implementations in production, but I don't know how many make use of realtime GC (RTSJ allows for a semi-manual memory management, much simpler than malloc/free but not as easy as a full GC). Some RTSJ implementations have a realtime GC, like IBM's WebSphere Real Time (http://www-03.ibm.com/software/products/us/en/real-time/ http://www-03.ibm.com/software/products/us/en/real-time/) -- that's the one using Metronome -- and Aicas Jamaica VM (http://www.aicas.com/ http://www.aicas.com/). Sun/Oracle also had an RTSJ JVM with a realtime GC (said to be better than Metronome), but it seems to have been discontinued recently.
mcartyem 13y ago
There have been a lot of posts related to garbage collection lately but none of them touched upon what I see as a crucial issue: why is garbage collection needed to begin with? Could you do without it? What is the key point that made it necessary? I'm aware of it being introduced by McCarthy in the original Lisp paper in 1960 of course. But I suspect what McCarthy originally meant is not what garbage collection turned out to be. What I suspect he meant was that there needs to be a way for memory to be managed. malloc/free offer a way for memory to be managed, and presumably they weren't invented until C was nine years later. What McCarthy might have meant is what became malloc/free in C, which doesn't need garbage collection. C isn't the only flag here. Was there any OS on the IBM 704 used to implement the original Lisp? Did the OS support multiprocessing? Because if it didn't (UNIX wasn't invented until 1969 either) it would make sense for memory to be available for a single process. And it would mean when people said garbage collection they were envisioning malloc/free. (Also, databases and operating systems can live without whatever makes garbage collection necessary, since they don't use it, and those are pretty complex and fast pieces of software.) So, what makes garbage collection different than malloc/free, and why is it necessary? I'd love to learn more about that.
- 0x0 13y ago
  Well, if you have data that can be referenced from more than one spot (for example, an object pointer that is a member of multiple lists), you need avoid calling free until the last reference is gone. One way to track that is to use an incrementing and decrementing reference counter, but then you end up leaking memory as soon as you get cyclical references. A garbage collector solves the problem of cyclical references. In some cases a garbage collector can turn out to be more efficient too, since there is no need to spend time carefully managing reference counts! :)
- betterunix 13y ago
  "why is garbage collection needed to begin with?" Well, think about this: what would a declarative language like Prolog look like if you had to manually deallocate memory? At a high enough level of abstraction, it does not make any sense to manually deallocate memory; it may not even make sense to speak about "memory" at all for some abstractions. "So, what makes garbage collection different than malloc/free, and why is it necessary? I'd love to learn more about that." It is the same as the difference between having a compiler generate the instruction sequence for setting up stack frames, and writing those instructions yourself in assembly language. As a programmer, your time is probably better spent on higher-level things than how stack frames are being set up. Likewise with allocating and deallocating memory: you will probably be more productive if you spend your time on something else, like the design or logic of your program. Remember, programming languages exist for programmers, to make us more productive. We are able to do more when we are not being distracted by things like figuring out when it is safe to deallocate memory or ensuring that we do not create memory leaks.
jwatte 13y ago
I'm not sure I agree work based allocators are out. Specifically, if you follow/mark N references for each M words allocated, you can guarantee to not fall behind and still have a strict upper bound on collection cost/run-time jitter. This adds a linear-in-size cost to memory allocation, which already typically has an amortized linear cost (because you touch all memory allocated) so it's analytically very well behaved.

119 points by Mongoose 13y ago

I wonder if this could be improved also by "time stealing" - if the mutator is idling, it waives its slice, if the GC doesn't expect to collect much, it waives its slice. The result would be more irregular but still able to give guarantees.

jjs 13y ago
Should it be improved this way? A hard real-time system can fail by running a piece of code too soon as well as too late. OTOH, a soft real-time program like a video game or voice chat could profit from this.
a-priori 13y ago
What jjs says is true: this 'time stealing' is non-deterministic, which makes it a no-go for hard real-time systems. For soft real-time systems, it would be a good idea. It would improve the average-case performance and/or power consumption while still providing the same worst-case guarantees.
- wtracy 13y ago
  Even in a hard real-time system, allowing the garbage collector to "catch up" whenever the mutator is idling sounds reasonable. It should make the system slightly more robust in the face of irregular heap usage.
  - a-priori 13y ago
    I'd argue that in a real-time system, the GC should be tuned such that it should never need to 'catch up' (i.e, in each round of collection, the collector always collects all garbage produced since the last round). If it does, that should be a non-fatal error condition. But I digress. Keep in mind that real-time systems are unique in that -- unlike most software -- they have well-understood requirements and limits. There shouldn't be anything 'irregular'. If there is, then you don't fully understand your system and need to do some analysis. But that said, it's not up to you or I to determine what is 'reasonable'. That's up to the certification body, and they're notoriously conservative about what they will certify (with good reason, I might add). If something causes non-deterministic behaviour, and is not necessary for the function of the system, they will almost certainly ask 'why is that there?' and you'd better have a good answer. Anecdote: I once had a similar thing happen. As a rookie, I once had to implement a search algorithm for one reason or another. I decided to use a recursive implementation of binary search. This routine was flagged during certification. The problem with recursion is that, unlike an iterative solution, as the problem size grows, a recursive algorithm grows in memory as well as time (we couldn't assume the compiler would be smart enough to use tail recursion) and it's hard to prove the maximum stack usage statically. I know, I tried and ended up replacing it with an iterative implementation of binary search.

the8472 13y ago

Or you could go for pauseless garbage collection, then you only have to concern yourself with the collector throughput keeping up with the allocations. http://paperhub.s3.amazonaws.com/d14661878f7811e5ee9c43de88414e86.pdf http://paperhub.s3.amazonaws.com/d14661878f7811e5ee9c43de884...

a-priori 13y ago

While the "Metronome" has very predictable behaviour that makes it probably the best GC collector for real-time purposes, it still has a maximum GC load before it gets backed up. If it gets backed up too far... forget about timing guarantees because the system will fail. The "Metronome" collector can guarantee a known and tunable GC capacity over time (in terms of objects collected/sec), which is good. But the flip side is that you need to be able to guarantee that your application will never exceed that capacity, at least not for any sustained period of time. In order to provide hard real-time guarantees in a garbage collected system, you need to know that there is no situation in which the system produce more garbage faster than the collector can collect. With manual deallocation, you can prove that with static analysis. With garbage collection you have to demonstrate it empirically using dynamic analysis. That requires exhaustive testing to make sure you've covered the worst-case scenario.

hga 13y ago
Manual deallocation of a heap???
- a-priori 13y ago
  Sorry, I don't follow.
  - hga 13y ago
    Are you allocating from and deallocating to a heap? If so, I've heard that can result in non-optimal results, that would also require dynamic analysis to avoid unacceptable worst cases.
    - a-priori 13y ago
      By 'non-optimal results' do you mean heap fragmentation? If so then yes that's a major concern with dynamic memory allocation in real-time environments. These systems must be designed to run continuously for years at a time and have limited memory, so any allocator that causes non-zero heap fragmentation is right out. There are allocators that don't do that. One way is to use a pool allocator which allocates fixed-size blocks. Since all blocks are the same size, fragmentation can't occur.

justncase80 13y ago

Would this also be deterministic? That seems like the fatal flaw with most current GC's.

a-priori 13y ago
Depends what you mean by 'deterministic' I suppose. Basically the system they're describing assigns a fixed time slice to the collector. In that way, yes it is deterministic in that the application is guaranteed to have the remaining processor time. What isn't deterministic is the load on the collector. That is determined both by the rate at which your application generates garbage as it performs its work, and how that garbage generation lines up with the collector's time slices. Under normal circumstances that load should have no affect on your application's behaviour or response times. But unlike a regular collector, this one will not degrade gracefully (becoming steadily slower as GC load increases): it will work 100% normal until it reaches a breaking point, at which time it will fail catastrophically.

rayiner 13y ago

Studying garbage collection is a wonderful education in algorithm engineering. Despite decades of work, there is no "best" GC algorithm. Instead, there are different points on the space of optimizing for space/throughput/latency/completeness/etc. Moreover, the various algorithms are linked by deep correspondences (e.g. Bacon's result that all collectors lie on a spectrum between pure tracing and pure reference counting, and that things like generational collection are hybrids.)

snprbob86 13y ago
Saving somebody 10 seconds, here is Bacon's paper: http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf
- apu 13y ago
  Adding the initial http links it automatically: http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf
  - snprbob86 13y ago
    Heh, fixed mine to save somebody yet one more second. Wrote this comment to waste that second that I saved. That said, I'm reading this paper now. It's absolutely fascinating and very approachable. Well worth checking out.
  - deleted 13y ago
    [deleted]
- profquail 13y ago
  The link is returning a 403 now (perhaps too much traffic from this article). For anyone that still wants to read it, here's a citation -- you can easily find a copy by searching for the title of the paper. Bacon, David F., Perry Cheng, and V. T. Rajan. "A Unified Theory of Garbage Collection." Convergence 6, no. 17 (2004): 32.
13y ago

tinco 13y ago

The author starts the piece enthusiastically marvelling at the fact that Real Time Garbage Collectors exist, but the article doesn't go very deep into how this particular one does it. I myself was a bit disappointed when I read the limitations, which reveal that the simple laws still hold, you can't make these guarantees without exactly knowing the upper limit of the amount of memory you are going to allocate. In the event that you design a real time system that dynamically allocates and deallocates objects, wouldn't it be almost or just as easy to implement manual memory management (through pools or whatnot) as it would be correctly identify the maximum amount of allocated memory?

eru 13y ago
I guess that depends on your tools. Perahps you have an automatic tool to estimate your memory usage? Of course, programmes amenable to this kind of automatic analysis must be written in a particular style---because in general you can prove anything about arbitrary programmes---but that style might still be easier to bear than managing your own memory.

FooBarWidget 13y ago

Finally a good use of the word "real-time". This is what real-time means, not web apps that stream data over WebSockets.

scotth 13y ago
Can't it mean both?
- lttlrck 13y ago
  Yes, providing it's appropriately prefixed with Soft or Hard...
  - scotth 13y ago
    Context seems good enough.
  - qznc 13y ago
    The web stuff is not even soft realtime. A better term for the web stuff would be "live" or "continuously updated" or "clickless" or whatever.

pron 13y ago

There are actually quite a lot of hard real-time, mission critical systems (mostly defense) using RTSJ (real-time specification for Java) implementations in production, but I don't know how many make use of realtime GC (RTSJ allows for a semi-manual memory management, much simpler than malloc/free but not as easy as a full GC). Some RTSJ implementations have a realtime GC, like IBM's WebSphere Real Time (http://www-03.ibm.com/software/products/us/en/real-time/ http://www-03.ibm.com/software/products/us/en/real-time/) -- that's the one using Metronome -- and Aicas Jamaica VM (http://www.aicas.com/ http://www.aicas.com/). Sun/Oracle also had an RTSJ JVM with a realtime GC (said to be better than Metronome), but it seems to have been discontinued recently.

mcartyem 13y ago

There have been a lot of posts related to garbage collection lately but none of them touched upon what I see as a crucial issue: why is garbage collection needed to begin with? Could you do without it? What is the key point that made it necessary? I'm aware of it being introduced by McCarthy in the original Lisp paper in 1960 of course. But I suspect what McCarthy originally meant is not what garbage collection turned out to be. What I suspect he meant was that there needs to be a way for memory to be managed. malloc/free offer a way for memory to be managed, and presumably they weren't invented until C was nine years later. What McCarthy might have meant is what became malloc/free in C, which doesn't need garbage collection. C isn't the only flag here. Was there any OS on the IBM 704 used to implement the original Lisp? Did the OS support multiprocessing? Because if it didn't (UNIX wasn't invented until 1969 either) it would make sense for memory to be available for a single process. And it would mean when people said garbage collection they were envisioning malloc/free. (Also, databases and operating systems can live without whatever makes garbage collection necessary, since they don't use it, and those are pretty complex and fast pieces of software.) So, what makes garbage collection different than malloc/free, and why is it necessary? I'd love to learn more about that.

0x0 13y ago
Well, if you have data that can be referenced from more than one spot (for example, an object pointer that is a member of multiple lists), you need avoid calling free until the last reference is gone. One way to track that is to use an incrementing and decrementing reference counter, but then you end up leaking memory as soon as you get cyclical references. A garbage collector solves the problem of cyclical references. In some cases a garbage collector can turn out to be more efficient too, since there is no need to spend time carefully managing reference counts! :)
betterunix 13y ago
"why is garbage collection needed to begin with?" Well, think about this: what would a declarative language like Prolog look like if you had to manually deallocate memory? At a high enough level of abstraction, it does not make any sense to manually deallocate memory; it may not even make sense to speak about "memory" at all for some abstractions. "So, what makes garbage collection different than malloc/free, and why is it necessary? I'd love to learn more about that." It is the same as the difference between having a compiler generate the instruction sequence for setting up stack frames, and writing those instructions yourself in assembly language. As a programmer, your time is probably better spent on higher-level things than how stack frames are being set up. Likewise with allocating and deallocating memory: you will probably be more productive if you spend your time on something else, like the design or logic of your program. Remember, programming languages exist for programmers, to make us more productive. We are able to do more when we are not being distracted by things like figuring out when it is safe to deallocate memory or ensuring that we do not create memory leaks.

jwatte 13y ago

I'm not sure I agree work based allocators are out. Specifically, if you follow/mark N references for each M words allocated, you can guarantee to not fall behind and still have a strict upper bound on collection cost/run-time jitter. This adds a linear-in-size cost to memory allocation, which already typically has an amortized linear cost (because you touch all memory allocated) so it's analytically very well behaved.