Faster IntSet by using BitMaps in the lower branches
ekmett at gmail.com
Mon Sep 19 18:02:55 CEST 2011
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.
On Mon, Sep 19, 2011 at 8:25 AM, Joachim Breitner
<mail at joachim-breitner.de>wrote:
> 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 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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Libraries