[Haskell-cafe] Program optimisation

[David Roundy]

On Fri, Apr 20, 2007 at 07:01:32PM +0100, Andrew Coppin wrote:
> I have *no idea* if this is an appropriate place to put this, but here
> goes...

Sure.

> Next, I read the GHC manual. Apparently there's a command-line switch
> "-O2" which makes GHC try harder to optimise the program. (I had
> stupidly assumed it always tries to make good code...) The result? The
> program now does the same job in 30 seconds. That's quite a big speedup
> just for typing 3 characters! (Gee... I wonder what it does differently?
> I did notice that the compilation time went from 5 seconds up to 20
> seconds. And the *.exe got smaller.)

This is standard behavior for compilers.

> Right, that seems to be no-op. Next I replaced lists with immutable
> boxed arrays. New runtime: 33 seconds.
> 
> Ooops. Now, I would have thought an array would make the GC's life
> *much* easier by replacing tens of thousands of cons cells with one nice
> big array. But, apparently, no. The profiler output says GC is almost
> identical. Hmm... weird!

The compiler is pretty smart about lists.  As long as you're doing simple
things with them (e.g. mapping), odds are pretty good there won't be any
intermediate cons cells generated (this is called deforestation).  In
contrast, no such optimization is available (yet) for arrays.  Every time
you create a new array, it needs to actually be created.

> Finally, in a fit of desperation, I changed it to *unboxed* arrays. For
> some reason, you can't have an unboxed array of complex numbers. So I
> had to make *two* unboxed arrays of doubles, and manually split/join
> myself. Similar problems happened elsewhere too. Suffice it to say, my
> program is now vomit-inducingly ugly. It doesn't even *function*
> correctly any more! (There's a byte alignment issue somewhere... I can't
> track it down.) New runtime: 15 seconds.

Indeed, unboxed arrays are much nicer, but the whole Array batch of the
standard library is pretty useless, in my experience.  You can roll your
own relatively easily using ForeignPtr, similar to Data.ByteString, but
that's a bit of a pain.

> I will mention that the ByteString module was the only thing I would
> find in all of Haskell for doing binary I/O. The final (fast) program
> uses an IOUArray Int Word8 to do the binary I/O instead. (What's the
> difference BTW? Is there one? Other than the name anyway.) Perhaps part
> of the speed was in avoiding an array type conversion? I don't know.
> Certainly this is the messiest part, and the part where I suspect my bug
> is hiding.

Binary IO is definitely an issue with Haskell.

> Finally, in the fast version, quant8 uses way less CPU (more like 50%),
> and the complex number math uses much more. Really goes look like the
> profiler being counterintuitive to me...

Profilers are always counterintuitive in any language.  (Okay, not quite
always, but pretty much whenever you actually need a profiler.)

> A short program synopsys:
> 
> module Main where
> 
> init_frame :: [[Complex Double]]
> 
> next_frame :: [[Complex Double]] -> [[Complex Double]]
> 
> process :: [[Complex Double]] -> [[Colour]]
> 
> save_file :: FilePath -> [[Colour]] -> IO ()
> 
> main = do
>  work 0 init_frame
> 
> work n xss = do
>  save_file ("Frame" ++ show n) (process xss)
>  if n < 500
>    then work (n+1) (next_frame xss)
>    else return ()

If you want actual help, you'll have to supply something more than this.
You could cut out the actual "work", and just post some code that does the
framework.  My guess (and you should have tested this) is that the runtime
won't decrease much if you cut out the actual work (or replace it by
something simple, like taking a exponential of everything), and the result
would be that we'd be able to do more than commiserate.

What happens if you cut the save_file from the process? Far better than
profiling is checking by hand the actual removal of code from the program,
as profiling has a tendancy to disable optimizations.  You did run your
timings with profiling disabled?

You've got three potentially expensive functions here (process, save_file
and next_frame), and it'd certainly help to have some idea which is the
bottleneck.

Due to lazy evaluation (less of an issue with unboxed arrays), you do need
to be careful when removing bits of code, as this could cause other bits of
code to not actually be run (e.g. if you never print the output, it might
be that the next_frame is never evaluated, so you might need to print just
the last frame, or compute the sum of each frame and print that).
-- 
David Roundy
Department of Physics
Oregon State University