Faster IntSet by using BitMaps in the lower branches

Joachim Breitner mail at
Mon Sep 19 14:25:18 CEST 2011


Am Sonntag, den 18.09.2011, 18:46 -0400 schrieb Edward Kmett:
> 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.

I’m not sure how to cleanly select the right implementation inside
Data.IntMap. Also, we have architectures with 31 bit words (s390, at
least). If anything, then the functions ought to move into the Bits type
class and into GHC.Word. There it makes also more sense to select
architecture-specific implementations, e.g. the primitive operation on

> 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.

The order is unfortunately relevant, and I am not sure I have a use for
an arbitrarily ordered fold.


Joachim "nomeata" Breitner
  mail at  |  nomeata at  |  GPG: 0x4743206C
  xmpp: nomeata at |

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part
URL: <>

More information about the Libraries mailing list