Faster IntSet by using BitMaps in the lower branches

[Edward Kmett]

Probably the simplest version is

magic = 0x07EDD5E59A4E28C2
offset = 58

lsbTable :: UArray Word64 Word8
lsbTable = 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
   ]

foldrBits :: (Int -> a -> a) -> a -> Word64 -> a
foldrBits f z 0 = z
foldrBits f z n | t <- n .&. negate n = f (fromIntegral (lsbTable ! shiftR
(t * magic) offset)) (foldrBits f z (xor n t))

swapping to

lsbTable = listArray (0,31) [0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20,
15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5,
10, 9]

magic = 0x077CB531

offset = 27

for the 32 bit case.


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