Re: garbage collector pauses, help?

From: rif (rif_at_mit.edu)
Date: 01/03/04 

Date: 02 Jan 2004 23:27:41 -0500

Ray Dillinger <bear@sonic.net> writes:

> rif wrote:
> >
> > Ray Dillinger <bear@sonic.net> writes:
> >
> > > Gareth McCaughan wrote:
> > > >
> > > > Ray Dillinger wrote:
> > > >
> > > > > Yes. With appropriate optional declarations, Lisp code usually
> > > > > generates machine code that runs within 5% of the speed of comparable
> > > > > C code (and on many problems, actually runs faster). And you can
> > > > > decide which code to decorate with optional declarations on the
> > > > > basis of profiling. Even without declarations, it's rarely less
> > > > > than 85% as fast as C when compiled.
> > > >
> > > > These numbers are better than I've seen with CMU CL, though
> > > > I haven't done extensive testing, and CMU CL is generally
> > > > reckoned one of the faster implementations. Where do they
> > > > come from?
> > > >
> > >
> > > These numbers *are* what I've seen with CMUCL. I've been using it
> > > to do genetic algorithms to find optimal players of turn-based games.
> > >
> > > I got 85% of the speed of my C code, then gave it type declarations
> > > and watched it pop up to 98% of the speed of my C code. Virtually no
> > > time is spent in the Garbage Collector.
> > >
> > > What numbers would you consider typical?
> > >
> > > Bear
> >
> > I do a lot of numerical work in CMUCL --- mostly signal processing and
> > machine learning. Very heavy on floating point computations.
> >
> > Without declarations and inlining, I find that I typically get
> > programs that're 10 times or more slower than a similar C program.
> > Doing all my arithmetic generic, and needing to box up the result of
> > every function that returns a floating point, gives me programs that
> > are way too slow, even compiled. Once I add declarations, I feel like
> > I can usually get within 50% or so of C. Then I usually have to do
> > another round of optimization (if I care about making the program
> > faster), focussing on avoiding excessive consing, and that usually
> > gets me to within 25% or so. These numbers are all somewhat rough
> > estimates.
> >
>
> Interesting.
>
> My GA code is essentially a translation of my C code - so I'm not
> using higher order functions like map, and as it happens I do just
> about no consing at all once the population of genomes is initialized
> - the "loser" in each contest is overwritten by an offspring of one
> or both of the two "winners".
>
> Suppose the speed difference comes down to the fact that I have been
> looking at something that's not, after all, written in a very lispy
> style?
>
> Bear

That seems pretty reasonable.

For me, one of the real advantages of CL is that I find that
programming in a functional style often leads to programs that have
fewer bugs. More specifically, I find I'm often presented with a
signal that needs to go through various modifications, filters, etc.
The "natural" way for me to write this in CL is to have each
processing step generate a new copy of the array. In C, I'd be more
likely to overwrite at every step.

The CL approach leads to very flexible programs, because if I find
later that I need a given step for a couple of different purposes (I
want to use a given array as input to a new step, and also sum over it
to compute its energy), I don't have to be as careful about
understanding when in the program the array contains the information I
want.

The downside is that I do a lot more consing. But then, once the
program's working, if this is really the problem (and often it isn't,
often the program is fast enough, and then I really win, because I was
able to write it much faster), I go through and make various steps in
the algorithm start "sharing" arrays. But usually this is pretty
easy, especially with the macros I have.

Really, I should make a higher level abstraction for doing this kind
of thing that automatically deduces when a given array can be written
over and when I need to cons up a new one...

Cheers,

rif