[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Created attachment 57345
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57345&action=edit
Use 64-bit integers to do 128-bit arithmetic

This patch defines a custom type that implements the necessary 128-bit
arithmetic for linear_congruential_engine<uint64_t, ...> without __int128.

It's an order of magnitude slower than using __int128 natively on x86_64, but
it gives the right results.

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Lewis Fox from comment #0)
> libc++'s
> implementation of linear_congruential_engine (though libc++ incorrectly uses
> Schrage's method).

I haven't checked what libc++ actually does, but it gives consistent results
for -m32 and -m64. However, apart from the first one, its results don't match
what libstdc++'s.

Libstdc++ and Boost give the same results:

864691128455147579
20120904253298372
499698276788149646
1283859513473858339
2211358525164835637
1565794316594927048
433037752037085551
3876224293909804757
842334705173512733
614226679431558764
3068544072891686009
780734117187050918
1963664848033545542
3791874062716605653
366668634810437006
1377239172204792920
1808622055437870614
464217244571328665
2604268511046649463
2831603438105397950
3223716036697852745
784694016100218461
1453099037541982349
2259076772827085306
2590915097279144408
3831773502251465123
320081643915990134
2376324005742734684
2037587339862127157
893313058057432898
118956510249458009
973816490706440657
2982490375421836301
1236945357523402079
3905294429470053119
2304284986302062495
2454379621599061616
1553811809817066890
2904663527490058979
2904663527490058979
2904663527490058979
2904663527490058979
2904663527490058979
2904663527490058979
2904663527490058979
etc.

Libc++ gets stuck  oscillating between two values right away:

864691128455147579
1965622972376959002
4035225266123976763
1965622972376959002
4035225266123976763
1965622972376959002
4035225266123976763
1965622972376959002
4035225266123976763
1965622972376959002
4035225266123976763
1965622972376959002
4035225266123976763
1965622972376959002

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Based on that, I'm not sure what libc++ does is actually better than what
libstdc++ does today (i.e. refuse to compile if the results would be wrong).

I think the patch above would make sense though. I'm sure it could be
optimized, I was more concerned with getting the results right than with
performance.

The first loop in operator% could just be a single left shift by the difference
in the number of leading zeros between __l and __x. And halve() should just be
a right shift (and "halve" isn't a reserved name).

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #1)
> Created attachment 57345 [details]
> Use 64-bit integers to do 128-bit arithmetic
> 
> This patch defines a custom type that implements the necessary 128-bit
> arithmetic for linear_congruential_engine<uint64_t, ...> without __int128.
> 
> It's an order of magnitude slower than using __int128 natively on x86_64,
> but it gives the right results.

            if (__builtin_uaddll_overflow(__l._M_lo, __c, &__l._M_lo))
              __l._M_hi++;

Why not just
            __l._M_hi += __builtin_uaddll_overflow(__l._M_lo, __c, &__l._M_lo);
and similarly for subtraction?
Is the reason for using the clang compat builtins instead of
__builtin_{add,sub,mul}_overflow the compatibility with clang versions which
don't
support these?

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #57345|0                           |1
        is obsolete|                            |

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Created attachment 57346
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57346&action=edit
Improved operator%

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #4)
> Why not just
>             __l._M_hi += __builtin_uaddll_overflow(__l._M_lo, __c,
> &__l._M_lo);
> and similarly for subtraction?

No good reason - I'll change it.

> Is the reason for using the clang compat builtins instead of
> __builtin_{add,sub,mul}_overflow the compatibility with clang versions which
> don't
> support these?

Again, no reason, I was just using the ones specific to the type because all
the types are fixed.

Thanks for the suggestions.

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #57346|0                           |1
        is obsolete|                            |

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Created attachment 57347
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57347&action=edit
With Jakub's suggested changes

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
            if (!__l._M_hi)
              {
                __l._M_lo %= __m;
                return __l;
              }
            auto __n = __l._M_hi ? __builtin_clzll(__l._M_hi)
                       : 64 + __builtin_clzll(__l._M_lo);
So, on the __n initializer you already know that __l._M_hi is non-zero, no need
to test it again.  Sure, the compiler will optimize it, but the shorter the
method in the header the better.

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Oops yes!

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
As discussed on IRC, probably the
if (!__builtin_mul_overflow(__l._M_lo, __x, &__lo))
optimization isn't a good idea, because most likely the compiler will in that
case
expand that to a full 64x64->128 multiplication plus testing that the upper 64
bits are or aren't zero, so computing everything this function needs and doing
it again if there is overflow, without possibility to query what it computed.

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #10)
> As discussed on IRC, probably the
> if (!__builtin_mul_overflow(__l._M_lo, __x, &__lo))
> optimization isn't a good idea, because most likely the compiler will in
> that case
> expand that to a full 64x64->128 multiplication plus testing that the upper
> 64 bits are or aren't zero, so computing everything this function needs and
> doing it again if there is overflow, without possibility to query what it
> computed.

Though, if it is common enough, one could try to optimize the __ll[0] == 0 &&
__xx[0] == 0 case, one can do then either 32x32->64 or 64x64->64 multiplication
and be done with it.  But if it is rare in random's usage, it would just make
the code larger.

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[lrflew.coll at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #12 from Lewis Fox <lrflew.coll at gmail dot com> ---
(In reply to Jonathan Wakely from comment #2)

My original comment about libc++ was in reference to the LLVM bugzilla report
#27839: https://bugs.llvm.org/show_bug.cgi?id=27839

It looks like the issue you discovered is LLVM bugzilla report #34206:
https://bugs.llvm.org/show_bug.cgi?id=34206

It seems like since I made that comment here, libc++ has updated to fix the
misuse of Schrage's algorithm (though, looking at the current source code, it
still looks wrong to me), so it does mean my initial comment is a little out of
date.

Either way, though, this issue wasn't in comparison to libc++, but rather that
libstdc++ seems to contradict the C++ standard. For reference, MSVC doesn't
have a native 128-bit integer type, but still handles these correctly by using
64-bit integer arithmetic (though MSVC could still optimize their
implementation for x86_64 using intrinsics if they wanted to).

This is a bit of an edge case that I don't think most users will encounter, so
performance is probably less important here than accuracy. I'd personally
prioritize minimizing branches (i.e. improving simplicity) than optimizing the
operand sizes for performance, but that's just my opinion.

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #13 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #11)
> Though, if it is common enough, one could try to optimize the __ll[0] == 0
> && __xx[0] == 0 case, one can do then either 32x32->64 or 64x64->64
> multiplication and be done with it.  But if it is rare in random's usage, it
> would just make the code larger.

We will only use this new type when the calculation a*(m-1)+c doesn't fit in 64
bits, and the input values should be uniformly distributed in [0,m) for a good
choice of parameters (and for a bad choice of parameters, you have bigger
problems than the calculation being slow!)

For a small value of a and large value of c we would use this new type but the
multiplication step would overflow infrequently, but I don't think that's a
good choice of parameters and not worth optimizing for.

So I think we should just use the full 64x64 multiplication unconditionally.

For operator% the if (__l._M_hi == 0) branch is probably worth it, because the
general case is so much more expensive.

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Lewis Fox from comment #12)
> (In reply to Jonathan Wakely from comment #2)
> 
> My original comment about libc++ was in reference to the LLVM bugzilla
> report #27839: https://bugs.llvm.org/show_bug.cgi?id=27839

Thanks, that got copied to github as
https://github.com/llvm/llvm-project/issues/28213

> It looks like the issue you discovered is LLVM bugzilla report #34206:
> https://bugs.llvm.org/show_bug.cgi?id=34206

And that is now https://github.com/llvm/llvm-project/issues/33554

> It seems like since I made that comment here, libc++ has updated to fix the
> misuse of Schrage's algorithm (though, looking at the current source code,
> it still looks wrong to me), so it does mean my initial comment is a little
> out of date.

Unsurprising when it took me more than 5 years to look into it properly ;-)

> This is a bit of an edge case that I don't think most users will encounter,
> so performance is probably less important here than accuracy.

100% agreed

> I'd personally
> prioritize minimizing branches (i.e. improving simplicity) than optimizing
> the operand sizes for performance, but that's just my opinion.

Agreed again, for although as I said in comment 13 I think the extra branch in
operator% might be worthwhile. Maybe with __builtin_expect(__l._M_hi == 0, 0))
as a branch prediction hint.

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #15 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:c9ce332b557bb95987d038d98ea929cdfd1eae1d

commit r14-8998-gc9ce332b557bb95987d038d98ea929cdfd1eae1d
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Feb 7 11:31:10 2024 +0000

    libstdc++: Use 128-bit arithmetic for std::linear_congruential_engine
[PR87744]

    For 32-bit targets without __int128 we need to implement the LCG
    transition function by hand using 64-bit types.

    We can also slightly simplify the __mod function by using if-constexpr
    unconditionally, disabling -Wc++17-extensions warnings with diagnostic
    pragmas.

    libstdc++-v3/ChangeLog:

            PR libstdc++/87744
            * include/bits/random.h [!__SIZEOF_INT128__]
(_Select_uint_least_t):
            Define specialization for 64-bit generators with
            non-power-of-two modulus and large constants.
            (__mod): Use if constexpr unconditionally.
            * testsuite/26_numerics/random/pr60037-neg.cc: Adjust dg-error
            line number.
            * testsuite/26_numerics/random/linear_congruential_engine/87744.cc:
            New test.

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #16 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:7f3d900684ad989164114f25eb46a33871c6533d

commit r14-9028-g7f3d900684ad989164114f25eb46a33871c6533d
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Feb 7 11:31:10 2024 +0000

    libstdc++: Fix FAIL: 26_numerics/random/pr60037-neg.cc [PR113931]

            PR libstdc++/87744
            PR libstdc++/113931

    libstdc++-v3/ChangeLog:

            * testsuite/26_numerics/random/pr60037-neg.cc: Adjust dg-error
            line number.

[Bug libstdc++/87744] Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

--- Comment #17 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:c74131e77f1a6b7afe700d3526a8992dc9744b0c

commit r14-9038-gc74131e77f1a6b7afe700d3526a8992dc9744b0c
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Feb 7 11:31:10 2024 +0000

    libstdc++: Fix FAIL: 26_numerics/random/pr60037-neg.cc again [PR113961]

            PR libstdc++/87744
            PR libstdc++/113961

    libstdc++-v3/ChangeLog:

            * testsuite/26_numerics/random/pr60037-neg.cc: Adjust dg-error
            line number.