random_device question

[Bonita Montero]

Is there any guarantee the standard makes that random_device shoudn't
start at the same internal state for all new threads, i.e. the output
of the following code is likey to be different on both lines?

#include <iostream>
#include <mutex>
#include <random>
#include <thread>

using namespace std;

int main()
{
auto thr = []()
{
static mutex mtx;
random_device rd;
mtx.lock();
cout << rd() << endl;
mtx.unlock();
};
thread t1( thr );
thread t2( thr );
t1.join();
t2.join();
}

[Alf P. Steinbach]

As far as I know the standard allows `random_device` to be an ordinary
pseudo-random number generator with fixed seed, although that's clearly
not the intent.

To work around the MinGW g++ standard library's pseudo random
implementation, define _GLIBCXX_USE_RANDOM_TR1 before including any
standard library header, i.e. in the build.

For an easy-to-break in-source way to do it see <url:
https://github.com/alf-p-steinbach/cppx-core/blob/master/source/cppx-core/stdlib-wrappers/random-numbers-util.hpp>,
which also defines some simple wrappers. I should have fixed that, it
should be a conditional static_assert instead. You get the idea I hope.


- Alf

[Chris M. Thomasson]

On 10/12/2019 12:40 AM, Bonita Montero wrote:
>
> Is there any guarantee the standard makes that random_device shoudn't
> start at the same internal state for all new threads, i.e. the output
> of the following code is likey to be different on both lines?

I don' think so, however, the term non-deterministic is used:

https://en.cppreference.com/w/cpp/numeric/random/random_device

A random device per thread should be okay. Although, one can create a
PRNG per thread and use a single random device to gain their individual
per-thread seeds.



> [...]

[Manfred]

The page also says that "In this case [PRNG] each std::random_device
object may generate the same number sequence."

Bottom line is that the properties random_device are implementation
dependent, so the authoritative source is the implementation, rather
than the standard.

In case of GCC this is what they say (which is not much):
https://gcc.gnu.org/onlinedocs/gcc-9.2.0/libstdc++/api/a06347.html

>
>
>
>> [...]

[Chris M. Thomasson]

On 10/12/2019 2:14 PM, Manfred wrote:
> On 10/12/2019 9:58 PM, Chris M. Thomasson wrote:
>> On 10/12/2019 12:40 AM, Bonita Montero wrote:
>>>
>>> Is there any guarantee the standard makes that random_device shoudn't
>>> start at the same internal state for all new threads, i.e. the output
>>> of the following code is likey to be different on both lines?
>>
>> I don' think so, however, the term non-deterministic is used:
>>
>> https://en.cppreference.com/w/cpp/numeric/random/random_device
>>
>> A random device per thread should be okay. Although, one can create a
>> PRNG per thread and use a single random device to gain their
>> individual per-thread seeds.
>
> The page also says that "In this case [PRNG] each std::random_device
> object may generate the same number sequence."
>
> Bottom line is that the properties random_device are implementation
> dependent, so the authoritative source is the implementation, rather
> than the standard.

Agreed. I think a per-thread PRNG seeded with a std::random_device is
fine. The thread would take the seed from a single instance of
std::random_device at startup, before passing control to the user. It
can even mix in its thread id for the seed as an experiment. Therefore,
after this, a thread can use its own per-thread context to generate a
pseudo random number without using any sync.

basic pseudo-code, abstract on certain things:


struct rnd_dev
{
a_true_random_ng rdev; // assuming a non-thread safe TRNG
std::mutex mtx;

seed_type generate()
{
mtx.lock();
seed_type seed = rdev.generate();
mtx.unlock();

return seed;
}
};


static rnd_dev g_rnd_dev;


struct per_thread
{
prng rseq; // thread local prng

void startup()
{
// seed with the main TRNG
rseq.seed(g_rnd_dev.generate());
}

// generate a thread local PRN
rnd_type generate()
{
return rseq.next();
}
};


Just for fun, Actually, each thread can use different PRNG algorithms. I
remember doing an experiment where there was a global static table of
function pointers to different PRNGS and a thread could choose between them.


Btw, can this be an implementation of a random device wrt its output:

https://groups.google.com/d/topic/comp.lang.c++/7u_rLgQe86k/discussion

;^)

[Manfred]

On 10/13/19 6:40 AM, Chris M. Thomasson wrote:
> Just for fun, Actually, each thread can use different PRNG algorithms. I
> remember doing an experiment where there was a global static table of
> function pointers to different PRNGS and a thread could choose between
> them.
>
>
> Btw, can this be an implementation of a random device wrt its output:
>
> https://groups.google.com/d/topic/comp.lang.c++/7u_rLgQe86k/discussion
>
> ;^)

Funny, however I wonder how reliable it can be - there is no guarantee
of an actual race condition.

Anyway, for a few years now Intel has been shipping CPUs with rdrand,
and GCC's random_device does use it, as far as I can see. Still I get
entropy() = 0, though.

[Bonita Montero]

> Anyway, for a few years now Intel has been shipping CPUs with rdrand,

> and GCC's random_device does use it, ...

Really? When I constantly read from random_device I get 100% load
on the core, but almost only kernel-time. I.e. random_device must
be feeded significantly by the kernel.

[Manfred]

In my case disassembly shows that it does - of course it can be that on
other systems it doesn't.

[Bonita Montero]

When I compile an run this ...

#include <random>
int main()
{
std::random_device rd;
for( unsigned u = 10'000'000; u; --u )
rd();
}

... this is the result when being compiled with g++ and run with
"Windows Subsystem for Linux 2.0" ...

real 0m25.452s
user 0m0.563s
sys 0m24.875s

And this is the result when being compiled with MSVC and run under
Windows 10 ...

real 531.25ms
user 531.25ms
sys 0.00ms

Maybe random_device hasn't a kernel-call for each ()-call, but the
kernel-calls might be a thousand times slower than when the app is
being feeded from the userland-state.

I think it's a big mistake to build random_device on top of /dev/random
or /dev/urandom. Standard-library random-number-generators simply don't
need to give high quality randomness.

[Chris M. Thomasson]

On 10/13/2019 9:26 AM, Manfred wrote:
> On 10/13/19 6:40 AM, Chris M. Thomasson wrote:
>> Just for fun, Actually, each thread can use different PRNG algorithms.
>> I remember doing an experiment where there was a global static table
>> of function pointers to different PRNGS and a thread could choose
>> between them.
>>
>>
>> Btw, can this be an implementation of a random device wrt its output:
>>
>> https://groups.google.com/d/topic/comp.lang.c++/7u_rLgQe86k/discussion
>>
>> ;^)
>
> Funny, however I wonder how reliable it can be - there is no guarantee
> of an actual race condition.

Yes there is. I am implementing an atomic fetch-and-add operation in a
very standard yet racy way, well, lets call it the full blown wrong way
wrt the fetch-and-add...
_______________________________
void racer(unsigned int n)
{
for (unsigned int i = 0; i < n; ++i)
{
// Race infested fetch-and-add op
unsigned int r = g_racer.load(std::memory_order_relaxed);
r = r + 1;
g_racer.store(r, std::memory_order_relaxed);
}
}
_______________________________

This can be influenced by simple moves of the mouse. Its funny to me.
There is no race condition wrt the standard, however, wrt the rules of
fetch-and-add, its totally foobar!

[Chris M. Thomasson]

On 10/13/2019 1:51 PM, Chris M. Thomasson wrote:
> On 10/13/2019 9:26 AM, Manfred wrote:
>> On 10/13/19 6:40 AM, Chris M. Thomasson wrote:
>>> Just for fun, Actually, each thread can use different PRNG
>>> algorithms. I remember doing an experiment where there was a global
>>> static table of function pointers to different PRNGS and a thread
>>> could choose between them.
>>>
>>>
>>> Btw, can this be an implementation of a random device wrt its output:
>>>
>>> https://groups.google.com/d/topic/comp.lang.c++/7u_rLgQe86k/discussion
>>>
>>> ;^)
>>
>> Funny, however I wonder how reliable it can be - there is no guarantee
>> of an actual race condition.

Well, if the simulation was using a single thread, then there is no race
condition wrt the foobare'd impl of fetch-and-add.

> Yes there is. I am implementing an atomic fetch-and-add operation in a
> very standard yet racy way, well, lets call it the full blown wrong way
> wrt the fetch-and-add...

[...]

[Chris M. Thomasson]

On 10/13/2019 11:27 PM, Chris M. Thomasson wrote:
> On 10/13/2019 1:51 PM, Chris M. Thomasson wrote:
>> On 10/13/2019 9:26 AM, Manfred wrote:
>>> On 10/13/19 6:40 AM, Chris M. Thomasson wrote:
>>>> Just for fun, Actually, each thread can use different PRNG
>>>> algorithms. I remember doing an experiment where there was a global
>>>> static table of function pointers to different PRNGS and a thread
>>>> could choose between them.
>>>>
>>>>
>>>> Btw, can this be an implementation of a random device wrt its output:
>>>>
>>>> https://groups.google.com/d/topic/comp.lang.c++/7u_rLgQe86k/discussion
>>>>
>>>> ;^)
>>>
>>> Funny, however I wonder how reliable it can be - there is no
>>> guarantee of an actual race condition.
>
> Well, if the simulation was using a single thread, then there is no race
> condition wrt the foobare'd impl of fetch-and-add.

As soon as multiple threads are involved, one must assume a race
condition wrt the standard. Even if the implementation has some strange
thread scheduler that keeps things in order.

[Chris M. Thomasson]

On 10/16/2019 2:49 PM, Chris M. Thomasson wrote:
> On 10/13/2019 11:27 PM, Chris M. Thomasson wrote:
>> On 10/13/2019 1:51 PM, Chris M. Thomasson wrote:
>>> On 10/13/2019 9:26 AM, Manfred wrote:
>>>> On 10/13/19 6:40 AM, Chris M. Thomasson wrote:
>>>>> Just for fun, Actually, each thread can use different PRNG
>>>>> algorithms. I remember doing an experiment where there was a global
>>>>> static table of function pointers to different PRNGS and a thread
>>>>> could choose between them.
>>>>>
>>>>>
>>>>> Btw, can this be an implementation of a random device wrt its output:
>>>>>
>>>>> https://groups.google.com/d/topic/comp.lang.c++/7u_rLgQe86k/discussion
>>>>>
>>>>> ;^)
>>>>
>>>> Funny, however I wonder how reliable it can be - there is no
>>>> guarantee of an actual race condition.
>>
>> Well, if the simulation was using a single thread, then there is no
>> race condition wrt the foobare'd impl of fetch-and-add.
>
> As soon as multiple threads are involved, one must assume a race
> condition wrt the standard.

Well, to clarify, not with the standard, but with the correct impl of an
atomic fetch-and-add. My code as is, has no racers wrt the std in any
conceivable scenario. Now, there can be special host systems that
schedule threads in a way where things can appear to work wrt the
fetch-and-add. The freedom of C++! :^)

Imvho, one must assume out-of-order counts in my busted fetch-and-add
when using more than one thread in pure standard C++.