[multiprecision] Getting the best performance on windows for uint128_t etc

From: Neill Clift (NeillClift_at_[hidden])
Date: 2019-07-11 17:04:16

Hi,
I develop a program for generating optimal addition chains. I normally use 64 bit integers but in order to attack some conjectures I compile up my program with boost using uint128_t.
In order to get some functionality I need I used the backend access to limbs. For example I need population count/hamming weight/binary digit count. I did this like this:

static
LPTYPER
bits(NTYPE n)
/*++

Calculates the number of 1 bits in a number.

--*/
{
                LPTYPER b = 0;
                std::size_t size = n.backend().size();
                boost::multiprecision::limb_type* p = n.backend().limbs();
                for (std::size_t i = 0; i < size; i++) {
                                b += (LPTYPER)__popcnt64(p[i]);
                }
                return b;
}

I use the same sort of logic to calculate Floor(Log2(n)) (number of largest bit set), to clear the bottom say b bits of an integer.
Is this a reasonable (though probably not idea) way to go?
I noted that the limbs are 32 bits on Windows and this leads me to my second question. How can I get the internals of boost using bigger chunks like 64 bit?
It seems I need a compiler supporting __int64. I have access to the intel compiler (19) and MSVC but neither seem to change this. I tried LLVM but that seemed quite slow. I may not have put enough effort into investigating LLVM up to this point.

Various bit operations seem overly slow in boost. For example I use sequences like this:

                                Control &= Control + 1;
                                Mask = ((Control - 1) ^ Control) >> 1;
                                Control |= Mask;

These seem to be bottlenecks under boost. That sequence above is meant to generate masks that straddle the first run of zero bits in control so 1010100000111111_2 produces a mask of 11111111111_2.
Thanks.
Neill.

Sent from Mail<https://go.microsoft.com/fwlink/?LinkId=550986> for Windows 10