[Haskell-cafe] Understanding allocation behavior

Bulat Ziganshin bulat.ziganshin at gmail.com
Sat Apr 8 04:24:40 EDT 2006

Hello Daniel,

Saturday, April 8, 2006, 4:21:14 AM, you wrote:

> Unless I overlooked something, I use foldBits only via size (though that's
> used a lot).

size of set? there is much faster method - use a table

[0..255] -> number of bits in this number seen as set

then we split Word to the bytes and count total size of set
by adding number of bits set in each byte

foldBits can be made faster (may be) by adding strict annotations:

foldBits :: Bits c => (a -> Int -> a) -> a -> c -> a
foldbits _ z bs | z `seq` bs `seq` False  = undefined

foldBits' :: Bits c => (a -> Int -> a) -> Int -> c -> a -> a
foldbits' _ i bs z | i `seq` bs `seq` z `seq` False  = undefined

moreover, GHC don't inline recursive functions! so foldbits' is out of
luck and it seems that GHC generates polymorphic version that is of
course very-very slow. what you can do?

1. use SPECIALIZE pragma. this allow to make faster version at least
for typical cases (a=c=Int, for example)

2. use recursion on the internal foldbits' function. may be this will
help to inline and therefore specialize each call to foldbits'. it's
better to ask Simon Marlow about this

Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com

More information about the Haskell-Cafe mailing list