Real-Time Garbage Collection Is Real(michaelrbernste.in) |
Real-Time Garbage Collection Is Real(michaelrbernste.in) |
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.All have seen decades of work, and we have some heuristics that we use to gauge quality, but there is no single quality measure. Also, studying each of them is rewarding.
Writing your own editor can be as much fun as writing your own garbage collector.
The "garbage collection" book is the only physical one I still own (everything else given away and in e-form now). It is a fascinating book, and gives you insights into PL run-time systems that you wouldn't get as easily studying other algorithms.
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.
Well, not really. Truly manual memory management is getting an enormous block of memory from the OS, and fully manually choosing what goes where within that block of memory. This is indeed a real technique used when the situation is dire enough. If you're not doing that, you're deferring something to your automated solution, the only question is, how much?
malloc/free is a combination that still gives you lots of power, but it's not perfect when you start pushing the abstraction hard enough. All malloc/free combinations have some sort of pathological case, where whatever allocation strategy they are choosing is wrong for some reason. That's why there isn't just one implementation, there's many, and some applications can see big wins switching, while others may see losses.
Garbage collection isn't really some sort of binary dichotomous decision vs. malloc/free; both are forms of automated memory management. Garbage collection techniques just step it up, and try to infer when you are done with memory. The disadvantage is, they may not be as smart as a human, the advantage is that they're a heck of a lot more consistent and pay much better attention. Then, even within "garbage collection", you've got a gradient; you may see a language like Rust with mostly deterministic memory management, but with an easy call-out to GC if you need it. You may see a language like Perl, with relatively consistent finalization as soon as an unshared reference leaves a scope, or you may see something that only collects during sweeps. At the far end you get imprecise garbage collectors, such as those used in Go right now (though they are working on it, and have already made a lot of progress), so even within the realm of GC there's a range of precision vs. speed vs. nuances the programmer needs to know to use them.
GC is necessary because one particular point on this large spectrum isn't the right choice for every program. It isn't even the maximally manual solution. In fact, there's even some middle grounds between malloc/free and fully manual memory management, such as arena allocation. There's a lot of fine gradation on this scale.
"(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.)"
A bold statement. Have you ever heard the term "compaction" used within the context of a database? That's a form of garbage collection. Contrary to what you said, almost all databases have some form of garbage collection. (Probably all the ones you're thinking about.)
As for whether operating systems have garbage collection, it depends on your precise definition of "operating system". Kernels may lack it, but as critical as they are, and as much sheer staggering code they may have for drivers and stuff, conceptually they actually aren't that complicated, compared to a lot of userland things. Broaden your definition and you'll find some form of garbage collection appear again. And if you include "reference counting" approaches as a form of garbage collection, the Linux kernel uses that all over the place. Is reference counting a form of garbage collection? Well, it can actually be a tough call... because it's all on a continuum.
There exists a point on the memory management continuum where management starts being more automatic (gc) than manual (malloc/free). I would like to understand the forces surrounding this specific point, right before the scale tips towards automatic.
If you tried to build a dynamic language without automatic management, what would break and why?
This implies that the only reason for garbage collection is programmer fallibility. However, I think there are some cases where there is literally no better way of knowing when everyone is done with a piece of memory than by checking (closures strike me as an area this can happen pretty quick), at which point the only solution is automated garbage collection - be it provided by the runtime, a library, or written by the programmer for the particular program.
Like console video games. Rarely there is malloc/free type of allocations, and most of them are for some third-party API, and often there are ways to avoid it... or the system itself (sometimes C CRT would do that beneath you, sometimes obvious - strdup, sometimes almost - fopen/fclose, and sometimes unexpected - for example certain *printf functions might do it).
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.
Garbage collection is the main reason why lambdas were slow to be added to C++, as the objects they close over have indefinite lifetimes.
> 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.
This doesn't make any sense, sorry. Manual memory management works well when objects have definite lifetimes, and fails miserably when they don't.
Computers don't have infinite memory. If they did, there would be no need for garbage collection. So if your program needs more memory than the system has, you either need to buy more memory, or figure out areas of the existing memory space that can be overwritten, or rewrite your program to use less memory. (Some embedded systems developers never use free() because they know their code is the only running code and know it probably won't use all the device's memory.) You can manually figure out and mark memory that can be overwritten by using free(), which can be error-prone if you accidentally mark a block of memory as available that shouldn't be. Or you can let the programming language runtime figure it out itself according to whatever algorithm (such as, simplistically, "this block of memory won't ever be accessed again in the running code, we can reuse its memory"). Garbage collection algorithms can be a lot more sophisticated and use memory-sharing and other things, but the point is to make memory usage efficient and not something the programmer necessarily needs to worry about.
Returning complex objects, without requiring them to be manually freed by whoever picked them (caller).
Also in certain languages - garbage collection actually allows saving of memory. If all strings are immutable, then "one", "one" and "one" might be stored in one place, and whoever asked for them would get the same place (you'll also get the benefit of using only pointer comparison, instead of strcmp). For this gc is needed - e.g. you return things, but you don't specify who owns them. It's just that much later an "agency" starts looking from the certain roots to track down which things are still owned, and which not.
For example - cherry tree - start from the root - all cherries on the tree are owned, all on the ground are no longer - they can be collected. Poor analogy, but it might work for some people.
One more point - if you have 1,000,000 mallocs and then frees then this might be much slower than having 1,000,000 allocations through a garbage collector and freeing them.
In the former case there is this form of "micro-management" - e.g. you have manually micro managed every allocation out there, and then you've had manually micro managed to free it.
Instead the garbage collector might free everything in few sweeps. Also the allocation with garbage collector can be sometimes as simple as moving a pointer ahead.
In the past CGI services were notorious for being slow when shutting down the process. A big portion of this was freeing the memory. In fact you don't need this, when a process is shutdown, no memory needs to be freed - e.g. this is a bit like ad-hoc garbage collection.
Another example was Pascal - there were mark/release regions. You can mark something, and then with release you would free all blocks at once allocated after the mark.
Such things are useful, when you don't want to suffer from too much malloc/free, but would like to keep sane non-gc collection scheme.
And lastly reference counting - it's another form of garbage collection/manual freeing, and it's used quite a lot. There is one problem - most of the implementations cannot handle cycles, and all of them suffer the penalty of dealing with the internal counter, which is even worse when more CPU's have to touch it.
Look at libpq for instance. There are several functions that free memory and destroy different types of objects: PQclear, PQfreemem, PQfinish, PQconninfoFree and maybe others that I forget. For some API functions the documentation explicitly states which free function to use, for others it says nothing and for yet others it says not to free anything because another object retains ownership.
C++ tries to solve the problem that libpq has by using RAII and destructors, but it opened a can of worms. Now you have to deal with tons of different types of smart pointers and fancy memory management patterns coming from different libraries and frameworks. And you must never think that smart pointers are really pointers because if you do, bad things will happen:
Can you return the this pointer from a member function? Not if someone else holds a shared_ptr to this. Can you return shared_ptr<ThisClass>(this)? No, because now you may have two different reference counts for the same object. Can you return shared_from_this() after inheriting enable_shared_from_this? Only if at least one shared_ptr already points at this, which depends on how the caller created this. Is SomeClassPtr a SomeClass*, a shared_ptr<SomeClass> or maybe a boost::intrusive_ptr<SomeClass>? Go find the typedef.
So garbage collection is desirable. Unfortunately it seems to be a very difficult problem to solve in the face of large amounts of memory and lots of parallelism, which is exactly where we're headed. I wish Oracle would buy Azul and make their garbage collector available in OpenJDK. The world would be a better place and I would forgive them all the nasty stuff they have done recently :)
[ignoring destructors/finalizers for now]
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! :)
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.
In principle, yes I think it's possible... at least, I don't think it reduces to the halting problem. But it would be tricky. It would be relatively simple to reason statically about the rate of memory allocation (iterate through all paths leading to a 'new' operator), but for this purpose you care about cases where an object becomes garbage and can be deallocated. That occurs when the last reference to the object is overwritten or goes out of scope, which is not so easy to determine in the presence of aliasing.
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?
http://paperhub.s3.amazonaws.com/d14661878f7811e5ee9c43de884...
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.
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.
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.
That said, I'm reading this paper now. It's absolutely fascinating and very approachable. Well worth checking out.
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.
If so, I've heard that can result in non-optimal results, that would also require dynamic analysis to avoid unacceptable worst cases.
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.
Many of the dynamic languages fling closures around with wild abandon, often without you even realizing it. (One object has a reference to another object which is from the standard library which happens to have a closure to something else which ends up with a reference to your original object... oops, circular reference loop. Surprisingly easy.)
There isn't much technically impossible with malloc/free (though IIRC there are indeed some cases that are both sensible and actually can't be correctly expressed in that framework, but the example escapes me), but there's lots of practical code where the cost/benefit ration goes absurdly out of whack if you're trying to write the manual freeing properly. It's hard to write an example here, because it arises from interactions in a large code base exceeding your ability to understand them. It's like when people try to demonstrate how dangerous old-style pthreading is; even though the problem is exponentially bad in nature, anything that fits in a blog post is still comprehensible. The explosion doesn't happen until you got to real code.
There's evidence garbage collection was not the desired solution but a plan B. McCarthy writes the reason reference counting was not implemented was a hardware limitation [1]:
"Since there were only six bits left in a word, and these were in separated parts of the word, reference counts seemed infeasible without a drastic change in the way list structures were represented. (A list handling scheme using reference counts was later used by Collins (1960) on a 48 bit CDC computer).
The second alternative is garbage collection..."
[1] - http://www-formal.stanford.edu/jmc/history/lisp/node3.html#S...
Either the language provides these capabilities, in which case it's doing some memory management of it's own, or you write them, in which case it wasn't necessarily all that dynamic to start with.
I imagine it might look like what you get when you try to write a dynamic language in C (Perl, Ruby, Python), a lot of macros that automate what's going on to the degree you are mostly writing some macro based DSL.
edit: I'm guessing "The Garbage Collection handbook", by Richard Jones et al. Looks like an interesting read.
If you're interested in GCs, I would suggest getting the newer edition for advanced material, and deferring to freely available papers such as Wilson's "Uniprocessor Garbage Collection Techniques" for fundamentals.
And yes, that blue book on garbage collection is worth reading; it's on my bookshelf, too. I'm still looking for something similar on text editors or spreadsheets.
I don't know that there exists tooling to construct these proofs, beyond general proof-constructing support, but I'm not working in hard-realtime environments so I'm sure I'm not aware of everything going on either.
No I don't. All I care about is having enough free memory to make new allocations. I don't care how much garbage there is, I just care that when there's garbage it's being freed fast enough to support my allocations.
It does. But the halting problem is solvable for specific instances, e.g. if you are writing the programmes.