[Haskell-cafe] Re: Performance Help

Dominic Steinitz dominic.steinitz at blueyonder.co.uk
Mon Mar 19 05:56:20 EDT 2007


Thanks.

> Fusing the ws is trickier. Directly appealing to the fibonacci-number
> example is not recommended because this would mean to keep the last 16
> ws in memory and shifting them right to left by hand. But as the

Are you saying this because we don't want a 16-tuple?

> "Alternate method of computation" on the website suggests, you can
> delegate the shifting to an index that shifts around mod 16. Having a
> mutable array is helpful, then.

Are you saying that because haskell doesn't really have mutable arrays, this 
is ruled out?

> Of course, you can also fill a large static (boxed!) array of 80 Word8s via
>
>   ws :: Data.Array.IArray.Array Int Word8
>   ws = accumArray 0 (0,80) (curry snd) $
>        zip [0..15] xs ++ [(i, xxor i) | i<-[16..80]]
>       where
>       xxor i = ws ! (i-16) `xor`
>            ws ! (i-3) `xor` ws ! (i-8) `xor` ws ! (i-14)
>
> or something like that (I didn't care about correct indices and bounds).
> GHC can fuse such array accumulations.

Why is an array better than a list? Is it because (!) is O(1) and (!!) is 
O(n)?

>
> In general, keeping stuff in lists is not wrong, but ByteStrings are
> more adapted to current CPU and RAM architecture.

I'm not clear how ByteStrings help here. We need to put bits into 32 words and 
operate on these.

Dominic.




More information about the Haskell-Cafe mailing list