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:
> The library dynamic_bitset contains a slow population count procedure:
> 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
> 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
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk