Subject: Re: [boost] dynamic_bitset count
From: Vicente Botet Escriba (vicente.botet_at_[hidden])
Date: 2009-03-16 10:52:22
Andreas Klein-5 wrote:
> Dear boost developers,
> I checked the implementation of boost::dynamic_bitset::count
> and find that it uses a table look up.
> This is not optimal.
> First on 64-bit machines divide-and-conquer algorithms are faster than
> table look up and save even memory.
> Second if the bitset contains several words, there are for both 32 and
> 64 bit machines population count algorithms that are faster than
> the simple loop over all words used by boost.
> Together with Y. Edel I developed a new version,which saves 60%
> against the simple algorithm. We put the code online
> (http://cage.ugent.be/~klein/popc.html). A disadvantage of our
> implementation is that we relay on aggressive optimization (-O3) of
> the compiler.
> If you are searching a compromise between speed and code
> complexity. The first iteration of the Harley-Seal-method (25% faster
> than the simple loop) would be a candidate.
> You find this and other population count algorithms on our homepage, too.
> If there is interest I can add one of the advance algorithms in
> Best wishes
> Andreas Klein
> Unsubscribe & other changes:
Please, post on a new thread. Do not replay to existing thread with message
not related to.
-- View this message in context: http://www.nabble.com/Stop-on-first-error-tp22513100p22539926.html Sent from the Boost - Dev mailing list archive at Nabble.com.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk