Re: [boost] dynamic_bitset count

Subject: Re: [boost] dynamic_bitset count
From: Jeff Flinn (TriumphSprint2000_at_[hidden])
Date: 2009-03-18 10:50:11

Andreas Klein wrote:
> Hello.
> 
> 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
> boost.
> 
> Best wishes
>      Andreas Klein

How do these compare with the bit count algorithms at:

http://graphics.stanford.edu/~seander/bithacks.html

Jeff