[Haskell-cafe] Optimizing cellular automata & the beauty of unlifted types

[Justin Bailey]

On Dec 20, 2007 7:42 PM, Sterling Clover <s.clover at gmail.com> wrote:
> I'm curious how much of the unboxing helped performance and how much
> didn't. In my experience playing with this stuff, GHC's strictness
> analyzer has consistently been really excellent, given the right
> hints. Unboxed tuples are generally a win, but GHC was often smarter
> at unboxing ints than I was.

It really did help. I started with an implementation that used Ints,
and this sped the program up by at least 2x. I think that's because of
the bit-manipulation I'm doing. For example, Data.Bits defines the
bitwise and operation on Ints as:

  (I# x#) .&.   (I# y#)  = I# (word2Int# (int2Word# x# `and#` int2Word# y#))

Which you can see has 3 conversions in it. The I#
deconstruction/construction is also suspicious to me, but I don't know
if there are performance costs there or not. Regardless, using Word#
directly lets me write (assuming w1# and w2# are already words):

  w1# `and#` w2#

Maybe better rewrite rules in the Data.Bits library would eliminate
unnecessary conversions and this wouldn't be necessary/

> Also, higher-order functions can be used
> fine, assuming they're not awful recursive, as long as you set GHC's
> unfolding threshold high enough. You can also manually force their
> inlining, to really get control. I found there tended to be a "sweet

I didn't know about unfolding, and I'll have to try that sometime. I
found that inlining seemed to have negative affects as often as it did
positive. I spent most of my time so far coming up with different
algorithms - now that I've got a decent one, I'll have to play with
inlining.

> spot" for any given program, where much higher or lower would degrade
> performance. As far as removing the word2int# and soforth, you could
> probably just use words throughout?

I try to. I just couldn't figure out how to write a Word# value
literally. For example, eqWord# compares Word# values. But this gives
a type error:

  1# `eqWord#` 1#

I have to write

  int2word# 1# `eqWord#` int2word# 1#

> Also, as we discovered the other week, you may want to be careful
> with bang patterns, as forcing strictness on already evaluated values
> takes some time. Although, SPJ did point out that this was
> significantly improved in the new GHC.

Good point, thanks.

Justin