Ronald

Thanks for your program, which had the amazing property that
Hugs runs it 20x as fast as GHC4.05 -O!

The reason turns out to be that you have hit on an optimisation
that Hugs makes and GHC doesn't!   But it is one that I don't
expect to happen often enough to be worth adding to GHC.  I'd
be interested in what others think.

Here's the key function:

runExperiment law dt param init 
  = init : zipWith (propagate dt)(law param stream) stream
  where  
    stream = runExperiment law dt param init

Notice that runExperiment calls itself with *exactly the same 
paramters*.  You could equally well write the function like this:

runExperiment law dt param init
  = stream
  where
    stream = init : zipWith (propagate dt) (law param stream) stream


Now it's explicit that the zipWith consumes the result
of the call to runExperiment.  Indeed, I'd argue that since
the efficiency of the whole program depends *crucially* on
spotting this sharing, the second program is better style
than the first.

As it happens, Hugs transforms the former into the latter
and GHC doesn't.  The reason Hugs does it is to improve
space usage, and it turns out that this is a non-issue in GHC
because tail calls don't allocate.  But in this case, the *whole*
of the call can be re-used, and that is a form of CSE, in this
case a hugely dominant one.  (Mark calls this the 'root
optimization'.)

Keep up the good work

Simon

Reply via email to