[gclist] Finalizers & Reference counting.

[David Chase]

At 11:27 PM 8/29/2002 -0700, Thomas F. Burdick wrote:
>Well, as someone who's currently working on a compiler, I can say that
>locality of reference can be a big performance issue.  My primary goal
>is to compile code correctly, with the close-secondary goal being to
>provide the best optimizations using algorithms of acceptable
>complexity.  Because of the first goal, if I see a range of
>implementational strategies, I'll tend towards the easiest to verify
>and maintain.  Unfortunately, this sometimes leads to polynomial-time
>algorithms that should be good, but whose constant factors are bloated
>too far by a combination of cache misses, and (help me) swapping.

What optimizations are you using?  This is straying a bit from GC,
but if you use some factored representation for your data flow (e.g.,
SSA) most of the optimizations (*) themselves run pretty fast.  I can't
say much for their locality, but memory is finally cheap (about $200/Gb
for PC133 w/o ecc) so at least you can deal with the swapping problem.
To make optimization expensive, you'd need to be working in a really
twisted framework (that is, you'd need really deep lattices -- strictness
analysis, trying to infer multi-level pointer aliasing, that sort of
thing).

Register allocation and scheduling are typically the big pigs.  Be
sure you use good algorithms, be sure you bound the size of your
inputs (e.g., break up big blocks, confine your attention to regions
of code no larger than N nodes and spill around them).

(*) dead code elimination, code motion, constant/type/bounds
propagation, reduction in strength, pattern-matching

>I'm working in Lisp, where it's been pretty easy to do this
>when I've needed to; I don't envy the gcc maintainers their task.

Gcc is a special case.  Other compilers have been written in C
and Java that don't seem to have the problems that it does.

David Chase