Re: [boost] Population count procedure in dynamic_set

Subject: Re: [boost] Population count procedure in dynamic_set
From: Edward Diener (eldiener_at_[hidden])
Date: 2016-09-28 07:47:33

On 09/28/2016 03:12 AM, Wojciech Muła wrote:
> Hello!
>
> The library dynamic_bitset contains a slow population count procedure:
> https://github.com/boostorg/dynamic_bitset/blob/340822f979371973fe4a84363623a68b984da57d/include/boost/detail/dynamic_bitset.hpp#L106-L125
>
> There are several better, faster and (more or less) portable algorithms.
> Daniel Lemire, Nathan Kurz and I work on a library which provides fastest
> possible implementations for CPU having AVX2 instruction set, you can check
> out its current state: https://github.com/CountOnes/hamming_weight.  I also
> did an extensive comparison of different algorithms on different machines:
> https://github.com/WojciechMula/sse-popcount, one example
> https://github.com/WojciechMula/sse-popcount/blob/master/results/skylake/skylake-i7-6700-gcc5.3.0-avx2.rst
>
> As I mentioned these algorithms are different, the fastest use SIMD
> instructions, other depends on a CPU instruction. However, some approaches
> are portable, machine-independent, like this
> https://github.com/WojciechMula/sse-popcount/blob/master/popcnt-bit-parallel-scalar.cpp
>
> It's possible to provide better solution at small cost, a lot of work
> has already been done.  Would you be interested in including such boosted
> procedures as part of dynamic_bitset (or a new library)?

Yes. If there is a faster method, which is portable, Boost is certainly 
interested in it. If you provide a PR I will certainly look at it.

>  Popcount itself is
> used in number of fields: I've found it in DNA matching (Jaccard index),
> computer vision, databases, and Daniel recently reported application in
> machine learning.
>
> best regards
> Wojciech