Re: Locality problems caused by size based allocation?

[Jeff Sturm <jsturm at one-point dot com>]

On Mon, 16 Dec 2002, Daniel Berlin wrote:
> This leads me to believe that our locality problems might actually be
> caused by the fact that we use size based allocation, which has
> basically no locality whatsoever in gcc.

Interesting.

What exactly is "size based allocation"?

> I also, based on a offhand suggestion by zack, made a ggc-boehm.

I've done this also...

> It works (though it fails if you have it collect whenever ggc_collect
> is called, even if i tell it it's not safe to collect without me
> explicitly calling the collection function. It also fails in a few
> cases. We must be hiding pointers somehow),

Yes.  IIRC I found two places where the backend hides pointers.  One is in
cse_basic_block:

  qty_table
    = (struct qty_table_elem *) xmalloc ((max_qty - max_reg)
                     * sizeof (struct qty_table_elem));
  qty_table -= max_reg;

> and is faster than ggc-page
> with size allocation, running the same speed as the copying collector
> and the non-size allocating ggc-page (garbage collection times are much
> faster, too).

I didn't see that.  I found no better than a 5% improvement (measured as
wall-clock time) using my ggc-boehm, no matter how I tuned it, with
generational collection enabled or not.

Anyhow I didn't find the results interesting enough  to continue the
experiment.

> It obviously doesn't collect as much garbage as the accurate collectors
> (roughly half as much, in fact).

I very much doubt that.  Pointer misidentification is certainly common
with a conversative collector, but 50% lossage is quite rare.  And if
that were happening you'd see plenty of blacklisted pointers (unless all
messages are suppressed, as with -DSILENT).

How are you measuring free space?  GC_get_total_bytes (for instance) isn't
very accurate; it doesn't count pages waiting to be swept or free lists.

Jeff