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

From: John Maddock (jz.maddock_at_[hidden])
Date: 2019-07-12 07:38:34

On 11/07/2019 18:04, Neill Clift via Boost-users wrote:
>
> 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;
>
> }
>
If you're writing platform/compiler specific code anyway, you could rely 
on the fact that uint128_t will have an even number of limbs, and 
reinterpret_cast the limb pointer to a pointer to uint64_t's and have 
things still work - for performance reasons multiprecision does this 
internally when initializing from a type twice the width of a limb.  
There are also typedefs:

boost::multiprecision::detail::limb_type, and 
boost::multiprecision::detail::double_limb_type.

Which could help here.

Aside: adding a native population count function might well be a useful 
addition to the library...

> 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?
>
The limb size is always half the width of the largest compiler supported 
integer type - this is a necessary condition to implement arithmetic 
entirely within the language.

So on GCC we have __int128 and so the limb size is 64-bits, but on msvc 
there's nothing wider than a 64 bit integer type, so the limbs are 32 bits.

If clang-win can have __int128 support enabled, then defining 
BOOST_HAS_INT128 will activate it's use and you'll get 64-bit limbs in 
general, though in this specific case boost::uint128_t will become a 
thin wrapper around unsigned __int128 (ie will have only one limb).  Of 
course in this specific case, if you have unsigned __int128 then you 
don't really need Boost.Multiprecision unless it's to ensure portability 
of the program to platforms without that type.

> 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.
>
Well I'm always open to suggestions for performance improvements, but 
there's not much low hanging fruit in the bitwise operations which are 
pretty simple on the whole.

BTW I'm not sure they help here, but there are a few operations like 
lsb/msb which use compiler intrinsics on msvc should they help.

HTH, John.

> Thanks.
>
> Neill.
>
> Sent from Mail <https://go.microsoft.com/fwlink/?LinkId=550986> for 
> Windows 10
>
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> https://lists.boost.org/mailman/listinfo.cgi/boost-users

---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus