Faster IntSet by using BitMaps in the lower branches

[Joachim Breitner]

Hi,

Am Montag, den 19.09.2011, 16:03 +0200 schrieb Gregory Collins:
> On Sun, Sep 18, 2011 at 11:07 PM, Edward Kmett <ekmett at gmail.com> wrote:
> > There are some neat tricks you can use using deBruijn multiplication to
> > optimize finding the least significant set bit.
> > My geometric coalgebra code
> > in https://github.com/ekmett/algebra/blob/master/Numeric/Coalgebra/Geometric.hs#L72
> > uses the following:
> 
> I use this in hashtables also :)
> 
> https://github.com/gregorycollins/hashtables/blob/master/src/Data/HashTable/Internal/CacheLine.hs#L273

hmm...

-- only works with 32-bit values -- ok for us here
firstBitSet# :: Int# -> Int#

That’s why I feel uneasy about this method. But now we have already
three users of a firstBitSet function, all of which had to re-implement
the wheel. This is really a strong argument for putting this as a method
into Data.Bits and the code into GHC.Word, where machine-specific
instructions can be used if found to be faster.


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/

-------------- 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: <http://www.haskell.org/pipermail/libraries/attachments/20110919/1a6b89dc/attachment.pgp>