[gclist] Finalizers & Reference counting.

Thomas F. Burdick tfb@OCF.Berkeley.EDU
Thu, 29 Aug 2002 23:27:03 -0700

Greg Hudson writes:
 > On Wed, 2002-08-28 at 16:47, Reedy,Christopher L. (Chris) wrote:
 > > I'm sure you've seen the e-mail from Linus Torvalds on the GCC mailing
 > > list about reference counting versus garbage collection. For those who
 > > may not have seen it, here is a quote from the e-mail:
 > > >  I strongly suspect that what makes gcc slow is that it has absolutely
 > > >  horrible cache behaviour, a big VM footprint, and chases pointers in
 > > >  that badly cached area all of the time.
 > Linus probably knows more about gcc than I do, but I think spending lots
 > of time in the kernel may have skewed his judgment.  Visible performance
 > problems in the real world almost always stem from algorithms with poor
 > scaling characteristics (O(n^2) or worse, where n is actually growing
 > large).  Not cache locality, not "hot spots" which need to be
 > hand-optimized, not anything like that.
 > Kernel programmers live in a world where cycle-counting optimizations
 > may make sense: every program on the system uses the kernel, so every
 > clock cycle you save in a common system call shaves off a little bit of
 > time for every program anyone runs.  libc programmers live in the same
 > world.  Everyone else should be looking at their algorithms and ignoring
 > the rest.

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.

So I don't think this is necessarily a case of cycle-counting.  If you
have a nice O(n^2) algorithm that because of memory-usage patterns,
performs worse with your actual data sets than an exponential
alternative -- well, it's time to refactor your code so you can
control your locality of reference better.  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.

           /|_     .-----------------------.                        
         ,'  .\  / | No to Imperialist war |                        
     ,--'    _,'   | Wage class war!       |                        
    /       /      `-----------------------'                        
   (   -.  |                               
   |     ) |                               
  (`-.  '--.)                              
   `. )----'