Algorithms – What Are the Algorithms Behind Low Pause GC?

I've never done low-level programming, so I don't know how complicated can freeing resources get.

Funny how the definition of "low-level" changes over time. When I was first learning to program, any language that provided a standardized heap model that makes a simple allocate/free pattern possible was considered high-level indeed. In low-level programming, you'd have to keep track of the memory yourself, (not the allocations, but the memory locations themselves!), or write your own heap allocator if you were feeling really fancy.

Having said that, there's really nothing scary or "complicated" about it, at all. Remember when you were a child and your mom told you to put away your toys when you're done playing with them, that she is not your maid and wasn't going to clean up your room for you? Memory management is simply this same principle applied to code. (GC is like having a maid who will clean up after you, but she's very lazy and slightly clueless.) The principle of it is simple: Each variable in your code has one and only one owner, and it’s the responsibility of that owner to free the variable’s memory when it is no longer needed. (The Single Ownership Principle) This requires one call per allocation, and several schemes exist that automate ownership and cleanup in one way or another so you don't even have to write that call into your own code.

Garbage collection is supposed to solve two problems. It invariably does a very bad job at one of them, and depending on the implementation may or may not do well with the other one. The problems are memory leaks (holding on to memory after you're done with it) and dangling references (freeing memory before you're done with it.) Let's look at both issues:

Dangling references: Discussing this one first because it's the really serious one. You've got two pointers to the same object. You free one of them and don't notice the other one. Then at some later point you attempt to read (or write to or free) the second one. Undefined behavior ensues. If you don't notice it, you can easily corrupt your memory. Garbage collection is supposed to make this problem impossible by ensuring that nothing is ever freed until all references to it are gone. In a fully-managed language, this almost works, until you have to deal with external, unmanaged memory resources. Then it's right back to square 1. And in a non-managed language, things are trickier still. (Poke around on Mozilla's bug-tracker for Firefox sometime and see if you can find how many different crash bugs were caused by their garbage collector screwing up and freeing things too early!)

Fortunately, dealing with this issue is basically a solved problem. You don't need a garbage collector, you need a debugging memory manager. I use Delphi, for example, and with a single external library and a simple compiler directive I can set the allocator to "Full Debug Mode." This adds a negligible (less than 5%) performance overhead in return for enabling some features that keep track of used memory. If I free an object, it fills its memory with 0x80 bytes (easily recognizable in the debugger) and if I ever attempt to call a virtual method (including the destructor) on a freed object, it notices and interrupts the program with an error box with three stack traces--when the object was created, when it was freed, and where I am now--plus some other useful information, then raises an exception. This is obviously not suitable for release builds, but it makes tracking down and fixing dangling reference issues trivial.

The second issue is memory leaks. This is what happens when you continue to hold on to allocated memory when you no longer need it. It can happen in any language, with or without garbage collection, and can only be fixed by writing your code right. Garbage collection helps to mitigate one specific form of memory leak, the kind that happens when you have no valid references to a piece of memory that has not yet been freed, which means the memory stays allocated until the program ends. Unfortunately, the only way to accomplish this in an automated manner is by turning every allocation into a memory leak!

I'm probably going to get dinged by GC proponents if I try to say something like that, so allow me to explain. Remember that the definition of a memory leak is holding on to allocated memory when you no longer need it. In addition to having no references to something, you can also leak memory by having an unnecessary reference to it, such as holding it in a container object when you should have freed it. I've seen some memory leaks caused by doing this, and they are very difficult to track down whether you have a GC or not, since they involve a perfectly valid reference to the memory and there are no clear "bugs" for debugging tools to catch. As far as I know, there is no automated tool that allows you to catch this type of memory leak.

So a garbage collector only concerns itself with the no-references variety of memory leaks, because that's the only type that can be dealt with in an automated fashion. If it could watch all your references to everything and free every object as soon as it has zero references pointing to it, it would be perfect, at least with regards to the no-references problem. Doing this in an automated manner is called reference counting, and it can be done in some limited situations, but it has its own issues to deal with. (For example, object A holding a reference to object B, which holds a reference to object A. In a reference-counting scheme, neither object can be freed automatically, even when there are no external references to either A or B.) So garbage collectors use tracing instead: Start with a set of known-good objects, find all objects that they reference, find all objects that they reference, and so on recursively until you've found everything. Whatever does not get found in the tracing process is garbage and can be thrown away. (Doing this successfully, of course, requires a managed language that puts certain restrictions on the type system to ensure that the tracing garbage collector can always tell the difference between a reference and some random piece of memory that happens to look like a pointer.)

There are two problems with tracing. First, it's slow, and while it's happening the program has to be more or less paused to avoid race conditions. This can lead to noticeable execution hiccups when the program is supposed to be interacting with a user, or bogged-down performance in a server app. This can be mitigated by various techniques, such as breaking allocated memory up into "generations" on the principle that if an allocation doesn't get collected the first time you try, it's likely to stick around for a while. Both the .NET framework and the JVM use generational garbage collectors.

Unfortunately, this feeds into the second problem: memory not getting freed when you're done with it. Unless the tracing runs immediately after you finish with an object, it will stick around until the next trace, or even longer if it makes it past the first generation. In fact, one of the best explanations of the .NET garbage collector I've seen explains that, in order to make the process as fast as possible, the GC has to defer collection for as long as it can! So the problem of memory leaks is "solved" rather bizarrely by leaking as much memory as possible for as long as possible! This is what I mean when I say that a GC turns every allocation into a memory leak. In fact, there is no guarantee that any given object will ever be collected.

Why is this an issue, when the memory still gets reclaimed when needed? For a couple of reasons. First, imagine allocating a large object (a bitmap, for example,) that takes a significant amount of memory. And then soon after you're done with it, you need another large object that takes the same (or close to the same) amount of memory. Had the first object been freed, the second one can reuse its memory. But on a garbage-collected system, you may well be still waiting for the next trace to run, and so you end up unnecessarily wasting memory for a second large object. It's basically a race condition.

Second, holding memory unnecessarily, especially in large amounts, can cause problems in a modern multitasking system. If you take up too much physical memory, it can cause your program or other programs to have to page (swap some of their memory out to disc) which really slows things down. For certain sytems, such as servers, paging can not only slow the system down, it can crash the whole thing if it's under load.

Like the dangling references problem, the no-references problem can be solved with a debugging memory manager. Again, I'll mention the Full Debug Mode from Delphi's FastMM memory manager, since it's the one I'm most familiar with. (I'm sure similar systems exist for other languages.)

When a program running under FastMM terminates, you can optionally have it report the existence of all allocations that never got freed. Full Debug Mode takes it a step further: it can save a file to disc containing not only the type of allocation, but a stack trace from when it was allocated and other debug info, for each leaked allocation. This makes tracking down no-references memory leaks trivial.

When you really look at it, garbage collection may or may not do well with preventing dangling references, and universally does a bad job at handling memory leaks. Its one virtue, in fact, is not the garbage collection itself, but a side-effect: it provides an automated way to perform heap compaction. This can prevent an arcane problem (memory exhaustion through heap fragmentation) that can kill programs that run continually for a long time and have a high degree of memory churn, and heap compaction is pretty much impossible without garbage collection. However, any good memory allocator these days uses buckets to minimize fragmentation, which means that fragmentation only truly becomes a problem in extreme circumstances. For a program in which heap fragmentation is likely to be a problem, it's advisable to use a compacting garbage collector. But IMO in any other case, the use of garbage collection is premature optimization, and better solutions exist to the problems that it "solves."

Data Structures are, for the most part:

1. Memory resident,
2. Transient,
3. Limited in size,
4. Not re-entrant without adding concurrency mechanisms like locks or immutability,
5. Not ACID compliant,
6. Fast, if chosen carefully.

Databases are, for the most part:

1. Disk-bound,
2. Persistent,
3. Large,
4. Safely concurrent,
5. ACID compliant, with transactional capabilities,
6. Slower than data structures

Data structures are meant to be passed from one place to another, and used internally within a program. When was the last time you sent data from a web page to a web server using a database, or performed a calculation on a database that was entirely resident in memory?

Database systems use data structures as part of their internal implementation. It's a question of size and scope; you use data structures within your program, but a database system is a program in its own right.