Re: Faster IntSet by using BitMaps in the lower branches

Hi, Am Montag, den 19.09.2011, 16:03 +0200 schrieb Gregory Collins:

On Sun, Sep 18, 2011 at 11:07 PM, Edward Kmett 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... uses the following:

I use this in hashtables also :)

https://github.com/gregorycollins/hashtables/blob/master/src/Data/HashTable/...

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@joachim-breitner.de | nomeata@debian.org | GPG: 0x4743206C xmpp: nomeata@joachim-breitner.de | http://www.joachim-breitner.de/