Faster IntSet by using BitMaps in the lower branches

[Edward Kmett]

The usual mechanism would be to just bundle a pair of foreign functions and
a fallback purely functional implementation.

I'll see about packaging up a Data.Bits.DeBruijn module somewhere with few
if any dependencies.

-Edward

On Mon, Sep 19, 2011 at 8:25 AM, Joachim Breitner
<mail at joachim-breitner.de>wrote:

> Hi,
>
> 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
> x86.
>
> > 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.
>
> Greetings,
> Joachim
>
>
> --
> Joachim "nomeata" Breitner
>  mail at joachim-breitner.de  |  nomeata at debian.org  |  GPG: 0x4743206C
>  xmpp: nomeata at joachim-breitner.de | http://www.joachim-breitner.de/
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110919/2c03fb73/attachment.htm>