Re: Faster compilation speed [zone allocation]

Re: Faster compilation speed [zone allocation]

[Robert Dewar]

<        Because the problem is not the garbage collection, its the
allocation pattern.  The proposal to use reference counting allows GCC to
switch to an allocator with better locality -- it's a requirement for the
underlying improvement, not a fix unto itself.
>

But removing garbage collection entirely certainly gives some information.
Another way of examining is to compile on a machine with a large level 2
cache, and watch the compilation time vs size of thing being compiled.

Re: Faster compilation speed [zone allocation]

[Lynn Winebarger]

On Thursday 15 August 2002 14:02, Robert Dewar wrote:
> <        Because the problem is not the garbage collection, its the
> allocation pattern.  The proposal to use reference counting allows GCC to
> switch to an allocator with better locality -- it's a requirement for the
> underlying improvement, not a fix unto itself.
> >
> 
> But removing garbage collection entirely certainly gives some information.
> Another way of examining is to compile on a machine with a large level 2
> cache, and watch the compilation time vs size of thing being compiled.

      Someone might try instrumenting the GC so you can see where memory
is getting allocated and (roughly) how long its living.  It would require
looking for return addresses and then correlating those
with some debugging information. 
    Then there'd be something substantial to argue over.

Lynn

Re: Faster compilation speed

[Michael Matz]

Hi,

On Wed, 14 Aug 2002, David Edelsohn wrote:

> |> 	Places where GCC could benefit from spacial locality is by
> |> allocating the instruction list and pseudo registers from a large, static
> |> virtual memory array instead of allocating individual objects dynamically.
>
> Andreas> Obstacks?
>
> 	I thought that obstacks are created dynamically, not statically.

Sort of.  Obstacks have the ability to grow an object which isn't yet
finalized, and in that process there might be some copying (the canonical
example is a string, which is created character by character).  After
finalization it doesn't change it's address anymore, but still is part of
that obstack.

One would not use that functionality, but simply use obstacks as
convenient containers for small objects, which are allocated already
finalized.  It allocates memory in blocks, and then gives out part of the
current block as long as enough is free in it, and the request is not
larger than a certain size (in which case it gets it's own block).  This
makes for extremely fast allocation (just a pointer increment in the
general case).  One can't deallocate objects in an obstack (or better only
all objects allocated after a certain one).  And it creates good space
locality, and needs less memory then a general allocator like malloc (in
case many small objects are allocated).

But that one can't free objects is a quite severe limitation (I wrote one
for KDE, in which you can free objects, but it has certain restrictions).
But it's still usable.  E.g. I use an obstack in the new register
allocator to allocate most of my small objects from it (nodes and edges of
the graph), and then simply free the whole thing once at the end of that
phase.  But that's not possible e.g. with the current RTL of the function,
there you really don't want to use an obstack.

> One does not want to ever copy or grow the array.

As explained, this doesn't happen if one uses the obstack without growing
objects.

> Statically allocating some of the large, persistent, sequential
> collections of objects would help locality.

This would lead to the idea of obstacks (without growing obstacks) per
data structure type, IOW to a zone allocator, which is not a bad thing.


Ciao,
Michael.

Re: Faster compilation speed [zone allocation]

[Per Bothner]

Michael Matz wrote:

Re: Faster compilation speed [zone allocation]

[Aldy Hernandez]

>>>>> "Per" == Per Bothner <per@bothner.com> writes:

This is just an idea, why doesn't someone hack the GC to never
collect, and then we can really find out how much is to be gained by a
refcounter, or no GC at all, etc.

Why go down this path, if we're not even sure it'll improve anything
(well, that much anyhow).

Aldy

Re: Faster compilation speed [zone allocation]

[David Edelsohn]

>>>>> Aldy Hernandez writes:

Aldy> This is just an idea, why doesn't someone hack the GC to never
Aldy> collect, and then we can really find out how much is to be gained by a
Aldy> refcounter, or no GC at all, etc.

Aldy> Why go down this path, if we're not even sure it'll improve anything
Aldy> (well, that much anyhow).

	Because the problem is not the garbage collection, its the
allocation pattern.  The proposal to use reference counting allows GCC to
switch to an allocator with better locality -- it's a requirement for the
underlying improvement, not a fix unto itself.

David

Re: Faster compilation speed [zone allocation]

[Lynn Winebarger]

On Thursday 15 August 2002 13:39, David Edelsohn wrote:
> >>>>> Aldy Hernandez writes:
> 
> 	Because the problem is not the garbage collection, its the
> allocation pattern.  The proposal to use reference counting allows GCC to
> switch to an allocator with better locality -- it's a requirement for the
> underlying improvement, not a fix unto itself.
> 
   GCC's GC promotion of poor locality of reference is not proof that
reference counting is the only way to improve that locality of reference.
It doesn't matter what allocation/reclamation scheme you switch to, if it's
not used in a way consistent with the cases it optimizes for, it's going to
stink.  There's just as much reason to believe there's a generational GC
that will do what you need as to believe reference counting will be some
kind of magic bullet (without the brittleness).
   
Lynn

Re: Faster compilation speed [zone allocation]

[David Edelsohn]

>>>>> Lynn Winebarger writes:

Lynn> GCC's GC promotion of poor locality of reference is not proof that
Lynn> reference counting is the only way to improve that locality of reference.
Lynn> It doesn't matter what allocation/reclamation scheme you switch to, if it's
Lynn> not used in a way consistent with the cases it optimizes for, it's going to
Lynn> stink.  There's just as much reason to believe there's a generational GC
Lynn> that will do what you need as to believe reference counting will be some
Lynn> kind of magic bullet (without the brittleness).
   
	Let me correct my sloppy wording.  What I meant by "it's a
requirement for the underlying improvement" is that it is a dependency for
that particular proposal -- RC is a means to an end, not an end unto
itself.  There are many ways to address the locality problem.

	I am trying to encourage people participating in this discussion
to stop fixating on the garbage collector itself.  Somehow when GC is
mentioned, people obsess on the garbage collection process without reading
the entire discussion.  If there is interest in discussing garbage
collectors, there are other mailinglists on that specific topic where the
pros and cons of various styles with and without hardware assistance are
debated.

David

Re: Faster compilation speed [zone allocation]

[Michael Matz]

Hi,

On 15 Aug 2002, Aldy Hernandez wrote:

> This is just an idea, why doesn't someone hack the GC to never
> collect, and then we can really find out how much is to be gained by a
> refcounter, or no GC at all, etc.

To switch off GC doesn't necessarily bring anything, except that GC isn't
done.  But the allocated memory still has the same locality as before
(i.e. if it's the reason for bad performance now, that will still be the
case if we switch off GC).  I.e. it wouldn't proove anything.


Ciao,
Michael.

Re: Faster compilation speed [zone allocation]

[Kai Henningsen]

matz@suse.de (Michael Matz)  wrote on 15.08.02 in < Pine.LNX.4.33.0208152037200.13269-100000@wotan.suse.de >:

> On 15 Aug 2002, Aldy Hernandez wrote:
>
> > This is just an idea, why doesn't someone hack the GC to never
> > collect, and then we can really find out how much is to be gained by a
> > refcounter, or no GC at all, etc.
>
> To switch off GC doesn't necessarily bring anything, except that GC isn't
> done.  But the allocated memory still has the same locality as before
> (i.e. if it's the reason for bad performance now, that will still be the
> case if we switch off GC).  I.e. it wouldn't proove anything.

Well, it might prove that the bad locality isn't *caused* by running the  
collector. (Or that it is, of course.)

MfG Kai

Re: Faster compilation speed [zone allocation]

[Per Bothner]

Aldy Hernandez wrote:

Re: Faster compilation speed [zone allocation]

[Kevin Handy]

Aldy Hernandez wrote: