Lambda the Ultimate

Doesn't this paper simply show that garbage collection needs to be better informed?

It's one thing to compare explicit and automatic collection language by yanking the free calls and using GC instead. In this case, though, it looks like they generated the free calls mechanically rather than by hand. If that system is far superior, irrespective of whether the fault is virtual memory, the implication is that GC needs better static analysis tools and instrumentation. Not to say that the interference of virtual memory itself is a trivial result; rather, that the seeming result of "virtual memory causes problems" is supplanted by the possible interaction of "we can't get away with the simple approximation we were using before."

I don't have time to dig through any details until after finals, so this may just be an indication that I need to read the paper.

How does the memory consumption of the paper's simulation of manual memory management relate to the memory consumption of actual manual memory management? The paper argues that actual manual memory management would use less memory, because they are waiting to the last possible moment, just before the object becomes unreachable.

This is unconvincing because the manual version might leak, depending on the input. Fixing the leak could involve rewriting the program, with a deallocation point late enough to be valid on all input, and an earlier/wider allocation point/scope to make sure that the object remains reachable all the way to final deallocation. Now the memory consumption is higher than in the simulation.

The naive way to do this research is to rewrite a garbage-collected program using manual memory management. The authors note that this would be arduous. When I was writing signal processing code in C I was able to cheat by writing small programs that did not free the memory that they allocated. I stitched them together with shell scripts and let the operating system reclaim the memory as processes exited and were started afresh. The memory consumption of programs with manually managed memory allocation is the product of a trade-off. If you push too hard at minimising memory usage you will end up with bugs. Refusing to discuss this trade-off fudges the the question of what the paper is actually about.

The authors have done a fine piece of work. Their 'magic' deallocator does a lot better than standard garbage collection. On its own this raises various interesting questions. Is there still a big advantage compared to generational garbage collects? Can one write a code analysis tool that statically computers the location of the 'magic' deallocations? I think the answer is obviously not, but this obvious answer misses the point. The authors have put a worthwhile performance improvement into play. Can one write a code analysis tool that statically captures half the possible improvement on actual code bases?

Unfortunately the authors phrase their paper as relevant to manual programming practise.

It would be possible (though onerous) to attempt to measure it by manually rewriting the benchmark applications to use exmplicit deallocation, but we would somehow have to factor out the impact of individual programmer style.

Well, no, one step at a time, please! It would be interesting to know whether any programmer can rewrite the benchmark applications to capture the performance gains that their research hints might to obtainable. Once you have established whether it can be done at all, one might go on to automate it or to teach it.

When porting our visualization software from C++ to OCaml we noticed that, although the average performance was degraded by ~20%, the worst case performance improved over five fold. That was largely due to OCaml's GC spreading deallocations over time whereas our C++ code suffered from avalanching destructors. As a soft real-time application, this is important for visualization, of course: the C++ code jerked noticeably.

So I would be interested to see worst case performance profiles as well as averages or totals.

We're porting our code to F# now, so it will also be interesting to see whether or not the GC in .NET provides the same benefits that OCaml's does.

I asked them at the presentation and one thing they overlooked is the fact that the actual machine code to do the explicit free() calls is not actually in the machine code of the application at the deallocation site. They use their instrumented simulator to "magically" decide to execute the explicit free call at a particular deallocation site, which means they actually do simulate the instructions of the free call, but that call's effect on the surrounding code is not captured (e.g. greater register pressure, larger code size, I-cache effects).

The effect is probably small in most cases (I would guess less than 1% execution time), but it still gives a slight advantage to the explicitly managed version.

Overall I think the authors did a really outstanding job controlling for as many variables as possible.

There is always that last one though.....

This paper has been around a while, and has been used to attack yours truly on my opinion that garbage collection is often given a bad rap. I'm certainly not an expert here, but I take issue with a number of the assumptions made in this paper. I have two primary concerns.

First, the paper assumes that tracking objects is free. They inserted calls to free() exactly where the object became unreachable. The running program paid no price to track the objects. This is not a reasonable assumption. In most non-GC programs I've seen, a huge proportion of the code goes to tracking the reachability of objects. The tracking code uses both CPU cycles and memory resources. Finally, the tracking code is not oracular and often does not release an object exactly when it is no longer referenced by anything outside of the tracking code.

Second, the paper uses garbage collection technologies that are now significantly out of date. Not all GC is created equal. For example, the .NET generational collector has many mitigations in place that address some of the specific concerns raised by the paper. The generational approach has been shown to significantly reduce the amount of time spent collecting garbage in typical programs, yet no modern generational collectors were measured by this paper.

I'm not going to claim that GC is free. There are times where it is simply not (yet?) appropriate. There are times when the program's allocation patterns are better suited to explicit memory management. But there are also times when GC ends up being significantly better (in terms of performance or memory usage) than explicit memory management, i.e. in situations where heap fragmentation is a problem, a coalescing GC can improve both performance (due to improved cache hit rates) and memory usage (due to reduced heap fragmentation).

The work done by Hans Boehm, while dated, seems to be more even-handed. He also used garbage collection mechanisms that are a bit outdated (the issue was forced due to the use of a conservative collection strategy), but even so he found that the systems using GC were only a bit slower than the equivalent systems using explicit memory management.

Anyway, just my 2c.

First, I am quite honored to see such a debate going on about this little work. There are many issues to pick with the paper, several of which have been discussed here. Neither Emery nor I expected this paper to end this debate, there are too many variables for that. But we realized that my trace generation work (Merlin) provided a unique opportunity to provide another data point and exploit any insights this provided.

Like all research, we could not investigate everything. We tried selecting the most commonly cited algorithms (concurrent & .NET algorithms would be great, but I did not have access to a system that could have run them in the necessary harness; my thesis included BC and a few algorithms we pruned due to a lack of space). We tried to include as much as we could in our accounting and state our methodology clearly so that people could decide whether these results would actually apply to specific environments. Given this very interesting discussion, I feel like we did a good job. I just hope others do to.

A few specific answers to questions raised so far:

* While we did not introduce leaks into the malloc-free runs, the reachability-based oracles left in place all the leaks from objects remaining reachable but unused. The liveness-based oracles freed objects after their last use (e.g., fixing all leaks) and led to a fair space reduction, but almost no difference in execution time. I think adding leaks would be interesting, but could be hard to do in a reproducible manner.

* We do as much as we can to account for the costs of freeing data. Because we insert calls to free() only where there already exists a similar call, we should see most of the calls costs (including some of the added register pressure since many get used otherwise). Since our analysis is not static, locations may not always call free() each time they are executed; we would somehow need to split these to get the full costs (which would modify the run and invalidate our traces).

* We ultimately decided to not modify the program run for the malloc-free runs. This does mean that we only pay for the object tracking costs that the program itself performs for GC purposes (which, in the case of the SPEC benchmarks whose code I could see, is actually fairly reasonable). I think the paper highlights that, unless memory is an issue, GC is a reasonable choice for performance (and a clear win once software engineering is included).

Anyway, I really think this conversation is very interesting and am always glad to see my work discussed here. Thanks!

A while back I did some experiments with using the Unix process model
and the explicit resource freeing after exit worked as a garbage
collection system for C programs. The programs were meant to be short
lived and no explicit free'ing was done do any allocated memory due to
the fact that the kernel will return all allocated resources in on
fell swoop during the process cleanup phase. This seemed like it
would lead to efficiency gains overall since the kernel was doing a
'large grain' cleanup/deallocation (of memory pages) rather than
explicitly freeing each object during runtime.

I have since lost the results, but I can recall that the system did
take longer to cleanup processes that had allocated a greater amount
of memory, which is in line with the behaviou8r of a general garbage
collector, plus it greatly simplified the actual code, mostly due to
the style writing very small "function" programs that could be tied
together with shell script and pipes (which is how unix was meant to
be used in the first place).

The point of this was that Unix and C both do have garbage collection
when used together; you just have to learn to program in a certain
type of way to use this feature. One of the main detractors of shell
script is the cost of fork/exec'ing each process, but if major parts
of the operating system (process resource reclamaition) weren't being
ignored by the user level programs, I have a feeling that this
overhead could be balanced out.

Programs written in this way are easier to write (less code, book
keeping), easier to understand (shorter) and are potentially more
efficient (letting the OS doing the work it's supposed to). This
looked to me like a feature of Unix that most C programmers miss and
seems to be closer to the 'functional' style of programming that most
imperative languages miss.