Slashdot Mirror

It sounds like it's talking about memory management for external fragmentation. Here is an article that looks like it is talking about those patches. Here is a site that seems to explain memory management pretty well. I could try explaining stuff myself but I'd probably miss some of the nuances (I'm no OS expert by any stretch).

Pros and cons of garbage collection?

If you don't CONS, you never need to collect garbage. *rimshot*

More seriously, GC isn't so much about pros and cons, as it is about tradeoffs between the various GC algorithms: time vs. space, low-latency vs. high-throughput, parallelism, etc.

If you're designing a new language, it should include garbage collection, or nobody will use it (i.e., your target audience can already program in C). You may wish to have multiple GC implementations available for different purposes, perhaps to be selected at compile-time.

For a good overview of what's available, see http://www.memorymanagement.org/

My personal favorite is the good old Cheney semi-space collector (and Ephemeral/Generational Garbage Collectors, which are more advanced versions designed to generally have low latency), as it is very straightforward (both to understand and to implement), compacting (it defragments memory, and can perhaps improve cache locality by grouping related objects), and it has high throughput (work is proportional to the amount of live data, not total data).

If memory usage is of more concern than fragmentation and throughput, a mark-sweep collector may be more your style.

There are also "real-time" (and "soft-real-time", i.e. bounded latency [see Henry Baker's Treadmill]) collectors, parallel collectors [including an interesting case for reference counting, usually considered a dog performance-wise, as a viable parallel/remote GC method], "conservative" collectors for C/C++ (see Hans-J Boehm's libgc), collectors for real and hypothetical computers with special hardware and/or OS support for GC features, and some collectors that are just plain weird.

Note also that garbage collection algorithms are considered hard to measure for performance, especially with regard to wall-time latency, so just because a paper(*) claims that a certain GC has certain performance characteristics, be sure to benchmark if it really matters.

(*) Did I mention papers? If you're serious about implementing GC, getting comfortable reading CS research papers is a must. The book "Garbage Collection" is your best friend here, as it provides a very good overview/survey of said papers and algorithms, and it discusses a lot of pros and cons between various algorithms, and useful variants or adaptations that have been applied to previously-published work.

Also check out Henry Baker's papers, because he is a memory management demigod: http://home.pipeline.com/~hbaker1/home.html.

Garbage collection techology has been dealing with this well for a long time. Read The Memory Management Reference - multiple threads are assumed, and the single-threaded special case merits barely a mention. The "mutator" threads can keep running while garbage collection is going on, too - memory barriers are used to protect against race conditions.

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

To make sure that I wasn't just blowing steam, I did a little bit of looking around, reading some research papers ... I don't have all of the links, but a lot of them were within a few clicks of the so-called The Memory Management Reference website

Well it's hard to argue with no links :). But your point that large objects are easier on a malloc()/free() seems like common sense. It's much more often that you'd write a custom allocator for small objects.

Refcounting is actually expensive, more so than GC. In multi-threaded apps, you have to use an interlocked instruction to update the refcount, or perhaps even make a function call.

Again with the threads?:). Yes, I've heard this argument before, however ... 1) You don't need to do locked refcounting. If you do you are almost certainly sharing too much information between the threads. Locking should not be done "automatically" inside objects. This will almost certainly lead to the threads serializing against each other. 2) GC needs something similar so you can have quick destruction. This is often especially noticable when an app. is written assuming GC, at this point the application will assume that doing "x = new foo();" is just as cheap as "foo x();", then objects of very different lifetimes will be intermixed and the GC needs to know to free the "stack like" objects quickly. For instance python has both a GC and a ref counting system, and this seems to make most people happier.

The function calls to malloc and free tend to blow the TLB and cache almost as effectively as collections. The function calls to specialized allocators often do so as well. The difference is that GC is only called once in a while (relatively), so the TLB and cache are only blown a few times a second instead of every few hundred allocations.

Yes, malloc/free are not simple functions. However I'd disagree that custom allocators can blow the cache. Often the "allocation" happens with a test and two pointer assignments (for instance Vstr does this -- actually one pointer assingment per object, and another for the entire group), and deallocation with just two pointer assignments. I fail to see how a GC could compete with this. In threaded programs this is even more pronounced as you don't have to do any locking.

Then you look at things like filesystems, which have had GC like properties for a long time ... and the ones that are the best at managing space are always the ones that do the most work at allocation time. The filesystems that have been design to "make allocation fast" tend to royally screw up management of the space under a bunch of conditions. And I don't see why GC would be any better at this.

The one paper on stats. that was linked directly from the Boehm C collector was Memory Allocation Costs in Large C and C++ Programs (1994), which is almost 10 years old :(. But I guess Boehm hasn't changed much (although I'm not sure I'd say the same for malloc/free).

This paper doesn't suggest to me that GC is very close to malloc/free, with it being worse in both space and time (perl taking 125% of the time and 275% of the memory). Xfig was the only app. sfaster CPU wise (by 0.3 of a second) and was almost half a MB bigger.

Personal observation also suggests this, as when gcc recently move from malloc/free to using Boehm it got both slower and bigger.

However I would probably be happy to take the hit on some of those packages tested ... mainly due to the fact that they aren't performance sensitive to me.

• If your program requires the allocation and deallocation of a lot of items of specific, predictable sizes, you take cache size and available memory into consideration, and really know what you are doing, you can speed up your program by writing special purpose allocators. However, the papers that I read indicated that in 4 out of 5 cases where special-purpose allocators were used instead of malloc and free, it did little or nothing to improve (and sometimes worsened) the speed of the program, but increased the complexity of memory management. Most modern general-purpose allocators are adaptive and set up lookaside tables for frequently allocated block sizes, and they do almost as good of a job as custom allocators in most cases.
• Using a conservative GC, such as the Boehem GC for C++ (where there is no language support for GC, so the GC actually has to scan the stack and assume that every bit pattern that matches the heap's address range is a valid reference) is slower for programs that allocate mostly large objects, but actually faster than malloc/free if the program allocates a lot of small objects.
• Manual memory management gets slower (more cycles spent making sure you've properly kept track of all of your allocated objects) and more difficult to get right as the application grows in size and complexity. GC doesn't. The more complicated the memory management needs, the more likely that GC will be significantly faster than manual management, even without taking the productivity savings into account.
• If threads are involved, lock contention for the heap becomes a significant factor in program execution time. While GC is not free from this, it doesn't degrade as quickly with increased # of processors.
• Refcounting is actually expensive, more so than GC. In multi-threaded apps, you have to use an interlocked instruction to update the refcount, or perhaps even make a function call. Benchmarks between refcounted apps and GC apps show GC taking a significant lead. Of course, there are optimizations that can help with this (weighted refcounting), but they aren't used a whole lot.
• The function calls to malloc and free tend to blow the TLB and cache almost as effectively as collections. The function calls to specialized allocators often do so as well. The difference is that GC is only called once in a while (relatively), so the TLB and cache are only blown a few times a second instead of every few hundred allocations.
• The locality of reference provided by copying collectors has been shown to speed up execution by a significant factor, often saving more cycles than were spent compacting the heap.

Anyway, that is what I came up with. I don't have all of the links, but a lot of them were within a few clicks of the so-called The Memory Management Reference website. I'm even more convinced than I was before.

However, I agree with you that everything has its place. There are places where GC still isn't appropriate. The GC tends to have a larger initial cost than malloc/free (in terms of both code and initial data requirements), so for very simple systems (embedded computers or bootstrappers for more complex systems) the GC just won't work -- there isn't enough room for a program complicated enough to allow the GC to be worth the initial cost. And while "real-time" GC does exist, it isn't yet good/fast enough to be used in the kernel where interrupt handling has to be done within very tight time constraints -- even though a standard GC implementation would likely have better performance (according to what I've read) than the

An informed comment about GC on Slashdot! Hell just froze over...

old objects referencing new objects is bad for modern GC

If you assume that most new GCs are generational, since then you've got to track those old-gen to young-gen ptrs. But then it's not really "modern", c.f. Ungar 84. (It's also interesting to note that the GC in IBM's production VM is not generational.)

creating temporary objects is no problem

Absolutely. It's simply a pointer-bump to allocate, and it probably never gets copied between semi-spaces (and certainly never promoted).

why would you ever want to have a pool of preallocated objects which get recycled

Totally agree. Your pool (long-lived) is going to get promoted into the old-gen along with its transitive closure, and any time you allocate anything to put into the fields of those objects you're going to have old to young ptrs, i.e. more cardtable work plus more promotion plus more etc.

You'd think that Sun would have some clue about Java...

The people at SunLabs (who wrote the GC) do. Unfortunately, people elsewhere at Sun don't seem to pay them too much attention...

There are a lot more reasons to use 64-bits than just letting programs use more than 4GB of memory:

1. 64-bit machines essentially turn conservative garbage collectors into precise garbage collectors because the chance of pointer misidentification becomes almost vanishingly small with address space so much larger than live memory. The ability to automatically garbage collect all your legacy C/C++ programs is a huge benefit.

2. Programs are now often constrained more by memory bandwidth into the ALU than by processing speed. Using 64-bit operands can help this dramatically.

There are real-time garbage collectors, which are guaranteed to not take longer than a fixed time.

Most modern garbage-collected languages can use generational garbage-collection, which, although not hard real-time, generally avoids long pauses, and is very efficient when much garbage is being generated quickly.

Malloc and free are generally not hard real-time.

Try reading the Garbage Collection FAQ

A good source for starting to address all of your garbage collection questions is Jones & Lins' book, Garbage Collection : Algorithms for Automatic Dynamic Memory Management. Another good source is The Memory Management Reference

It is certainly _a_ way. More on GC? See The Memory Management Reference.

IIRC the following paper details it being done on DEC Firefly processors:

Andrew W. Appel, John R. Ellis, and Kai Li. Real-time concurrent garbage collection on stock multiprocessors. In Proceedings of the 1988 SIGPLAN Conference on Programming Language Design and Implementation, pages 11--20, Atlanta, Georgia, June 1988. ACM Press.