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

On Wed, Aug 22, 2018 at 2:03 PM, Evgeny Shulgin via Boost < boost@lists.boost.org> 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?

By a curious coincidence, I have been working in that part of libc++ ;-) You can take a look here: https://github.com/llvm-mirror/libcxx/blob/master/include/bit Gcc and clang have provided the bit intrinsics for a long, long time - since before libc++ cares about. Boost's mileage may vary. The MSVC intrinsics are missing (for my purposes) important things - like "noexcept" and "constexpr". -- Marshall