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

Justin Bailey jgbailey at gmail.com
Fri Dec 21 18:40:15 EST 2007

On Dec 21, 2007 2:55 PM, Bertram Felgenhauer
<bertram.felgenhauer at googlemail.com> wrote:

> If you look at the generated machine code, you'll find that f and g
> are identical functions. The sole purpose of the int2Word# and
> word2Int# operations is to satisfy the type checker. (This is
> even true at the core level. The core language is typed, so you
> still need to do the conversions there. No code is generated for
> them though.)

Good to know. They are scary!

> The I# deconstruction has a cost, but with proper strictness annotations
> ghc should optimize those away - check the intermediate Core to see
> whether it actually does.

If I see things like GHC.Prim.Intzh, is that a clue its the "unlifted" type?

> In fact most of the speedup you got seems to come from the use of
> uncheckedShiftL# and uncheckedShiftRL# - just using
>   shiftL, shiftR :: Int -> Int -> Int
>   I# a `shiftR` I# b = I# (word2Int# (int2Word# a `uncheckedShiftRL#` b))
>   I# a `shiftL` I# b = I# (word2Int# (int2Word# a `uncheckedShiftL#` b))
> speeds up the stepWithUArray code by a factor of 2 here, starting with
> the first program at http://hpaste.org/4151.

That is great. I tried your speedup and you are right - just
redefining those makes the "lifted" version faster than the unlifted.
Too bad there isn't an "unsafe" version of the shifts available.


More information about the Haskell-Cafe mailing list