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

An Obvious Fault

[vandel405]

An obvious fault that seems to go with out notice about garbage collectors, particularly stop-and-copy collectors is that when ever they do the full blow stop and copy, they have to touch all of those memory pages, and fault all of your virtual memory back into ram.

Re:An Obvious Fault

[p2sam]

An obvious fault that seems to go with out notice about sorting algorithms, particularly bubble sort is that it takes O(n^2) time to complete.

Re:An Obvious Fault

[10101001 10101001]

That's not how big O notation works. It's actually defined as:

If O(n log n), then

c*f(n)+k < n log n

defines the worst case scenario for time where c and k are constants and f is the function being used. n is always the number of elements being sorted (for sort algorithms). So, the issue is what k and c are in each of the various algorithms. It might be that c and k are huge for heap/merge sort, but with quicksort as O(n^2), it'd take either a hugely massive c and/or k or really small n for quicksort to always be faster than heap/merge sort.

Of course, as was pointed out, quicksort is more trivially to write, is generally n log n performance, and apparently has a lower c value (IIRC, heapsort has a c of 2). So, people use quicksort even though quicksort isn't guaranteed to always have the best time. Heck, people still use bubblesort (which is fine for really small n's as bubblesort's k is really small). Personally, I'd rather sort algorithms (and gc algorithms) be stuffed into system wide libraries and possibly let an outside function chose which to use; gmp which uses several different methods for doing bignum integer math is a good example of just having a library choose the right algorithm for the job; it'd seem smart to have an equivalent sort algorithm which was based on n and either worst or average case as chosen by the programmer.

Big O Notation

Re:An Obvious Fault

[hding]

Obviously the poster's point was that there are better garbage collection algorithms that do not generally suffer from the original poster's problems, as there are sorts that generally perform better than bubble sort. It was intended to be a tad sarcastic, I'd think.

Sigh. It's not a "feature" of other languages...

[devphil]

...it's required by them.

Stack-based languges like the C family (including Java) don't need GC to operate correctly, but can use it if it's available. (Java just has it all turned on by default.)

By "correctly," I'm specifically leaving out memory leaks. Your program may leak, but it will still run correctly, give the right answers to computations, not suddenly lose track of variables, etc. (Right up until you run out of swap.)

Those "other languages" the author dumps a list of don't use GC just to free the poor programmer from the burden of thinking, or whatever. Nearly every one of those languages either has support for functional programming, or is centered around it. And in functional programming, you're creating functions on the fly.

Which means returning functions as data. Possibly involving local variables in the creating function. Which means that locally-declared variables have to keep existing after the creating function returns, even if the coder can't get to them anymore. And the only way to do that is to have the runtime system manage its own heap, which means a garbage collector.

So for all those languages, it's not an "ease of use" thing. It's a "there's no way for a programmer to do even do it manually at all" thing. GC is the only option.

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

[sfjoe]

...languages dependent on garbage collection have always failed to find much deployment in industrial settings.

Huh? The world's busiest e-commerce websites are largely written in Java. Just what is your definition of "industrial settings"? If you mean that Java isn't used much in a foundry, then I guess you're right.

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.

Re:Under the Rug

[DavidTurner]

Well put!

Another important consideration is that where the programmer has the expectation that his garbage will be cleaned up for him, he will tend to assume that all of his resources will be cleaned up. This is clearly not the case. The seminal example for me was the use of database query result sets in C# - if you don't explicitly close them, they tend hang around, and the next time you try to perform a query on the same connection, you'll as likely as not get an exception. Surprise!

Also, as some other posters have pointed out, not all garbage collection is automatically bad. It works pretty well in Lisp, Scheme, Haskell, and friends. However in the cases of Java and C# it is certainly detrimental, as it disables the only really effective mechanism for managing resources in those languages - destructors.

Perhaps the thing to do is introduce an analogue for Lisp unwind-protect mechanisms. I suggested this a while back on the Java community forums, in the form of having sentry objects with the lifetime semantics of C++ automatic objects. Someone made the suggestion that the volatile keyword could be twisted to serve this purpose.

Re:Under the Rug

[DavidTurner]

Please explain to me exactly how you can implement a resource management system (or regime as you call it) in C++ for, lets say, managing socket connections, that has no equivlent in Java. You are aware of this method, right?

Okie dokie (pardon the bad formatting):

class TCPSocket
{
int handle_;
public:
TCPSocket()
{
handle_ = socket (AF_INET, SOCK_STREAM, 0);
}

~TCPSocket()
{
close(handle_);
}
};

I think you'll find that there's no equivalent to the above in Java.

This may prove to be good reading, if you are interested in learning more.

Re:Under the Rug

[DavidTurner]

Java doesn't have destructors. It has finalizers, but they are called at unpredictable and occasionally awkward times (if at all). This presents a whole new challenge in terms of establishing invariants.

Consider, for example, the case of a mutex. In C++ I can encapsulate the acquisition and release of the mutex in an object (for an example of this, see boost::mutex::scoped_lock at www.boost.org), and know for certain that I will own the mutex object for the duration of the scope of the locking object. This invariant is maintained even in the presence of exceptions, break or continue statements, early returns, or other surprises.

The net effect is that the code is (a) robust, (b) maintainable, and (c) easy to read.

Contrast:

mutex::scoped_lock lock(name_list_update);
if (!should_insert) break;
name_list.insert("Bjarne");

with:

name_list_update.lock();
if (!should_insert) {
name_list_update.unlock();
break;
}
try { name_list.insert("Bjarne"); }
finally { name_list.unlock(); }

Re:Under the Rug

[Spy Hunter]

So we should ignore GC because it doesn't solve all the world's resource problems at once? Your post doesn't provide a convincing argument against the use of GC. Non-portability is a non-issue; only language writers have to worry about that, and it's already their job. The cache-thrashing issue is the only real problem you mention. Generational GC significantly reduces this problem, to the point where the small runtime performance hit (if there is one at all; malloc and free take time too you know) is balanced out by increased programmer productivity (giving more time to optimize if you so desire, or add features if that's what you value more).

Side note: Boost Lambda and FC++ are impressive but ugly hacks with horrible syntax, lots of "gotchas" that make code not work (often related to operator precedence and order of evaluation), and compiler errors from hell. Probably not the best examples of the power of C++. (OTOH, maybe that makes them the perfect examples of the "power" of C++ ;-)

Re:Under the Rug

[arkanes]

Thats pretty cool, but I suspect that the code gets really tangled if you've got a need to lock more than one resource - you'd need chains of closures. It's functionally (hehe!) equivilent to the C++ RAII model, but I think the C++ one is more concise and clear.

On the other hand,it can probably deal with transaction-style locks easier than RAII can - although I've seen a system to handle that that uses RAII objects combined with functors (instead of closures). It works almost identically to the Ruby model.

Re:Under the Rug

[hding]

In Lisp a pretty common way to handle this sort of thing is with a with-some-resource macro (with-open-file is a commonly used built-in). This sort of macro will typically take information for dealing with the resource (e.g. in the file example the pathname of the file, options for opening it, etc.) and the body of code to be executed with the resource; it will then expand to code that acquires the resource and then uses it and releases it (the latter two typically wrapped in unwind-protect to assure the release should there be an exit via a condition or whatnot).

Re:Under the Rug

[arkanes]

Sun is being misleading. You can do that, but it's a lousy idea. Read up on when finalization occurs (the relevant docs were posted in part elsewhere in this thread). Basically, it's run when the object is GCed, not when it goes out of scope (which makes it useless for RAII), and it's not guaranted to be run at all. Finalization is not the same as destruction, and can't be used for the same purposes. Simple as that.

I'll try to clear it up a little more with a better example. Say you're locking a file. In C++, you'd create an object to control the lock.

class locker {
locker() {lockfile();}
~locker() {unlockfile();}
};
function WriteFile() {
locker l;
....
}

The file is locked when the function is entered, and is unlocked when the function is left, no mater how it's left - early return, exception, anything. There is no way to leave that function scope with the file locked. You can't do anything like that with Java, because it has no automatic objects and non-deterministic finalization.

Re:Under the Rug

[Gaijin42]

the using keyword in c# handles exactly this situation.

This code :

using(DisposableObj x = new DisposableObj())
{
x.DoSomething();
}

is equivilent to

DisposableObj x = new DisposableObj();
try
{
x.DoSomething();
}
finally
{
x.Dispose();
}

So as long as the object's author put any "close/release" code into the dispose method, it will get handled automatically when you are done with it.
(Even if an exception occurs!)

Most c# objects that have dispose() also have a close()

For example, databases. You can close() them and then reopen them multiple times. If you call dispose() and the object is open, it closes for you.

(So what, I still have to call dispose manually!)

And thats the purpose of the using(){} syntax. You dont have to remember anymore.

Re:Under the Rug

[Bloater]

Building a nifty little lock management facade *does* make the problem go away. That is precisely the point. The user of that interface cannot even *compile* a program that is not safe with respect to it (Not to say that C++ is any good in other respects, of course).

The only real ways to do this in Java are twofold:

1) Use synchronize, and only return the accessor object if the appropriate monitor is held. Then the accessor object throws an exception for each method if you use it without holding that monitor. But there is no reasonable way to implement a cache within that accessor object. There may be a way with several waiting threads and using notify in a complex way that will probably deadlock - but that is hardly the goal of using an object oriented design.

The problem is that leaving the synchronize block should cause all cached data in the accessor to be flushed to the *real* object - this is often necessary to guarantee performance when the main memory bus is significantly slower than the on-die cache. Furthermore, using a reference to the accessor outside of the synchronize block in which it was created should not only be prohibited - it should be inhibited.

2) Continuation passing style. But to get that inline one define a subclass inline, which means that any access to local variables requires that they be final. That is not always desirable, and frequently undesirable. This *could* be alleviated in Java with some simple changes (such as allowing reference to non-final variables if it can be guaranteed that there will remain no references to the object after return, but it is still quite ugly conceptually.

I also don't believe that the alternative of folding the cache into the real object lazily when another accessor is created is workable without an eccessive level of synchronization, possibly causing immense slowdowns on NUMA architectures.

So while, in C++, the programmer of the interface manages the resources, the interface they produce causes the user of the interface not to have to worry about it. Without that, the user of the interface must be very cautious of their use, and consider far more exceptions. And probably have to take bug reports from end-users that would *not* happen with the C++ method (as long as they don't use "&", see below).

This post is not intended to mark GC as bad, as there *may* be a solution. An object can be explicitly deleted at a given moment by waiting for notification performed in the finalize method - if the runtime guarantees to GC the object early when waiting for that notification. That is, however, difficult to make both safe and strict in Java, since the wait may be a long one, and it can be hard to statically prove that there are no other references, or to inhibit their creation. C++ also cannot utterly inhibit the creation of references to the accessor object that exists beyond its lifetime, but that is a problem with allowing pointers.

An unfortunate choice in C++ is that the register keyword is nothing more than an optimisation hint, while in C it inhibits the address-of ("&") operator.
An unfortunate choice in Java is that references are just C++ pointers with no arithmetic operations - only the "dereference and resolve member" operator "." ("->" from C++) that can throw an exception, "==", and crucially, assignment.

Re:Under the Rug

[hak1du]

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.

For the same reason people in industry have kept programming in Cobol and Fortran, and for the same reason they keep producing software with all sorts of problems, bugs, and limitations.

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

Not true at all. Generational collectors generally achieve far better locality than malloc-style allocators.

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.

Fundamentally, the point behind GC is not to make your life easier, it is to make it possible for the language to be safe. Without GC, a language with heap allocated mutable data structures just cannot be safe. GC generally cannot reliably manage any other resources besides memory and it is not meant to.

Given a resource management regime that can handle all these other important resources, as is commonly practiced in C++, memory becomes just another resource.

But memory isn't just any resource, memory is a resource that can contain machine pointers to other memory (as well as references to other resources).

The problem of resource management for memory is that of arbitrary directed graph reachability. And that is exactly the problem that a garbage collector solves, as efficiently as possible.

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.

C++ solves a common but limited subset of the resource management problem and then just declares victory. And even that false victory is not very satisfying because in order to achieve it, C++ has sacrified runtime safety. (In fact, with that choice, it has also sacrificed efficiency, but you aren't going to believe that no matter what I say.)

Re:Under the Rug

[Pseudonym]

In fact, most programs in those languages never need to manage anything but memory. Academia is like that.

Ah, yes. Any language which isn't procedural is "academia only".

There are many counter-examples, some of which I can't really talk about. Probably the most famous is Erlang, a functional language used to implement highly scalable, fault-tolerant telephone exchanges. Declarative symbolic languages like O'Caml are also widely used in bioinformatics, but somebody will probably dismiss that as "academia", too. (Admittedly, memory is usually the most critical resource that bioinformatics software has to manage.)

Lisp's "with-this-and-that" and C#'s "using" construct also just paper over the hole [...]

Actually, they solve a fairly large proportion of resource management problems. Many resource acquisitions really are scoped. I work writing highly scalable database servers for a living (in C++, incidentally) and I can report that for our domain at least, this is true most of the time.

"Resource acquisition is initialisation" is an extremely good discipline for object-oriented-esque imperative languages, such as C++. Still, you have to remember that in C++, object lifetimes are still scoped! Even those which are stored on the heap are still, when you get down to it, managed by scoped objects. Those which aren't are, when you get down to it, managed manually. In other words, "resource acquisition is initialisation" doesn't free you from manual resource management, it just pushes it to a higher level. Another way to think about this is that it effectively ties related resources together, letting you manage them as an abstracted bundle.

Still, most of the time, outside of "academia", the abstractions still leak. In our database server, for example, you still have to be aware of what locks are held when to avoid deadlock, no matter how much you abstract it. So even if you don't have to write code to manage resources manually, you still have to go through most of the thought processes that you would if you did manage them manually.

Re:Reference Counting...

[bluGill]

One day a novice came to the master and said "I have this great idea for GC, we just count references." To which the master replied one day a novice came to the master and said "I have this great idea for GC, we just count references."

One of my favorite little sayings that applies here. I suggest you look for the original if you haven't seen it, I can't paraphrase it as good.

Circular References

[bcore]

Another flaw of ref counting is that if you have two objects which are no longer referenced by any of the active application, but which have references to each other, they will not get GC'ed, leading to memory leaks. Circular refs alone are just not good enough for any serious application, unless you force the programmer to look after cleaning up circular references, which kinda defeats alot of the benefit of using a GC'ed language.

Re:Reference Counting...

[jonadab]

> Is reference counting really that bad?

Refcounting can't collect everything if you have any circular references. It's
what Perl5 has, and we live with it, but Perl6 is getting real garbage
collection (mark-and-sweep I think, or at any rate something more advanced
than refcounting).

Re:Sigh. It's not a "feature" of other languages..

[jonadab]

> By "correctly," I'm specifically leaving out memory leaks.

What a thing to leave out. Memory leaks are one of the hardest-to-track-down
and most annoying kinds of bugs that we perpetually see in application after
application. Okay, crashes are more annoying and pervasive, sure. And
buffer overruns (which are not a problem in most languages that have GC,
albeit GC is not the reason they're not a problem). But memory leaks are
high on the list.

> And in functional programming, you're creating functions on the fly.

I'm trying to imagine a programming language that doesn't let you create
functions on the fly but is powerful enough for writing real applications.
The only thing I can come up with is that you could write what basically
amounts to an interpreter so that you wouldn't have to write "functions"
in the implementation language but could write them in the interpreted
language instead. But that seems like a really ugly hack, just to avoid
including real memory management in the compiler/interpreter/vm/whatever.

It is possible to get around the need for closures (i.e., anonymous routines
that hold references to otherwise-out-of-scope lexicals), if you have a
sufficiently powerful object system. But again, it seems like a questionable
goal; sometimes closures are really the most convenient way to accomplish
something. (Sometimes they're not, of course... that's why I favour
multiparadigmatic languages.)

> So for all those languages, it's not an "ease of use" thing. It's a
> "there's no way for a programmer to do even do it manually at all" thing.
> GC is the only option.

Strictly *theoretically*, the programmer can do all that stuff in any
Turing-complete language; it's possible to do functional programming in
8086 assembly language, for example, if you're willing to go far out of
your way to do it. But in practice, neither assembly language nor C
really makes that easy or practical, no. But then, there are actually
quite a lot of things that those languages don't make easy or practical.

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.

a way to give the GC a hint?

[Doppler00]

It might be useful if some languages had an optional method of hinting that an object should be garbage collected soon. This would help in languages like Java where you get a huge amount of data stored and then all at once the disk thrashes as it GC everything. For some algorithms, it would be nice to tell Java ahead of time that you're done with the object and you're not going to reference it anymore. The nice thing is though, it wouldn't be a requirement, so you wouldn't have to worry about deleting an object still in use by mistake. I wonder how efficient this would be.

Re:a way to give the GC a hint?

[Nasarius]

Simply doing something like:

foo = null;

is sufficient. If you really want to, you can call the garbage collector manually:

System.gc();

Re:a way to give the GC a hint?

[tcopeland]

> you can call the garbage collector manually

Unfortunately, this doesn't force it to run. From the JDK 1.4.2 Javadocs for System.gc():

Calling the gc method suggests that the Java Virtual Machine expend effort toward recycling unused objects in order to make the memory they currently occupy available for quick reuse.

Note the "suggests". No guarantees...

GC has always been efficient

[hak1du]

however, [manual storage management] can be more efficient in many ways if properly handled. This discrepancy in efficiency has slowed the widespread adoption of the automated approach.

There hasn't been a "discrepancy in efficiency". Good garbage collectors have been comparable to, or better than, manual storage allocators for decades.

The perception of a "discrepancy in efficiency" has several causes:

• Garbage collection allows programmers to get sloppy about storage managmentt: if a non-GC program gets sloppy about storage management, it crashes, if a non-GC program gets sloppy about storage management, it just runs slowly. Unfortunately, as a result, many core libraries in garbage collected languages are pretty sloppily written and slow--the fault is with the libraries, not with garbage collection.
  
• Garbage collection allows language implementors to make different design decisions. Many garbage collected languages will do memory allocation every time you use a floating point number. Imagine how slow C would be if you called "malloc" for every floating point number.
  
• Garbage collection often bundles memory management overhead into single chunks of time, while manual storage allocators don't. Furthermore, garbage collector implementations really rub your nose in it, printing messages like "[starting garbage collection... done]". But doing a lot of storage management at once is usually more efficient overall--in aggregate, manual storage managers spend more time, they just diffuse it out. However, both kinds of behaviors exist with both storage managers, and you can pick and choose.
  

The article is right that garbage collection is a good choice today. It is wrong in that it has pretty much always been a good choice. Garbage collection could have been widely adopted in the 1970's or 1980's, and we would have saved ourselves a lot of headaches and troubles without any loss in efficiency.

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

Feels like

[nate nice]

I feel like I just read a small section in the memory management section of an operating systems or programming languages text book. I'm not sure what to discuss here, no knew ideas were expressed or presented here. Perhaps the author could have postulated new ideas for memory management or suggested how current ideas could be improved. Interesting read if you're a programmer who never really got into the mechanics of a programming language and what certain runtime systems do to make your program work. Then again, I would probably call you a strict-scripter and when scripting you're generally more concerned with expressions rather than mechanics.

Although, the point the author made about CPU's being cheaper and faster and how this is allowing the programmer to care less and less about mechanics so the can make use of this extra power to make programming a more expressive rather than mechanical practice is interesting.

Personally, I see no problem with one day having high level application programmers who know nothing of hex, memory management or physical hardware but rather algorithms, computability and productions, etc. Of course, there will always be a place for the "computer programmer", but also a place for the "analytical abstractionist engineer".

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:The GC pitfall

[StrawberryFrog]

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.

While you are entirely right, this is no differnt from previous generations of programming languages. You always do better if you have a bit of understanding of the wiring behind the board.

I'm sure that there were objections to high-level languages by assembler coders who objected that "there are a lot of C coders who don't think at *all* about the assember generated" and "there are a lot of C++ coders who don't think at *all* about the pointers behind those object refs"

Re:Reference Counting...

[Circuit Breaker]

Reference counting can interact nicely with multithreading on modern (post `96) hardware - most modern CPUs have this nice "compare-and-swap" atomic operation, which can be used to manage refcounts without any form of locking. Yes, it is a little less efficient and a little more intricate, but it's doable; In Windows, for example, it's called "InterlockedIncrement()" and "InterlockedDecrement()".

Also, in many environments you DON'T modify the reference count every time you copy a pointer; there's a concept called "borrowed references" which is used in Python, COM, and many other ref count schemes to avoid some useless refcounts.

Python (pre 2.0) used to do only refcount, and did it much better than Java (using GC) in all respects except thread friendliness. Modern python (2.0 and beyond) does both -- but it's extremely rare for the gc to be needed at all.

Re:Education?

[adamofgreyskull]

There are Godlike Real Programmers and there are sloppy programmers. I don't think that GC will automatically make everyone a sloppy programmer. If it stops some of the sloppy programmers from creating applications with huge memory leaks, isn't that a good thing?

Reference counting

[Antity-H]

It was mentionned earlier that reference counting was pretty good, but had a few drawbacks when it came to cycles and multi-threading.

I took a bit of time to go and read Wikipedia's page

In the description they give, they mention that reference counting GC can represent managed objects by directed graphs.
I know there exists algorithm to find cycles in such graphs. So I suppose these could be applied to this problem. Other proposal are to use a tracing GC to detect them. To which it was replied that this would be able to reclaim the memory but not to properly finalize the objects. I don't see why that would be true. I mean, if you have found a member of the cycle to be collected, can't you just finalize that one and let the whole cycle unravel itself ? If there are cycles inside that cycle, just do it again on these etc ...

As I said, another common objection was the cost of updating the counters in multithreaded environnments. Multiple solutions have been proposed, some more portable than others (using processor/platform specific atomic increments, or deferring the update until it is really necessary and using the standard mutex protection)

All this said, I try to understand a couple of things.
-I am no genius, thus these ideas must not be new, what is the problem which can't be solved with these?
-Reference counting seems to integrate better in the runtime of the program. All the other techniques proposed seem to imply some monolithic operation on the memory summing up all the overheads at on time and doing the cleaning once in a while, with the possibility of becoming a bottleneck in heavily loaded systems. Reference counting OTOH seems to allow the cleanup to continually add a little bit of overhead to the system but nothing which will bring the whole thing to a grinding halt before allowing it to go on. What have I missed?

Relevant references

[hding]

A couple of relevant references for garbage collection are the following website (which unfortunately hasn't been updated for a while - still, it's useful):

The Memory Management Reference

and of course Jones and Lins book, Garbage Collection: Algorithms for Automatic Dynamic Memory Management

Re:Sigh. It's not a "feature" of other languages..

[jonadab]

> > I'm trying to imagine a programming language that doesn't let you
> > create functions on the fly but is powerful enough for writing real
> > applications.
>
> C, C++, Java.

[Scratches Java off list of languages to learn.]

I know C and C++ have been traditionally used for writing applications, but I
have long been of the opinion that they're not really powerful enough for the
job. It takes several times as many programmer-hours as it ought to to do
anything, from prototyping to new feature work to debugging, which IMO means
that "powerful enough" is a real stretch. These languages get by and continue
to be used at this point mostly because a lot of people know them.

In the past, these languages were selected because programmer time was cheaper
than computer resources (with which they're more miserly than a higher-level
language), but that's no longer anywhere near true, as the article points out;
the *average* computer has enough RAM to run three horribly-inefficient
extreme memory-hog applications at the *same time* without needing any swap,
and newer models are coming with more and more. You talk about GC screwing
up virtual RAM algorithms, but it's really not an issue on most systems; if
a process grows to three or four *times* the size it needs to be, it doesn't
actually have any user-noticeable impact on performance. Memory leaks are
actually much worse, because in that case the wasted memory doesn't ever get
collected and eventually it becomes a problem, after a couple of hours of
use. (Actually, a very small memory leak can go for days without being a
problem, but those aren't the ones we notice so much.) In 1996, when most
consumer-grade operating systems were so stable that you had to reboot every
few hours, memory leaks weren't such a big deal (provided you had lots of
swap space), but now that almost any modern OS (and most applications) can
run for weeks and weeks if not months or even years without being restarted,
memory leaks are now a big deal. It's okay to continually use five times as
much RAM as you technically need; it's not okay for your memory requirements
to keep growing as a function of how long you've been running, because that
can get to be *way* more than five times what you need.

Back to creating functions on the fly, I'm just a little bit surprised to
learn that Java doesn't have such an important feature; I had been lead to
believe it was a relatively high-level language with fairly high-level
features. It runs on a virtual machine, for crying out loud; I had imagined
it would be fairly modern and flexible in its design. Are you sure it can't
create functions on the fly, or is that just something you don't know how to
do in Java? That's a pretty serious accusation to level at a language,
almost as bad as saying it can't allocate extra memory on the fly.

Java doesn't have *a* garbage collector

[blamanj]

It has different collectors, which you can select according to the needs of your application. Currently there are two, the default collector (generational) and an incremental collector which is slower but less likely to pause.

Also, the default collector is a 3-generation one, not 2, at least as of Java 1.4.1. More details here.

Re:Sigh. It's not a "feature" of other languages..

[jonadab]

> Any compiled language by definition can't create functions on the fly

This is flat-out false. There are various compiled languages (compiled as
in compiled to native machine code, yes) that not only allow creating functions
on the fly but actively encourage it. Common Lisp is just one example. Yes,
garbage collection gets compiled in. (This is no weirder than compiling a
memory-management library into a C program, and actually being standardized
is an advantage.)

Besides that, the whole compiled-versus-interpreted-languages argument is
getting fairly blurry these days. It's no longer as simple as C and C++ on
the one extreme, which take hours to compile and then run on systems that
don't even have a compiler, and BASIC on the other extreme where you can stop
the program while it's running, change some variables and maybe some lines of
code, and set it running again (possibly at a different line) in-progress
with the state intact. There are all kinds of in-between cases now, Perl
and Java and Python and so on, which technically are both compiled and
interpreted or neither or somewhere in-between. Java runs on a virtual
machine, okay, and Perl6 will, but what do you do with Perl5 and others like
it, which don't really run on a vm per se but have separate compile-time and
run-time phases yet allow more code to be compiled later at run time (through
eval and things like it), ... and then there's JIT compilation... and then
you have compilers that take languages designed to compile to a virtual
machine and instead compile them to native machine code for a specific
platform...

Re:The extreme situations are the only ones ...

[Tom7]

Any application that can tolerate garbage collection is trivial. Thanks anyway -- I'll stick to C and assembly.

Wow, with this attitude I can see why you are worried about keeping your job.
Did you know that GCC uses a garbage collector? They found it too difficult to manually manage memory. Is GCC a trivial application?
In my program we write loads of decidedly non-trivial software all of the time that not only tolerates, but benefits greatly from GC.

Garbage collection is not appropriate for every task, but to assert that all tasks worth doing demand C and assembly is ridiculous.

*sigh*

[Estanislao Mart�nez]

In this OCaml code, the plusx is created "on the fly" and it is different function, depending on the value of x that is read on runtime.

I'm ready to believe you're simplifying this deliberately to illustrate functional programming techniques, but I think the simplification here is confusing.

It's important to keep in mind the difference between code routines and closures. The term "function" as is commonly used doesn't respect this difference. C's "functions" are code routines, while ocaml's are closures, i.e. a pair of a routine and an invocation frame.

What's being "created on the fly" are closures, which are like stack frames (storage for local values of identifiers in an invocation), but which:

1. are allocated in the heap,
2. have a pointer to a "parent" frame (the bindings in the enclosing environment), and
3. have unlimited extent (since the invocation of a closure A might return a closure B whose "parent" is A, requiring that A be kept around indefinitely after the call to it returns).

I think the point the original poster is making can be expressed in another way, but one that's more revealing of what's at stake: stack allocation is a form of automatic memory management.

In any modern language, there is some form of automatic storage management behind the scenes for function-local storage. Imagine if in C, you had to manually allocate the stack frame of any function you called, and every function had to deallocate its frame before returning. This would be tedious and repetitive. Automatic management of a stack of limited-extent frames provides the programmer a simple (but restricted) way of doing this.

It would be possible to have a functional language where the storage for closures was managed by hand. Imagine a language like C except that it allowed you, when you called a function, to specify a heap-allocated binding to be used in the invocation, instead of a stack frame.

This would be similar to the hypothetical C variant from above, where the programmer was responsible for creating and destroying stack frames. But much harder, since closures have unlimited extent. In the stack allocation case, it's clear when the allocations and deallocations need to happen (before the a function is called, and before one returns). In the manually allocated closure language, the programmer would have to figure out on his own the extent of every closure, and when and where it's safe to free them. This is not simply tedious like in stack allocation, but rather devilishly complex in general.

So, garbage collection solves it.

Re:An Obvious Fault [in your post]

[voodoo1man]

I think you mean "mark and sweep" collectors. "Stop and copy" collectors just trace the working set from whatever your heap root is. Add in the copy step, and you only touch twice the size of you working set. If your collector is well-written and the OS provides the hooks, it will ask for the new space to be allocated in core, and the old space to be discarded, wherever it is.