Re: How to benchmark memory managers?

Emery Berger wrote:
> Hi Calum,
> 
> In response to your first question ("are there any standard approaches
> to testing memory managers?"), the answer is yes.
> 
> The experimental methodology used for the evaluation of memory managers
> is now fairly sophisticated. We measure performance across a range of
> benchmark applications. For Java, this includes the SPECjvm98 suite,
> SPECjbb, and a new collection of applications called the DaCapo
> benchmark suite. Studies of garbage collectors present data points for a
> range of heap sizes (generally presented as multiples of the maximum
> "live" size). When measuring collection pause times, it's also standard
> practice to include a "mutator utilization" curve. You can see examples
> of this methodology in recent publications on the subject in PLDI,
> OOPSLA, and SIGMETRICS, among others.
>  
> Now, the methodology I've just described is used for comparing garbage
> collectors to other garbage collectors. It's a different matter to
> compare (relocating) garbage collectors to explicit memory managers
> (malloc/free): as you note, you cannot use relocating collectors as
> malloc-replacements. You also cannot use malloc/free in a language
> designed for garbage collection, since programs in those languages lack
> calls to free.
> 
> If you'd like to see a way around these difficulties, I'd refer you to a
> paper by my student Matthew Hertz and myself. We have developed a
> methodology that gets around these complications, and we have compared
> the performance of numerous garbage collection algorithms to a
> widely-used explicit memory allocator (the Lea allocator). The paper is
> in submission, but there's an earlier technical report version available
> at http://www.cs.umass.edu/~emery/pubs/04-17.pdf.

Thanks, that looks like very interesting and useful work.

I have knocked together a simple GC for my own application, and the 
obvious question was how to measure it.  I need to check if I am 
improving it, and malloc seems like a good reference point.  I am 
interested in how it performs against manual memory allocation, since 
this is a critical question for the direction of programming languages, 
but as you say this cannot be an exact comparison.

So I knocked up a simple test-suite that creates various data structures 
(trees and lists) of various sizes, and also intersperses this with 
"chaff" (I am sure you have a technical word for this) representing 
short-lived temporaries.  The intention is that this models real 
application behaviour, but unfortunately I don't have the time to 
implement a plug-in for a JVM.  I wonder how it would do in your test?

My results are here: http://visula.org/gc

What I found from benchmarking my GC was that there was a single metric 
that determined the GC's performance relative to malloc.  That metric 
was % live data.  When % live data was 50% or less, my GC outperformed 
malloc.  When the % live data was above 50%, malloc was better.

Regards,
Calum

> regards,
> -- emery
> 
> 
>>-----Original Message-----
>>From: [email protected] [mailto:[email protected]]
> 
> On
> 
>>Behalf Of Calum Grant
>>Sent: Monday, January 03, 2005 1:39 PM
>>To: [email protected]
>>Subject: [gclist] How to benchmark memory managers?
>>
>>I am in the process of writing a garbage collector, and would like a
>>good test-suite for benchmarking it.  I would also like to compare its
>>performance with other memory managers, such as malloc.
>>
>>Are there any standard approaches to testing memory managers?  I can't
>>use it as a malloc-replacement in real applications since it requires
>>marking and relocation which is not easy on opaque binary data (unless
> 
> I
> 
>>go the way of Boehm et al, but that is not the design of this
> 
> collector).
> 
>>I've put together a few simple test cases, allocating a few million
>>objects in some simple data structures, but they just don't seem to be
>>realistic enough.  I want to be able to say "n% faster/slower than
>>malloc on xyz" with confidence.
>>
>>Calum
> 
> 
>