doc: Explain why GetRandMicros must not be templated

MarcoFalke commented at 8:24 pm on April 23, 2020: member

in src/random.h:75 in 333393d96d outdated

66@@ -67,7 +67,17 @@
67  * Thread-safe.
68  */
69 void GetRandBytes(unsigned char* buf, int num) noexcept;
70+/** Generate a random integer in the range [0..range). Precondition: range > 0 */
71 uint64_t GetRand(uint64_t nMax) noexcept;
72+// The following GetRand*(std::chrono::*) MUST NOT be templated on the type of
73+// the duration to prevent unsafe use at the call site. If it was templated, it
74+// would be impossible for the compiler to select the right template. E.g.
75+// assuming that a GetRand<T> exists for all duration types, then `foo` will

sipa commented at 8:31 pm on April 23, 2020:

I don’t understand this.

sipa commented at 8:35 pm on April 23, 2020:

Oh you mean because it would use the type of the input (hours) as precision, effectively, and then converted to microseconds afterwards?

That’s a very roundabout way of describing the problem, and wouldn’t apply to a GetRandMicros that always interpreted the input as microseconds.

MarcoFalke commented at 8:41 pm on April 23, 2020:

I don’t understand this.

Here is the code. I am happy to remove the sentence and replace it with code instead.

 0template <typename D>
 1D GetRandDur(const D& duration_max)
 2{
 3    return D{GetRand(duration_max.count())};
 4}
 5
 6BOOST_AUTO_TEST_CASE(util_time_GetRandTime)
 7{
 8    std::chrono::seconds rand_hour = GetRandDur(std::chrono::hours{1});
 9    // Want seconds to be in range [0..1hour), but always get zero :((((
10    BOOST_CHECK_EQUAL(rand_hour.count(), 0);
11}

MarcoFalke commented at 8:45 pm on April 23, 2020:

That’s a very roundabout way of describing the problem, and wouldn’t apply to a GetRandMicros that always interpreted the input as microseconds.

Yes, that is the reason why I added GetRandMicros in fa883ab35ad2d4328e35b1e855d0833740a6b910, but I forgot to add documentation back then.

sipa commented at 9:17 pm on April 23, 2020:

Yeah, I understand now. You mean templatizing to avoid the “Micros” in the function name (and implicitly pass the resolution of the result that).

There’s a rather crazy way to work around that:

0template<typename In, typename OutRep = typename In::rep, typename OutPeriod = typename In::period>
1std::chrono::duration<OutRep, OutPeriod> GetRand(std::chrono::duration<OutRep, OutPeriod> arg) {
2    return arg;
3}

That’s a GetRand that only applies to durations, but you still always have to explicitly state the resolution you want (e.g. GetRand<std::chrono::milliseconds>(SOME_CONSTANT_OF_TYPE_CHRONO_HOURS) will work as expected; GetRand(...) won’t compile).

sipa commented at 9:20 pm on April 23, 2020:

I doubt that’s more appealing than just GetRandMicros, GetRandMillis, … functions, though.

DrahtBot added the label Docs on Apr 23, 2020

DrahtBot added the label Tests on Apr 23, 2020

MarcoFalke removed the label Docs on Apr 23, 2020

MarcoFalke removed the label Tests on Apr 24, 2020

MarcoFalke added the label Docs on Apr 24, 2020

in src/random.h:73 in 333393d96d outdated

66@@ -67,7 +67,17 @@
67  * Thread-safe.
68  */
69 void GetRandBytes(unsigned char* buf, int num) noexcept;
70+/** Generate a random integer in the range [0..range). Precondition: range > 0 */
71 uint64_t GetRand(uint64_t nMax) noexcept;
72+// The following GetRand*(std::chrono::*) MUST NOT be templated on the type of
73+// the duration to prevent unsafe use at the call site. If it was templated, it

glozow commented at 7:42 pm on April 24, 2020:

My knowledge is pretty limited, but maybe I can make a suggestion for clearer wording?

It seems like the issue is that, if GetRand*(std::chrono::*) is templated with this implementation, the max_duration’s count() is used as-is instead of converting between the argument type and return type like we would expect it to. Instead, the conversion happens at the end. In simple terms, the std::chrono types won’t convert nicely which means we lose precision if we want random small units of time over the duration of a large unit of time (which I’m guessing is a common use case). For example, when you try to get random seconds over the duration of 1 hour, the only return value you can get is 0 hours = 0 seconds.

Other example: std::chrono::seconds rand_seconds = GetRandDur(std::chrono::hours{4}); can return non-zero values, but only at the precision of hours (i.e. 0, 3600, 7200, or 10800 seconds).

If you were to make a template, it only necessarily works as intended if you pass in a max_duration of strictly the same type (or @sipa’s workaround).

amitiuttarwar commented at 10:42 pm on April 24, 2020:

@MarcoFalke - I built on @gzhao408’s description. here’s an attempt at a comment:

The following GetRand<duration> MUST NOT be templated on the type of the <duration> to prevent unexpected results. If there is a mismatch between the return type and the argument type, the compiler is unable to reliably select the correct template. The unexpected conversion handling can lead to precision loss.

Eg. std::chrono::seconds rand_seconds = GetRandDur(std::chrono::hours{2}) will return 1 of 2 values rather than 1 of 120 values.

MarcoFalke commented at 10:57 pm on April 24, 2020:

Thanks @gzhao408 and @amitiuttarwar for helping me to explain this. Took your suggestion and added you both as co author in the commit.

in src/random.h:76 in 333393d96d outdated

71 uint64_t GetRand(uint64_t nMax) noexcept;
72+// The following GetRand*(std::chrono::*) MUST NOT be templated on the type of
73+// the duration to prevent unsafe use at the call site. If it was templated, it
74+// would be impossible for the compiler to select the right template. E.g.
75+// assuming that a GetRand<T> exists for all duration types, then `foo` will
76+// always be set to a constant, not a random duration.

amitiuttarwar commented at 8:09 pm on April 24, 2020:

I don’t think this is true? its just random in relation to the duration type of the input.

eg. std::chrono::seconds foo = GetRand(std::chrono::hours{5}) might return 3600, 7200, 10800 etc.

MarcoFalke commented at 8:53 pm on April 24, 2020:

Any suggestions to improve the wording? Something with “quantized”, maybe?

amitiuttarwar commented at 10:43 pm on April 24, 2020:

think precision loss captures it better, esp with example. attempted in other comment thread.

in src/random.h:74 in 333393d96d outdated

66@@ -67,7 +67,17 @@
67  * Thread-safe.
68  */
69 void GetRandBytes(unsigned char* buf, int num) noexcept;
70+/** Generate a random integer in the range [0..range). Precondition: range > 0 */
71 uint64_t GetRand(uint64_t nMax) noexcept;
72+// The following GetRand*(std::chrono::*) MUST NOT be templated on the type of
73+// the duration to prevent unsafe use at the call site. If it was templated, it
74+// would be impossible for the compiler to select the right template. E.g.

amitiuttarwar commented at 8:15 pm on April 24, 2020:

is it impossible, or does the compiler just select template duration of param thats passed & then tries to convert afterwards?

seems that way to me because std::chrono::seconds val = GetRandDur(std::chrono::hours) gives a type conversion error

MarcoFalke commented at 8:53 pm on April 24, 2020:

No it doesn’t give a type conversion error.

This compiles fine for me and the test pass:

 0template <typename D>
 1D GetRandDur(const D& duration_max)
 2{
 3    return D{GetRand(duration_max.count())};
 4}
 5
 6BOOST_AUTO_TEST_CASE(util_time_GetRandTime)
 7{
 8    std::chrono::seconds rand_hour = GetRandDur(std::chrono::hours{1});
 9    // Want seconds to be in range [0..1hour), but always get zero :((((
10    BOOST_CHECK_EQUAL(rand_hour.count(), 0);
11}

amitiuttarwar commented at 10:23 pm on April 24, 2020:

oh interesting. maybe its different in gcc vs clang?? or I’m missing something obvious.

sipa commented at 10:27 pm on April 24, 2020:

I hope not; that would violate the language spec.

std::chrono::hours should always be implicitly convertible into std::chrono::seconds.

amitiuttarwar commented at 10:32 pm on April 24, 2020:

ok I tried again and it works. I must have made an accidental error. my mistake!

amitiuttarwar commented at 10:58 pm on April 24, 2020:

oh, my error was in what I was typing here. I get conversion issue when I do std::chrono::minutes val = GetRandDur(std::chrono::seconds{120})

so when function arg is higher precision than return value.

which is why I was suspecting compiler selects template duration based on function arg, then tries to convert afterwards. so selection is deterministic vs unexpected, but can lead to unexpected results.

amitiuttarwar commented at 8:15 pm on April 24, 2020: contributor

concept ACK on adding reasoning (especially given I was considering trying to turn GetRand* into a template), some clarification questions

MarcoFalke force-pushed on Apr 24, 2020

amitiuttarwar commented at 11:04 pm on April 24, 2020: contributor

ACK fa6c75bdbe7f842c7c4c3846467cb47dd1431a75… but not sure if my ack counts anymore 🙂

doc: Explain why GetRandMicros must not be templated

Co-Authored-By: Amiti Uttarwar <amiti@uttarwar.org>
Co-Authored-By: Gloria Zhao <gzhao408@berkeley.edu>
Co-Authored-By: Pieter Wuille <pieter.wuille@gmail.com>

fa13199e89

in src/random.h:74 in fa6c75bdbe outdated

66@@ -67,7 +67,17 @@
67  * Thread-safe.
68  */
69 void GetRandBytes(unsigned char* buf, int num) noexcept;
70+/** Generate a random integer in the range [0..range). Precondition: range > 0 */
71 uint64_t GetRand(uint64_t nMax) noexcept;
72+// The following GetRandDur<duration> MUST NOT be templated on the type of the
73+// <duration> to prevent unexpected results. If there is a mismatch between the
74+// return type and the argument type, the compiler is unable to reliably select

sipa commented at 11:13 pm on April 24, 2020:

Sorry to nitpick here, but i think this is still confusing.

In a hypothetical

0template<typename T>
1T GetRandDur(T max) { return T{GetRand(max.count())}; }
2
3std::chrono::seconds r = GetRandDur(std::chrono::hours{1})

there is no unreliable template selection or mismatch between types. GetRandDur is reliably instantiated with T=std::chrono::hours, and is returning a random value of the same type. It’s in the assignment outside of the function call that the conversion to std::chrono::seconds happens, and this assignment doesn’t lose precision; the precision was never requested in the first place.

How about this instead:

Templates cannot be used here to avoid stating explicitly what precision
is desired in the result. A hypothetical
`template<typename T> T GetRandDur(T)` invoked on a
`std::chrono::hours` argument will only ever return a duration with the
resolution of 1 hours, which may be unexpected when assigning to
a variable of a higher resolution duration like `std::chrono::seconds`.

MarcoFalke commented at 11:42 pm on April 24, 2020:

Thanks. Copy-pasted your text.

amitiuttarwar commented at 11:50 pm on April 24, 2020:

ah yes. ok this confirms what I was trying to get at in the other thread. thanks!

MarcoFalke force-pushed on Apr 24, 2020

sipa commented at 2:40 am on April 25, 2020: member

It does actually seem possible to create a templated GetRandDur that works as expected(?) when assigning to higher-resolution duration types. I’m not sure it’s a good idea, but posting this here in case people are interested:

 0template<typename D>
 1class RandDur
 2{
 3    const D m_max;
 4public:
 5    constexpr RandDur(D max) : m_max(max) {}
 6    template<typename D2>
 7    operator D2() const { return D2{GetRand(D2{m_max}.count())}; }
 8};
 9
10template<typename D>
11RandDur<D> GetRandDur(D duration_max)
12{
13    return RandDur<D>(duration_max);
14}
15
16std::chrono::seconds s = GetRandDur(std::chrono::hours{2});

s will take on a value between 0 and 7200 seconds here. It works by returning an object RandDuration from GetRandDur that is an unevaluated random-duration operation. It’s evaluated when converting it to seconds, at which time the destination type is known.

A reason this may not be a good idea is because now

0auto r = GetRandDur(std::chrono::hours{2});
1std::chrono::seconds s1 = r;
2std::chrono::seconds s2 = r;
3printf("%i, %i\n", (int)s1.count(), (int)s2.count());

would print two different numbers.

promag commented at 2:28 pm on April 26, 2020: member

ACK fa13199e89ee6524c74747774b2031ec7d50accb.

What if we prevent template argument deduction?

MarcoFalke commented at 2:34 pm on April 26, 2020: member

What if we prevent template argument deduction?

how?

jonatack commented at 5:39 pm on April 26, 2020: member

ACK fa13199e89ee6524c74747774b2031ec7d50accb

sipa commented at 10:32 pm on April 26, 2020: member

@promag That would work, for example using:

0template<typename D>
1D GetRandDur(typename std::common_type<D>::type max) { ... }

but you’d still be left with a templated function which you’d need to call as

0std::chrono::microseconds r = GetRandDur<std::chrono::microseconds>(std::chrono::hours{2});

so it wouldn’t avoid the need for explicitly passing in the precision. The current codebase’s approach effectively does the same thing, but with a slightly shorter notation (where GetRandMicros is effectively GetRandDur<std::chrono::microseconds>.

MarcoFalke commented at 11:21 pm on April 26, 2020: member

I wasn’t aware that there is a way to tell the compiler that a template argument must be passed. I’ll switch out the implementation here with the std::common_type one.

in src/test/util_tests.cpp:1353 in fa13199e89

1347@@ -1348,6 +1348,13 @@ BOOST_AUTO_TEST_CASE(gettime)
1348     BOOST_CHECK((GetTime() & ~0xFFFFFFFFLL) == 0);
1349 }
1350 
1351+BOOST_AUTO_TEST_CASE(util_time_GetRandTime)
1352+{
1353+    // Check that GetRand* can not magically increase the resolution of the result

promag commented at 11:59 pm on April 26, 2020:

What magic?

promag commented at 0:06 am on April 27, 2020: member

@MarcoFalke what @sipa said, sorry for the delay.

I don’t mind either approaches, nice observation and test thought.

MarcoFalke closed this on Apr 27, 2020

MarcoFalke deleted the branch on Apr 27, 2020

sipa commented at 2:51 am on April 27, 2020: member

Why?

promag commented at 8:04 am on April 27, 2020: member

Maybe because scoped changed Marco will open a new PR? 🤔

DrahtBot locked this on Feb 15, 2022

doc: Explain why GetRandMicros must not be templated #18751