Locality problems caused by size based allocation?

[Daniel Berlin]

On Tue, 17 Dec 2002, Jeff Sturm wrote:

>
> 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"?
What ggc-page does, which is segregate objects based on size rather than
age or object type.

This doesn't work well for RTL, for instance, where you have 3 (or was it
2 or 4, i forget which) sizes of RTL, so size allocation guarantees that
in a linear walk of RTL, you'll end up moving across all different
random pages.


> > > 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.

What version were you using?

Also, I also have a few tests where locality matters quite a bit,
otherwise you'll completely trash the caches.

>
> Anyhow I didn't find the results interesting enough  to continue the
> experiment.
Nor did I. It crashes in some of my testcases (we must be hiding pointers
or something).

>
> > It obviously doesn't collect as much garbage as the accurate collectors
> > (roughly half as much, in fact).
>
> I very much doubt that.
I'm going by.

  Pointer misidentification is certainly common
> with a conversative collector, but 50% lossage is quite rare.

Not in gcc.
  And if
> that were happening you'd see plenty of blacklisted pointers (unless all
> messages are suppressed, as with -DSILENT).

You do.
100's of k worth.

>
> 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.
I'm measuring *used* space before and after collection.
Not free space.
And I do it with gc_get_heap_size() - gc_get_free_bytes () before and
after a collection.
IE size of heap - number of bytes free in the heap.
I also looked at the stats output to make sure, and it wasn't collecting
much in most collections, which jived with the 50% (it's actually worse in
a lot of collections i'm being nice).

For example, on one test case, we go from
22404k -> 21540k in the first collection, and the stats on stderr say it
only collects ~1 meg of garbage (IE the numbers match).

ggc-page and ggc-copy go ~20meg -> ~4.9 meg (ggc-page is 21142k -> 4973k).





>
> Jeff
>
>