<HTML><BODY><div><div>Hi!</div><div> </div><div>Thanks for your review.</div><div> </div><div>See my answers & questions below.<br> </div><blockquote style="border-left:1px solid #0857A6; margin:10px; padding:0 0 0 10px;">Суббота, 5 сентября 2020, 1:39 +03:00 от Vladislav Shpilevoy <v.shpilevoy@tarantool.org>:<br> <div id=""><div class="js-helper js-readmsg-msg"><style type="text/css"></style><div><div id="style_15992591511624727557_BODY">Hi! Thanks for the patch!<br><br>See 2 comments below.<br><br>On 04.09.2020 15:51, Ilya Kosarev wrote:<br>> Tarantool codebase had at least two functions to generate random<br>> integer in given range and both of them had problems at least with<br>> integer overflow. This patch brings nice function to generate random<br>> int64_t in given range without overflow while preserving uniform random<br>> generator distribution. Most relevant replacements have been made.<br>><br>> Closes #5075<br>> ---<br>> Branch: <a href="https://github.com/tarantool/tarantool/tree/i.kosarev/gh-5075-fine-random-in-range" target="_blank">https://github.com/tarantool/tarantool/tree/i.kosarev/gh-5075-fine-random-in-range</a><br>> Issue: <a href="https://github.com/tarantool/tarantool/issues/5075" target="_blank">https://github.com/tarantool/tarantool/issues/5075</a><br>><br>> @ChangeLog:<br>> * Introduce overflow resistand & evenly distributed random in range (gh-5075).<br><br>1. resistand -> resistant<br><br>><br>> src/lib/core/random.c | 8 ++++++++<br>> src/lib/core/random.h | 12 ++++++++++++<br>> src/lib/swim/swim.c | 26 ++++----------------------<br>> test/unit/histogram.c | 12 +++---------<br>> 4 files changed, 27 insertions(+), 31 deletions(-)<br>><br>> diff --git a/src/lib/core/random.c b/src/lib/core/random.c<br>> index f4fa75b1c1..2229c5fbbc 100644<br>> --- a/src/lib/core/random.c<br>> +++ b/src/lib/core/random.c<br>> @@ -97,3 +97,11 @@ rand:<br>> while (generated < size)<br>> buf[generated++] = rand();<br>> }<br>> +<br>> +int64_t<br>> +random_in_range(int64_t min, int64_t max)<br>> +{<br>> + assert(max >= min);<br>> + double drand = drand48();<br>> + return (int64_t)(drand * max + (1 - drand) * min);<br>> +}<br><br>2. The problem here is that you won't get an overflow, but you won't get a<br>completely random number either. This function is not able to return<br>anything > 48 bits without precision loss. So for example if I will give it<br>a range [INT64_MIN, INT64_MAX], it will never return lots of integers > 2^48.<br>Especially the ones > 2^53, since starting from this point double will loose<br>integer precision.</div></div></div></div></blockquote></div><ol><li>Ok, right, i see the problem here. Didn’t think it through enough.</li></ol><div><blockquote style="border-left:1px solid #0857A6; margin:10px; padding:0 0 0 10px;"><div><div class="js-helper js-readmsg-msg"><div><div><br>I expect a random function be able to return any value from the given range.<br>Not only certain ones.<br><br>In other words, this solution is not much better than rand() %. It also is not<br>able to return the complete range.<br><br>I was thinking about that a lot, and this is why I filed a ticket. It is not<br>a trivial task.<br><br>The function should be able to return any value from 0 to 2^64-1 to cover the<br>entire [INT64_MIN, INT64_MAX], or [0, UINT64_MAX].<br><br>I was thinking we could use random_bytes() to get a value [0, UINT64_MAX], and<br>then scale it down to the given range. For example, if the range is [A, B], then<br>its length L = B - A. And the random value is R.<br><br>Then a scaled down value would be<br><br> S = R / UINT64_MAX * L<br><br>The problem here is the precision loss again. When you will divide R / UINT64_MAX<br>to get a value from [0, 1] range, the result is likely to be garbage. Double<br>can't handle that precision. This is where I stopped and filed the ticket.</div></div></div></div></blockquote></div><ol start="2"><li>Well, yes, scaling doesn’t really seem to work as good as we want to.<br>I looked through this page: <a href="https://www.pcg-random.org/posts/bounded-rands.html">https://www.pcg-random.org/posts/bounded-rands.html</a><br>on generation in range and found out a bounding method which i think is<br>the most suitable for us. It works for int64_t too and can be used both<br>for «complete random» and «pseudo-random»:<pre>```
uint32_t bounded_rand(rng_t& rng, uint32_t range) {
uint32_t mask = ~uint32_t(0);
--range;
mask >>= __builtin_clz(range|1);
uint32_t x;
do {
x = rng() & mask;
} while (x > range);
return x;
}
```</pre></li></ol><div><blockquote style="border-left:1px solid #0857A6; margin:10px; padding:0 0 0 10px;"><div><div class="js-helper js-readmsg-msg"><div><div>Another issue - random_bytes() is easy to use, but it is not pseudo-random. It is<br>completely random. This is actually good usually, but not for the tests. In swim<br>unit tests knowing random seed is the only way to reproduce a fail. That makes me<br>think we need two random functions: for pseudo-random values and for real random.<br><br>Pseudo-random could be generated by concatenation of several rand() calls using<br><< and |.<br><br>Another option - implement Mersenne twister algorithm of pseudo-random numbers of<br>uint64_t type.<br><br>Also I would look into what std:: has in C++. Its random functionality is much<br>richer than rand().</div></div></div></div></blockquote></div><ol start="3"><li>Right, C++ has mersenne_twister int64_t implementation and some solution<br>to get int64_t in range as following:<pre style="background-color:#ffffff; color:#080808; font-family:'JetBrains Mono',monospace; font-size:9.8pt"> </pre></li></ol><div> </div><pre style="background-color:#ffffff; color:#080808; font-family:'JetBrains Mono',monospace; font-size:9.8pt">```
std::random_device rd;
std::mt19937_64 generator(rd());
std::uniform_int_distribution<int64_t> range(min, max);
return range(generator);
```
</pre><div>However, C++ implementation seems to be overcomplicated.<br>I think it is better idea to implement something simple & fast.</div><div> </div><div>For the mersenne_twister the good idea is to adopt this implementation,</div><div>as far as i see it:</div><div><a href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt64.html">http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt64.html</a></div><div> </div><div>But what i think might be even better is to take something less classic</div><div>while more relevant, according to this paper: <a href="https://arxiv.org/pdf/1910.06437.pdf">https://arxiv.org/pdf/1910.06437.pdf</a></div><div> </div><div>I think the best option for us now is xoshiro256++: <a href="http://prng.di.unimi.it/">http://prng.di.unimi.it/</a></div><div>It seems to be much faster and doesn’t fail any known statistical test as far as i see.</div><div>The implementation to adapt: <a href="http://prng.di.unimi.it/xoshiro256plusplus.c">http://prng.di.unimi.it/xoshiro256plusplus.c</a></div><div> </div><div><div data-signature-widget="container"><div data-signature-widget="content"><div>--<br>Ilya Kosarev</div></div></div><div> </div></div></BODY></HTML>