Page MenuHomePhabricator

[libc++] Fix `uniform_int_distribution` for 128-bit result type
ClosedPublic

Authored by fwolff on Wed, Nov 17, 4:46 PM.

Details

Summary

Fixes PR#51520. The problem is that uniform_int_distribution currently uses an unsigned integer with at most 64 bits internally, which is then casted to the desired result type. If the result type is int64_t, this will produce a negative number if the most significant bit is set, but if the result type is __int128_t, the value remains non-negative and will be out of bounds for the example in PR#51520. (The reason why it also seems to work if the upper or lower bound is changed is because this branch will then no longer be taken, and proper rejection sampling takes place.)

The bigger issue here is probably that uniform_int_distribution can be instantiated with __int128_t but will silently produce incorrect results (only the lowest 64 bits can ever be set). libstdc++ also supports __int128_t as a result type, so I have simply extended the maximum width of the internal intermediate result type.

Diff Detail

Event Timeline

fwolff requested review of this revision.Wed, Nov 17, 4:46 PM
fwolff created this revision.
Herald added 1 blocking reviewer(s): Restricted Project. · View Herald TranscriptWed, Nov 17, 4:46 PM

Is uniform_int_distribution really the only distribution with this kind of problem? What about, I dunno, binomial_distribution?

libcxx/include/__bits
55 ↗(On Diff #388060)
libcxx/include/__random/uniform_int_distribution.h
244

Would this work if it were simply

typedef typename conditional<sizeof(result_type) <= 4, uint32_t,
    typename make_unsigned<result_type>::type>::type _UIntType;

? That is, I think the old code was just assuming that for types larger than 32 bits, typename make_unsigned<result_type>::type was by definition uint64_t; now that that's false, we can just make the substitution.

libcxx/test/std/numerics/rand/rand.dis/rand.dist.uni/rand.dist.uni.int/int128.pass.cpp
29
  • I think it's worth verifying that d.min() == 0 && d.max() == INT128_MAX (however we spell that). Similarly on line 40.
  • Shall we add a case where the constructor arguments to uniform_int_distribution<__[u]int128_t> are outside the range of int64/uint64?
  • Style nit: Please use int not auto on lines 30 and 41, and __int128_t not auto on lines 31 and 42.
  • Shall we check uniform_int_distribution<__uint128_t> while we're at it?
fwolff updated this revision to Diff 388290.Thu, Nov 18, 1:05 PM

Is uniform_int_distribution really the only distribution with this kind of problem? What about, I dunno, binomial_distribution?

binomial_distribution also seems to be affected, and maybe others as well. But I haven't looked into them deeply yet, and it's not obvious from looking at the code briefly what causes the problem there.

Also, is there a reason why uniform_int_distribution.h defines its own independent_bits_engine instead of using the one from the random header?

And, out of curiosity, because I haven't been able to figure it out by myself and must be overlooking something: Do you happen to know why the simple definition of independent_bits_engine (here, 26.4.4.2) was dropped in favor of the much more complicated one that made it into the standard?

fwolff marked 3 inline comments as done.Thu, Nov 18, 1:06 PM

binomial_distribution also seems to be affected, and maybe others as well. But I haven't looked into them deeply yet, and it's not obvious from looking at the code briefly what causes the problem there.

Also, is there a reason why uniform_int_distribution.h defines its own independent_bits_engine instead of using the one from the random header?

On both of those questions (but especially the second), I tentatively propose that we (I?) should granularize <random> into <__random/*.h> before landing this PR. (Which will merge-conflict horribly, no matter which way we do things. Unless people think we should just land this one ASAP. I wouldn't object to that, but I wouldn't necessarily encourage it either.)

And, out of curiosity, because I haven't been able to figure it out by myself and must be overlooking something: Do you happen to know why the simple definition of independent_bits_engine (here, 26.4.4.2) was dropped in favor of the much more complicated one that made it into the standard?

Way before my time; I wonder if @mclow.lists would remember. :) What little I've got: That engine was absent from N1932, which was discussed in Berlin 2006 (the meeting notes are not enlightening to me); N2079 had the "simple" version of random_bits_engine, with some comments indicating that getting the math exactly technically right on generate_canonical was harder than it looked; I don't know where N2079 was discussed (presumably Portland though); and then its successor N2111 had the "complicated" version of independent_bits_engine and was voted into the Standard in Portland 2006 (the meeting notes are just a straw poll on voting in the still-draft-numbered d2111, no recorded discussion).

On both of those questions (but especially the second), I tentatively propose that we (I?) should granularize <random> into <__random/*.h> before landing this PR. (Which will merge-conflict horribly, no matter which way we do things. Unless people think we should just land this one ASAP. I wouldn't object to that, but I wouldn't necessarily encourage it either.)

Sure. Do let me know if/how I can help (so that I'm not stepping on your toes).

Way before my time; I wonder if @mclow.lists would remember. :) What little I've got: That engine was absent from N1932, which was discussed in Berlin 2006 (the meeting notes are not enlightening to me); N2079 had the "simple" version of random_bits_engine, with some comments indicating that getting the math exactly technically right on generate_canonical was harder than it looked; I don't know where N2079 was discussed (presumably Portland though); and then its successor N2111 had the "complicated" version of independent_bits_engine and was voted into the Standard in Portland 2006 (the meeting notes are just a straw poll on voting in the still-draft-numbered d2111, no recorded discussion).

Thanks for digging up this information! I can only imagine that it must have something to do with some mathematical intricacy that I'm not seeing...

"Granularize the <random> header" is now D114281.

fwolff updated this revision to Diff 389301.Tue, Nov 23, 1:18 PM

Rebased after D114281 was merged.

Quuxplusone accepted this revision as: Quuxplusone.Tue, Nov 23, 2:21 PM
Quuxplusone added a subscriber: ldionne.

LGTM mod nits! Please wait for @Mordante or @ldionne to approve.
For the record, do we think that there is an implied "TODO" here to look into the situation for all other integer distributions, such as binomial_distribution?
And if so, are you (@fwolff) volunteering to tackle that?

libcxx/include/__bits
53 ↗(On Diff #389301)

Nit: I personally prefer to see (X)-1 rather than (X)~0, since I always mentally read the latter as (X)~0u (which would be wrong) and then correct myself. :) Alternatively, in this case I guess you could just use ~0uLL and save yourself some parentheses.

libcxx/test/std/numerics/rand/rand.dis/rand.dist.uni/rand.dist.uni.int/int128.pass.cpp
82

Tiny nits throughout:

  • a <= n && n <= b is easier on the eyes than n >= a && n <= b. https://quuxplusone.github.io/blog/2021/05/05/its-clamping-time/
  • I'd prefer not to see the extraneous const on lines 42, 43, 49, 58, 59, 65.
  • I'd prefer T(a, b) over T{a, b} on lines 61, 75, and arguably 60, 74 (since we're not worried about most-vexing-parse, and our Ts here are not sequences, arrays, or aggregates).
  • Perhaps rename all_in_range to all_in_64bit_range or all_in_narrower_range or something like that, to indicate more clearly why we don't expect all the output to be "in range"?
Mordante requested changes to this revision.Wed, Nov 24, 11:17 AM

Thanks for looking into this issue!

libcxx/include/__bits
49 ↗(On Diff #389301)

In the header <bit> there is __countl_zero which has 128-bit support. Can we use that function instead?

libcxx/include/__random/log2.h
23

Does this header the same as __bit_log2 in <bit>?

libcxx/test/std/numerics/rand/rand.dis/rand.dist.uni/rand.dist.uni.int/int128.pass.cpp
36

This feels flaky. If the tests happens to produce 100 random values below UINT64_MAX the test fails.
I suggest to select a specific random number engine with a fixed seed for this test.
Then you can add a stable test to see whether values in the wanted range are produced.

52

Why do we need this test? Isn't assert(n >= a && n <= b); enough to test?

This revision now requires changes to proceed.Wed, Nov 24, 11:17 AM

+1 it's a good idea to investigate the possibility of reusing __countl_zero and __bit_log2.

libcxx/test/std/numerics/rand/rand.dis/rand.dist.uni/rand.dist.uni.int/int128.pass.cpp
36

This isn't literally flaky, since default_random_engine will be fixed at compile time and so will its default seed — we're not using random_device or anything. I agree its definition might vary between libc++/libstdc++ and MSVC (I'm not sure if it does in practice; I'm pretty sure off the top of my head that it's minstd_rand0 for both libc++ and libstdc++).
Note that engines' behaviors are defined by the standard, so minstd_rand0{}() has the same value on all implementations by definition. It's the distributions whose behaviors diverge across implementations (and unfortunately it's the distribution whose behavior we really care about here).

The chances of 100 numbers all being clustered in one 18446744073709551616th of the PRNG's range (or even one-tenth of its range, as on line 42) strikes me as actually-far-more-than-astronomically unlikely. So I don't see a problem here. But, at the same time, it wouldn't hurt to s/default_random_engine/minstd_rand0/ just to remove one superfluous degree of freedom.

52

I believe this illustrates my recent point about renaming this variable. :) We want to check that all the values are in the range [a, b]; but then we also want to check that some of the values are not in the narrower range [INT64_MIN, INT64_MAX] (because if they all happened to fall in that narrower range, that would likely indicate a truncation bug somewhere in libc++ code).

Mordante added inline comments.Thu, Nov 25, 10:04 AM
libcxx/test/std/numerics/rand/rand.dis/rand.dist.uni/rand.dist.uni.int/int128.pass.cpp
36

Fair point. In fact when it fails we might consider the distribution not to be uniform.

I still think it's best to use a fixed random engine.

52

Indeed it illustrates your point. Kete Gregory's "Naming is hard, let's do better" talk of a few years ago directly comes to mind ;-)

fwolff updated this revision to Diff 389887.Thu, Nov 25, 4:40 PM

This attempts to fix the remaining concerns/requests.

Regarding the other integer distributions: binomial_distribution and negative_binomial_distribution actually seem to work; discrete_distribution is not relevant here because nobody has over UINT64_MAX weights; and I haven't gotten poisson_distribution and geometric_distribution to work, but this might just be due to the extreme values of the parameters you'd have to use to get 128-bit results (and the latter just delegates to negative_binomial_distribution anyway).

fwolff marked 8 inline comments as done.Thu, Nov 25, 4:46 PM
fwolff added inline comments.
libcxx/include/__random/log2.h
23

Yes, but __bit_log2 is marked with _LIBCPP_CONSTEXPR_AFTER_CXX11, so it won't work for C++11 because we are using it to initialize static const members, or am I missing something?

Mordante accepted this revision.Sun, Nov 28, 4:40 AM

LGTM modulo one style issue. Please resolve this issue and rebase the patch to verify the CI is green before landing.

libcxx/include/__random/log2.h
23

Good point, too bad we can't remove the duplication.

libcxx/test/std/numerics/rand/rand.dis/rand.dist.uni/rand.dist.uni.int/int128.pass.cpp
30

Please change auto with the type, here and in the remainder of this file. This is the typical style in LLVM/libc++.

This revision is now accepted and ready to land.Sun, Nov 28, 4:40 AM
Quuxplusone accepted this revision.Sun, Nov 28, 9:25 AM
Quuxplusone added inline comments.
libcxx/test/std/numerics/rand/rand.dis/rand.dist.uni/rand.dist.uni.int/int128.pass.cpp
30

(FWIW, as long as it's auto x = TheSpecificType(); as in these cases, personally I'm fine with it. But even in these cases, TheSpecificType x; will be shorter.)

ldionne requested changes to this revision.Mon, Nov 29, 8:44 AM

Thanks a lot for looking into this @fwolff.

The only issue I see with this patch is that the Standard says that instantiating any of the distributions with something that is not short, int, long, long long, unsigned short, unsigned int, unsigned long, or unsigned long long is undefined: http://eel.is/c++draft/rand#req.genl-1.5. Hence, this is technically an extension, and another valid approach would be to just static_assert(_IntType is one of the aforementioned types); from within the distributions. I'm curious to hear your thoughts on whether it's better to stick to the Standard or provide this as an extension (in which case we should probably annotate that it is an extension).

Requesting changes so we can have this discussion, however I'm fine with the patch if we decide to go for this approach.

libcxx/include/__random/log2.h
61–66

Or something like that -- the current formatting looks really weird with the < alone on its own line.

This revision now requires changes to proceed.Mon, Nov 29, 8:44 AM

I prefer to allow this extension; I even wonder whether not allowing 128-bit values was intentionally or an artifact of prohibiting (un)signed char. In general I prefer to allow __[u]int128_t to be used as a first-class citizen in libc++.

fwolff updated this revision to Diff 390780.Tue, Nov 30, 12:19 PM
fwolff marked an inline comment as done.
fwolff marked 3 inline comments as done.Tue, Nov 30, 12:25 PM

I prefer to allow this extension; I even wonder whether not allowing 128-bit values was intentionally or an artifact of prohibiting (un)signed char. In general I prefer to allow __[u]int128_t to be used as a first-class citizen in libc++.

Yes, this is also how I feel about this.

[...] or provide this as an extension (in which case we should probably annotate that it is an extension).

What does that mean exactly, annotating it as an extension?

libcxx/include/__random/log2.h
61–66

Fixed, although I followed the precedent of _Working_result_type from __independent_bits_engine here.

ldionne accepted this revision.Tue, Nov 30, 1:16 PM

I prefer to allow this extension; I even wonder whether not allowing 128-bit values was intentionally or an artifact of prohibiting (un)signed char. In general I prefer to allow __[u]int128_t to be used as a first-class citizen in libc++.

Yes, this is also how I feel about this.

Ok. In that case, can we add a comment somewhere in uniform_int_distribution that __int128_t is supported? Make sure the comment contains the word "extension", so that when we eventually get a formal way of documenting those, it's easy to find the existing extensions we support.

[...] or provide this as an extension (in which case we should probably annotate that it is an extension).

What does that mean exactly, annotating it as an extension?

I just meant documenting it somewhere.

This revision is now accepted and ready to land.Tue, Nov 30, 1:16 PM
fwolff updated this revision to Diff 390849.Tue, Nov 30, 4:07 PM
fwolff marked an inline comment as done.

Ok. In that case, can we add a comment somewhere in uniform_int_distribution that __int128_t is supported?

Done, and thanks for reviewing this! Can you also commit it for me? You can use name and email as in commit dc1c27149f214ff099e99930226ae312b0cf1910 for attribution. Thanks!

This revision was automatically updated to reflect the committed changes.

Hi. I think the build issue we're seeing (https://ci.chromium.org/ui/p/fuchsia/builders/ci/clang_toolchain.ci.core.x64-debug-subbuild/b8829019800818975281/overview) is caused by this patch:

../../../../llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/install/bin/../include/c++/v1/bit:142:5: error: static_assert failed due to requirement '__libcpp_is_unsigned_integer<i
nt>::value' "__countl_zero requires an unsigned integer type"
    static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_zero requires an unsigned integer type");
    ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../../../../llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/install/bin/../include/c++/v1/__random/uniform_int_distribution.h:242:24: note: in instantiation of function template s
pecialization 'std::__countl_zero<int>' requested here
    size_t __w = _Dt - __countl_zero(_Rp) - 1;
                       ^
../../../../llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/install/bin/../include/c++/v1/__random/uniform_int_distribution.h:206:17: note: in instantiation of function template s
pecialization 'std::uniform_int_distribution<bool>::operator()<std::linear_congruential_engine<unsigned int, 48271, 0, 2147483647>>' requested here
        {return (*this)(__g, __p_);}
                ^
../../src/tests/fidl/compatibility/compatibility_test.cc:592:43: note: in instantiation of function template specialization 'std::uniform_int_distribution<bool>::operator()<std::linea
r_congruential_engine<unsigned int, 48271, 0, 2147483647>>' requested here
  s->primitive_types.b = bool_distribution(rand_engine);
                                          ^

Is there something wrong on our end that's causing this to happen, or is this from something incorrect with the patch?

fwolff added a comment.Wed, Dec 1, 3:03 PM

Is there something wrong on our end that's causing this to happen, or is this from something incorrect with the patch?

Could be; I will look into this (although technically you are not allowed to instantiate std::uniform_int_distribution with bool according to the standard, as @ldionne has noted above).

Hi. I think the build issue we're seeing (https://ci.chromium.org/ui/p/fuchsia/builders/ci/clang_toolchain.ci.core.x64-debug-subbuild/b8829019800818975281/overview) is caused by this patch:

../../../../llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/install/bin/../include/c++/v1/bit:142:5: error: static_assert failed due to requirement '__libcpp_is_unsigned_integer<i
nt>::value' "__countl_zero requires an unsigned integer type"
    static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_zero requires an unsigned integer type");
    ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../../../../llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/install/bin/../include/c++/v1/__random/uniform_int_distribution.h:242:24: note: in instantiation of function template s
pecialization 'std::__countl_zero<int>' requested here
    size_t __w = _Dt - __countl_zero(_Rp) - 1;
                       ^
../../../../llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/install/bin/../include/c++/v1/__random/uniform_int_distribution.h:206:17: note: in instantiation of function template s
pecialization 'std::uniform_int_distribution<bool>::operator()<std::linear_congruential_engine<unsigned int, 48271, 0, 2147483647>>' requested here
        {return (*this)(__g, __p_);}
                ^
../../src/tests/fidl/compatibility/compatibility_test.cc:592:43: note: in instantiation of function template specialization 'std::uniform_int_distribution<bool>::operator()<std::linea
r_congruential_engine<unsigned int, 48271, 0, 2147483647>>' requested here
  s->primitive_types.b = bool_distribution(rand_engine);
                                          ^

Is there something wrong on our end that's causing this to happen, or is this from something incorrect with the patch?

I believe there's something wrong with the patch; specifically I think this'll fix it:

diff --git a/libcxx/include/__random/uniform_int_distribution.h b/libcxx/include/__random/uniform_int_distribution.h
index 55b4761637f0..169d2ed112d0 100644
--- a/libcxx/include/__random/uniform_int_distribution.h
+++ b/libcxx/include/__random/uniform_int_distribution.h
@@ -230,8 +230,8 @@ typename uniform_int_distribution<_IntType>::result_type
 uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
 {
-    typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t), uint32_t,
-                                 typename make_unsigned<result_type>::type>::type _UIntType;
+    typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t), __identity<uint32_t>,
+                                 make_unsigned<result_type> >::type::type _UIntType;
     const _UIntType _Rp = _UIntType(__p.b()) - _UIntType(__p.a()) + _UIntType(1);
     if (_Rp == 1)
         return __p.a();

I'm working on a regression test now. Shockingly, we have no tests for uniform_int_distribution<T> for any T except int and now __{u,}int128_t — not even short, let alone bool.

Hi. I think the build issue we're seeing (https://ci.chromium.org/ui/p/fuchsia/builders/ci/clang_toolchain.ci.core.x64-debug-subbuild/b8829019800818975281/overview) is caused by this patch:

../../../../llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/install/bin/../include/c++/v1/bit:142:5: error: static_assert failed due to requirement '__libcpp_is_unsigned_integer<i
nt>::value' "__countl_zero requires an unsigned integer type"
    static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_zero requires an unsigned integer type");
    ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../../../../llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/install/bin/../include/c++/v1/__random/uniform_int_distribution.h:242:24: note: in instantiation of function template s
pecialization 'std::__countl_zero<int>' requested here
    size_t __w = _Dt - __countl_zero(_Rp) - 1;
                       ^
../../../../llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/install/bin/../include/c++/v1/__random/uniform_int_distribution.h:206:17: note: in instantiation of function template s
pecialization 'std::uniform_int_distribution<bool>::operator()<std::linear_congruential_engine<unsigned int, 48271, 0, 2147483647>>' requested here
        {return (*this)(__g, __p_);}
                ^
../../src/tests/fidl/compatibility/compatibility_test.cc:592:43: note: in instantiation of function template specialization 'std::uniform_int_distribution<bool>::operator()<std::linea
r_congruential_engine<unsigned int, 48271, 0, 2147483647>>' requested here
  s->primitive_types.b = bool_distribution(rand_engine);
                                          ^

Is there something wrong on our end that's causing this to happen, or is this from something incorrect with the patch?

@leonardchan
It's technically not allowed to instantiate the distributions with bool. In that other patch, I am pushing so that we make it ill-formed and provide a diagnostic -- are you able to fix the code on your side?