This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Faster compilation speed

On Sat, 10 Aug 2002, Daniel Berlin wrote:
> > 
> > "So what about circular data structures? Refcounting doesn't work for
> > them".  Right.  Don't do them.  Or handle them very very carefully (ie
> > there can be a "head" that gets special handling and keeps the others
> > alive). Compilers certainly almost always end up working with DAG's, not
> > cyclic structures. Make it a rule.
> Sorry, there are cases that make this impossible to do (IOW we can't make 
> it a rule).

Hmm. I can't imagine what is there that is inherently cyclic, but breaking 
the cycles might be more painful than it's worth, so I'll take your word 
for it.

Things like data structure definitions (which clearly can be cyclic thanks
to pointers to themselves) can often be resolved trivially with nesting
rules (ie if you can show that the lifetime of type A is a superset of the
lifetime of B, then you don't actually need to refcount a backpointer from
B to A).

For the obvious example that I can think of (ie just a structure
definition containing a pointer to itself - possibly indirectly via other
structures), that type lifetime nesting is inherent in the C type scopes,
for example. For type X to have been able to contain a pointer to type Y,
Y must have had a larger scope than X, so the pointer from one type
structure to another never needs refcounting in a C compiler.

(This, btw, is why I don't believe in automated GC systems - even if they
use refcounting internally. It's simply fairly hard to tell a GC system
simple rules like when you need to ref-count, and when you don't.  If you
just always ref-count on assignment, you _will_ get the obvious circular
references, simply because you miss the high-level picture).

But other cases might certainly be much more painful, so I certainly agree
with you:

> But another option is to do what Python does.
> Have a reference cycle GC that just handles breaking cycles.
> Run it explicitly at times, or much like we do ggc_collect now.
> Reference cycles can only possibly occur in container objects, so you 
> only have to deal with the overhead of cycle-breaking there.

Nothing says you can't mix the two approaches, no. If the subset of
allocations you need to worry about from a GC standpoint is relatively
small, the cache efficiency advantages of refcounting clearly don't
matter, and the disadvantages can be disproportional.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]