Subject: Re: [boost] dynamic_bitset count
From: Jeff Flinn (TriumphSprint2000_at_[hidden])
Date: 2009-03-18 10:50:11
Andreas Klein wrote:
> Sorry for multiple posts. Hopplfully I got I now right.
> 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
How do these compare with the bit count algorithms at:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk