Re: [boost] dynamic_bitset count

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
> boost.
> 
> Best wishes
>       Andreas Klein
> 
> 
> 
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
> 
> 

Please, post on a new thread. Do not replay to existing thread with message
not related to.

Thanks,
Vicente
-- 
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.