FW: How to benchmark memory managers?

[I think my last attempt to post this failed, due to a change
in punctuation in my email address.  Apologies for any duplicates.]

I think Emery's and Matthew's measurements provide a very
interesting data point here.  But as with all such measurements,
you have to be careful about over-generalizing from them.
They clearly reflect a particular set of assumptions.
I think the issues you have to be aware of here are:

1) The one that James pointed out: Explicit memory management
often adds other overhead.  Sometimes that's near zero.  But
with a sufficiently bad solution (e.g. unsharing data structures
to preserve unique "owners") in a hard case, it can be
arbitrarily large.  And lock-free parallel algorithms often
become much harder in the absence of a garbage collector.

2) It seems to me that single-threaded or single-processor,
performance-critical applications are in danger of extinction
over the next few years, at least in many domains.  Thus
multi-threaded performance is critical.  For many malloc/free
implementations (though probably not Emery's latest) synchronization
overhead dominates if you are allocating small objects.  For garbage
collectors on the other hand, it is relatively easy to keep it near
zero.  This leads to some other performance measurements like the
ones near the end of
http://www.hpl.hp.com/personal/Hans_Boehm/ismm/04tutorial.pdf
where tracing collection wins by a large margin, at least
with moderate space use.
Based on an earlier email exchange with Emery, I think the
measurements here assume minimal synchronization overhead in
both cases.

3) Some of the measurements are very sensitive to raw tracing rates for the
tracing GC.  This in turn seems to depend to a large extent on
grubby low-level details, and vary by up to an order of magnitude
or so between collector implementations.  My impression is that on current
fast hardware, at least with "easy" benchmarks, tracing rates
should be on the order of 300MB/processor-second or better.
(For our collector and GCBench, I get on the order of 800MB/sec
for GCBench on a dual 2Ghz HT P4 with 4 threads.  That's probably
a near-best-case, given the 24 byte object size, and I'm measuring
just the tracing, not other GC overhead.  I vaguely recall
a statement from someone at BEA with comparable numbers for JRockit.)
An older published number for the Jikes collectors is much lower, but I
don't where they currently fit in.  (This is a bit less critical for
generational collectors, but it still matters.)

Hans

> -----Original Message-----
> From: [email protected] 
> [mailto:[email protected]]On
> Behalf Of James McCartney
> Sent: Sunday, January 09, 2005 6:12 PM
> To: [email protected]
> Cc: [email protected]
> Subject: Re: [gclist] How to benchmark memory managers?
> 
> 
> 
> On Jan 9, 2005, at 5:46 PM, Matthew Hertz wrote:
> 
> >>> We use exact object reachability traces [27, 28] as an oracle to 
> >>> indicate when objects should be deallocated. By implementing this 
> >>> oracle inside a detailed architectural simulator, we can 
> execute and 
> >>> precisely measure unaltered Java applications as if they were 
> >>> written using explicit memory management.
> >> by using an oracle, you eliminate the cost of the explicit 
> management 
> >> that a programmer using explicit memory management would 
> have had to 
> >> implement in order to determine when objects become 
> garbage. Thus any 
> >> cost of explicit destruction or reference counting which 
> may have to 
> >> be done is not accounted for. So I think this methodology 
> is biased 
> >> since it completely eliminates the cost on one side that is being 
> >> counted on the other.
> >
> > As we describe in the paper, the system inserts calls to 
> free whenever 
> > the
> > oracle (object reachability trace) determines that an object can be 
> > deallocated.
> >  Because the programs are run in a simulator, I capture the 
> full cost 
> > of these
> > deallocation calls without adding any overhead for the 
> oracle.  Since 
> > the
> > results in our paper include the full costs of both explicit and 
> > implicit memory
> > management, we stand by our conclusions.
> 
> the cost of free only equals the cost of explicit memory 
> management if 
> none of the objects ever had shared ownership. Otherwise 
> there is some 
> mechanism being hidden by the oracle that is not being accounted for.
> 
>