Boost logo

Boost :

Subject: [boost] Population count procedure in dynamic_set
From: Wojciech Muła (wojciech_mula_at_[hidden])
Date: 2016-09-28 03:12:47


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: I also
did an extensive comparison of different algorithms on different machines:, 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)? 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, gregod at, cpdaniel at, john at