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

Subject: Re: [boost] [dynamic_bitset] Using of GCC built-in functions may increase performance of some methods
From: Andrey Semashev (andrey.semashev_at_[hidden])
Date: 2018-08-22 21:16:46

On Wed, Aug 22, 2018 at 10:03 PM, Evgeny Shulgin via Boost
<boost_at_[hidden]> 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<value_to_type<(bool)mode> *>(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