A Glance At Garbage Collection In OO Languages

JigSaw writes "Garbage collection (GC) is a technology that frees programmers from the hassle of explicitly managing memory allocation for every object they create. Traditionally, the benefit of this automation has come at the cost of significant overhead. However, more efficient algorithms and techniques, coupled with the increased computational power of computers have made the overhead negligible for all but the most extreme situations. Zachary Pinter wrote an excellent article about all this."

Comments

Under the Rug

[Markus Registrada]

As with most such presentations, this article sweeps under the rug most of the reasons why languages dependent on garbage collection have always failed to find much deployment in industrial settings.

A previous poster noted that most GC algorithms are distinctly unfriendly to virtual memory systems. They usually have similar problems with cache locality, which can result in an enormous slowdown, regardless of the time actually spent in the GC itself. A practical problem is that GC regimes are notoriously non-portable, so that each new language implementation needs to have the (increasingly complex) GC re-done again.

A more fundamental problem is that memory is only one of many resources a typical industrial program must manage. GC takes over memory management, but leaves the other scarce resources -- file descriptors, sockets, mutexes, database connections -- to be managed manually, as in C. (Java has this problem, for instance.) "Finalization" simply cannot provide the necessary guarantees.

Given a resource management regime that can handle all these other important resources, as is commonly practiced in C++, memory becomes just another resource. Management is encapsulated the same way for all. A language that lacks the tools necessary to implement such a regime needs GC, so the presence of GC may actually (as in the case of Java) indicate a fundamental weakness in the language.

(Anybody who thinks languages like Haskell or ML are fundamentally more powerful than C++ must be unaware of the Boost Lambda library, and of FC++, a set of header files that implements Haskell language semantics for C++ programs. They get along fine without GC, as well.)

Re:Under the Rug

[WayneConrad]

GC takes over memory management, but leaves the other scarce resources -- file descriptors, sockets, mutexes, database connections -- to be managed manually, as in C.

Ruby has an interesting approach using closures to handle manual resource allocation. One calls the function that allocates a resource, passing it a closure. The function allocates the resource, calls the closure, and then deallocates the resource (even if an exception occurs). Here's how you might write to a file the manual way (I apologize for the lousy formatting; I don't know how to trick /. into indenting):

file = File.new("foo")
file.puts "My mistress's eyes are nothing like the sun"
file.close

That's the usual way, easy to get wrong: What if an exception occurs? What if I forget to call close? Here's the better way, calling File.open and passing it a closure:

File.open("foo") do |file|
file.puts "My mistress's eyes are nothing like the sun"
end

File.open might use this common idiom:

def File.open(filename)
file = File.open(filename)
begin
yield(file)
ensure
file.close
end
end

The "yield" calls the closure that was passed in, passing it the file object. The "begin...ensure" is like Java's "try...finally" construct, used here to make sure that the file gets closed whether the closure terminates normally or raises an exception.

This idiom doesn't solve all manual resource allocation/cleanup problems, but it's a pretty way to solve some of them.

I don't think Ruby invented this idiom, but I don't know where it came from. Perhaps Lisp: Everything seems to have come from Lisp.

Re:Under the Rug

[Pseudonym]

A previous poster noted that most GC algorithms are distinctly unfriendly to virtual memory systems.

It depends on the language. Haskell, for example, has very different memory access patterns than Java. Being lazy, a value is produced only when it's time to be first consumed, at which point it often becomes garbage immediately. It follows that most of the garbage that a decent generational GC will be collecting will probably be in cache.

Anybody who thinks languages like Haskell or ML are fundamentally more powerful than C++ must be unaware of the Boost Lambda library [...]

I'm one of those rarest of beasts, a programmer who regularly uses (and likes) both Haskell and C++. (Disclaimer: I'm not familiar with FC++, though from what I've read it doesn't really support lazy evaluation, which is one of Haskell's most important distinguishing features.)

From a reductionist point of view, of course, neither is more powerful than the other. However, even with Boost.Lambda and the likw, I still find Haskell almost always allows for far more rapid development than C++ does, all other things being equal. Naturally, all other things are rarely equal, and speed of development is not always the greatest concern, and I won't be drawn into ranking one of my two favourite languages over the other.

Re:Under the Rug

[BCoates]

That sounds like the way a C++ destructor is used with the "Resource Acquisition is Initialization" model. You'd open a file by creating an object on the stack, and the destructor would close the file-handle once control returns (or the object is deleted, if on the heap)

// some_file_object is a hypothetical file i/o object with manual open(), close(), write(), etc. functions

class File : public some_file_object {
public:
File( const std::string & fname ) : m_handle( open(fname) ) {}
~File() { close(m_handle); }
private:
const handle m_handle;
};

It's sort of inside-out relative to the ruby version becuase it doesn't use the closure, but the useage is near-identical:

{
File file( "foo" );
file.write( "There are more things in heaven and earth, Horatio, than are dreamt of in your philosophy." );
} // close happens here, or at the throw/return/break/continue site, if any

new/delete just being another open/close pair to be avoided or contained away in a small object when practical, so it reduces the benefit gained from GC use.

Dilbert GC

[StarWynd]

This is my kind of garbage collection!

Re:Reference Counting...

[Pseudonym]

It can be.

Let's ignore circular references for a moment. To be honest, cycles don't turn up as often as people claim in programs where reference counting is done manually (or through smart pointers) because people are smart enough to know the issues and avoid them (e.g. by using weak references or other non-owning pointers to break cycles).

For a start, reference counting interacts badly with multithreading. The reference count has to be protected against concurrent updates, and that can cost a lot, especially if the count is already effectively protected in some other way (e.g. by only being used single-threadedly). This is such a problem that many C++ library vendors are doing away with reference counting in their std::basic_strings.

Secondly, every time you copy a pointer, you modify the reference count. Every single time. Sometimes (e.g. if you take a temporary local copy) that will be in cache, but not always. If there's contention between CPUs (see previous point), for example, the count will bounce between them. Sometimes it's an almost guaranteed cache miss.

Admittedly, this isn't such a big problem in C++-implemented reference counting, because the programmer is usually far more aware of what's going on with pointer copying and will go to some lengths to avoid copying, but it can cost if reference counting is automatic. Have a look at the Python source code some time and see just how much trouble it goes to to avoid manipulating reference counts.

The GC pitfall

[jtheory]

Good article, though very limited in scope (basically just a list of GC methods, wrapping up with the methods used by recent Java and .NET interpreters). I was a little disappointed that they didn't get into the implications of using languages with GC.

One pitfall that I've noticed basically comes along with the benefit of avoiding "micro-managed" explicit memory management -- there are a lot of Java coders who don't think at *all* about memory management, because they think it's all handled for them. Mix that in with an over-excitement about OO, and you get some impressively slow and non-scaleable code.

You DO need to understand, at least on a basic level, what's going onto the heap, and what the garbage collector has to do to keep up with your "garbage". Carefully nulling out objects that are going to be out of scope in a millisecond is just wasting space, but you should definitely keep an eye on what objects you're allocating within that loop that runs a million times. They're all going on the heap; are they all going to be on there at the same time? When are they going to be eligible for collection? Are they just Strings, or larger objects (which possible create other objects when they are created)?

If you have to optimize a section of code, consider sticking to primitives and Strings (obviously you're balancing this against the cost of possibly less-maintainable code!), and don't forget that when you instantiate com.foo.Bar, all of its superclasses are also instantiated, including any member objects they hold. And don't make a variable static for no reason -- it won't get collected with the object instance....

Two useful things to think about -- heap size (the objects you're actively using at a given moment, so they can't be collected), and churn rate (how fast you're creating and trashing objects). Object creation/destruction isn't as costly as it was with the early versions of Java (no, you probably don't need that Thread pool!). But any application that needs to scale requires some thought on memory usage and churn before you start coding.

Re:GC has always been efficient

[hak1du]

What about real-time constraints?

What about them? Real-time garbage collectors give you guaranteed real-time responses.

I suspect that you have actually never used a real-time storage allocator of any form. The memory allocators that ship with major C/C++ compilers certainly make no real-time guarantees. The way people usually get real-time performance out of them is by pre-allocating large chunks of memory. Well, you can do in garbage collected languages as well.

GC are generally non-deterministic (they start and finish according to their own rules),

No, they don't. Just like with malloc implementations, their behavior may differ from implementation to implementation, but it is generally pretty well understood. It can usually also be controlled well.

Simple garbage collectors only will start a garbage collection when you ask for a block of memory and it can't satisfy the request; they don't just start up for no reason at all. Parallel garbage collector may run a thread in parallel to the main program but never stopping it. Incremental collectors do a little bit of work each time you allocate. Real-time collectors guarantee well-defined maximum responses for allocation.

If the garbage collector in your language (Java?) doesn't do what you want, it's not a problem with garbage collection in general, it's a problem with the specific implementation your vendor has chosen to give you. Just like there are mediocre or bad malloc implementations, there are mediocre or bad garbage collectors.

How about one of the earlier comments to the effect that mark-and-sweep type algorithms page-faults all the memory used by an application? That has got to be inefficient, and since virtual memory is not under the control of the application by definition there is nothing that can be done, except if the GC is directly under the control of the OS, which doesn't often makes sense (it's not very flexible then).

Well, that comment is wrong. First of all, you don't have to use a mark-and-sweep collector. Most high-performance collectors are, in fact, generational and are very VM friendly (moreso than malloc/free in many cases). Second, operating systems have interfaces to their VM subsystems, so the GC can, in fact, control what is happening with paging--prefetching pages, etc. And they do. Even 20 years ago, Berkeley UNIX had system calls specifically designed to let Franz Lisp let the kernel know what it was doing. Third, a malloc implementation cannot move pointers around to make accesses more local or sequential--good garbage collectors do, so GC is actually superior in that regard.

The article itself says that there is no way to make a GC perform as well or better as a finely tuned hand-micro-managed in every case.

You can "micro-manage" and "fine tune" in the presence of a GC as much as you can in its absence. But in the presence of GC, you have the freedom to be sloppy and your code will still run--so many people don't bother. In C/C++, you don't have a choice.

In languages that don't have GCs you can add one yourself (Bohm's GC works fine for C/C++, and is in fact used for GCJ, the GNU implementation of the Java language), with the benefit that you can turn it off if you don't want it for some reason, something you can't do in Java for example.

No, that is backwards. In languages without GC, you cannot add a GC and get all the benefits from the GC. Boehm's GC, for example, may retain arbitrary amounts of garbage, and its lack of integration with the language and compiler means that it can't be anywhere near as efficient as an integrated GC. Boehm's GC is a great hack, and it work really well, but it is not something you can ultimately rely on. Furthermore, if you add Boehm's GC to a language without GC, you are still left with an unsafe programming language.

Secondly, languages with garbage collection often give you full control over the GC: you can enable it or disable i