Re: [boost] [dynamic_bitset] Using of GCC built-in functions may increase performance of some methods

On Wed, Aug 22, 2018 at 10:03 PM, Evgeny Shulgin via Boost wrote:

Hi all, when I was playing around the Boost.DynamicBitset library, I noticed the last lines of the count() function (which returns the number of bits in the bitset that are set):

return do_count(m_bits.begin(), num_blocks(), Block(0), static_cast *>(0));

Well, this line was modified 10 years ago last time.

Let's go deeper. GNU C provides several language features not found in ISO standard C. These include a bunch of bit operations - you can look at them here: https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html. For example, *__builtin_popcountll *counts the number of bits in an 'unsigned long long', so we can use this kind of code to calculate bits (don't judge, I wrote this fast and didn't think of coding standards):

size_type res = 0; for (size_type i = 0; i < m_bits.size(); i++) { res += __builtin_popcountll(m_bits[i]); }

I checked that m_bits[] and popcount() both work with 64-bit values on my machine. It halved the running time of a program that has a bitset and calls count() over and over again - here's the code https://gist.github.com/Izaron/5005fed4184ee6483699191dc5ef3677 I used. These __builtin_XXX functions can be used everywhere where it's possible, with preprocessor directives. Or is it actually used and longer time means something else? I used the latest version of Boost.

I think such an optimization would be useful. Note that MSVC also has intrinsics for popcount[1], although I don't think those are supported when the target CPU doesn't implement the corresponding instructions. You would have to check at compile time whether the target CPU supports it (e.g. by checking if __AVX__ is defined). I think, Boost.DynamicBitset is community-maintained. If you create a PR, someone from CMT will take a look. [1]: https://msdn.microsoft.com/en-us/library/bb385231.aspx