Faster IntSet by using BitMaps in the lower branches

[Edward Kmett]

On Sun, Sep 18, 2011 at 5:20 PM, Joachim Breitner
<mail at joachim-breitner.de>wrote:

> Hi,
>
> Am Sonntag, den 18.09.2011, 17:11 -0400 schrieb Edward Kmett:
> > I should have mentioned. This function asumes that the input n is not
> > equal to 0.
>
> that is fine, that is in invariant that holds for my bit array.
>
> But I guess we’d need to use CPP magic to separate bitness – my code
> uses whatever "Word" means. Or does it work gracefully on 32?
>
> How about adding it to Data.Word (then I don’t feel responsible for
> getting it fast and can just use it :-))
>
>
You can use a smaller DeBruijn multiplication table to handle 32 bits, but
the one that I gave puts the answer in the most significant 6 bits of a 64
bit word, so if you use it with a 32 bit word, they'll be setting bits you
don't have and all answers will be 0.

Also, if you don't care about the particular order in which you visit the
bits you could store the bits in a different order in the Word(64) than you
would if you just set them directly by preshuffling them. I was able to
derive the following operations, which move the repeated lookups out of the
fold:

magic = 0x07EDD5E59A4E28C2
offset = 58

preshuffleTable :: UArray Int Word8
preshuffleTable = listArray (0,63)

[63,0,58,1,59,47,53,2,60,39,48,27,54,33,42,3,61,51,37,40,49,18,28,20,55,30,34,11,43,14,22,4,

62,57,46,52,38,26,32,41,50,36,17,19,29,10,13,21,56,45,25,31,35,16,9,12,44,24,15,8,23,7,6,5]

preshuffle :: Int -> Int
preshuffle n = fromIntegral (preshuffleTable ! n)

setShuffled :: Word64 -> Int -> Word64
setShuffled w n = setBit w (preshuffle n)

testShuffled :: Word64 -> Int -> Bool
testShuffled w n = testBit w (preshuffle n)

clearShuffled :: Word64 -> Int -> Word64
clearShuffled w n = clearBit w (preshuffle n)

-- NB: the bits do not come out in order!
foldShuffledBits :: (Int -> a -> a) -> a -> Word64 -> a
foldShuffledBits f z 0 = z
foldShuffledBits f z n | t <- n .&. negate n = f (fromIntegral (shiftR (t *
magic) offset)) (foldShuffledBits f z (xor n t))

unshuffleTable :: UArray Int Word8
unshuffleTable = listArray (0,63)

[1,3,7,15,31,63,62,61,59,54,45,27,55,46,29,58,53,42,21,43,23,47,30,60,57,50,37,11,22,44,25,

51,38,13,26,52,41,18,36,9,19,39,14,28,56,49,34,5,10,20,40,17,35,6,12,24,48,33,2,4,8,16,32,0]

I can derive a similar magic, offset and preShuffle table could be derived
for 32 bits, I just haven't needed it.

The caveat is that you'd get the bits out in the wrong order for toAscList,
but if you are concerned with the performance of foldBits it may be a win in
other areas and you can loop and test shuffled bits for when you really do
need the values in ascending order.

-Edward
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110918/b47295c6/attachment.htm>