Speeding up GC

[David S. Miller]

   From: loewis@informatik.hu-berlin.de (Martin v. Löwis)
   Date: 03 Jun 2002 15:25:05 +0200
   
   Does this approach have a chance of speeding up GC? What do you think?

One problem with your idea is that this would make the
mark list for each page more complex.  Currently it is
a single bitmap with one bit per object allocated from
that page.

A page can (currently) contain objects of various types.
Trees, RTL, and various other things can all reside within
the same page.

To implement your idea would likely be more expensive than
the GC walk itself.  That is, unless someone can come up
with some fantastic implementation I haven't thought of.

A more pressing problem, which I am working on, is that GCC
allocates a HUGE number of throw-away objects.  Ie. things
allocated then immediately never referenced again.  The two
major classes of such objects are:

1) SEQUENCE rtl for holding generated insns

   This is the part I am working on right now.  We emit
   ton of these things, especially when splitting insns.
   And the current "optimization" in gen_sequence which
   tries to avoid emitting the SEQUENCE causes the INSN
   to be dropped, so we end up emitting two INSNs instead.

   This stuff is so dumb and I hope I can finish up my
   patch before I next go to sleep.

2) "Can I do this?" type RTL generation.  Often we generate
   RTL just to see if creating a particular kind of
   expression is possible.  We do this a lot.  One example
   of this is "product_cheap_p ()" in gcc/loop.c

All of these are bad because they fragment GC pages, so if
you look at pages at various points in time you'll see a layout like
this:

   ... some other objects ... | dead SEQUENCE | ... | dead SEQUENCE

That dead SEQUENCE ties up the whole page from being used for other
orders.  It also thus makes GC's working set of pages larger than it
needs to be.

The next order of buisness is locality, as noted by Richard Earnshaw
and others.  GC makes for horrible locality in the RTL.  One way
to deal with this is to create an obstack like allocator from the
GC pages.  Currently each page is for allocating objects of a certain
power of 2 size.  In the obstack-like GC allocator, all objects of
a certain class (for example, long term RTL) get carved out of a
single page.  This hopefully can bring back the locality properties
of obstacks and the benefits of GC at the same time.  I have a
work-in-progress patch which I'll get back to after my patch which
kills of gen_sequence() as described above in #1