A simple PRNG using /dev/urandom

[hMx]

Here's some C++ source code for a PRNG (pseudorandom number generator) which uses guarded access to the kernel's /dev/urandom device.

This very much looks like a RNG, without any pseudo. What do I miss?

/dev/random and /dev/urandom are PRNG. They take environmental noise (or hardware RNG output), and do some math with it to make a pseudo-random stream with the desired distribution.

I don't understand. Transforming a RNG stream will yield another RNG stream (with maybe another distribution), but not any pseudorandom stream. Please also see wikipedia about the pseudo, https://en.wikipedia.org/wiki/Pseudorandomness :

A pseudorandom process is a process that appears to be random but is not. Pseudorandom sequences typically exhibit statistical randomness while being generated by an entirely deterministic causal process. Such a process is easier to produce than a genuinely random one, and has the benefit that it can be used again and again to produce exactly the same numbers - useful for testing and fixing software.

Sorry for being nitpicking. I like the RNG, but I think the name PRNG is misleading, here.

precisely because of that definition you just quoted, the kernel RNG has been called a PRNG in recent times. The interrupts and network traffic and what not that feed timestamps into the entropy pool while very hard to predict are not truly random. About the only thing that seems to be allowed to call itself truly random these days has to be based off quantum effects.

I do understand that the kernel RNG is not the best possible RNG. But it is also not an entirely deterministic causal process. For me, pseudo-random implies that it can be repeated, and that is not the case here. One may call the kernel RNG a weak one, or a not truely one, but not a pseudo one, I find that misleading.[/i]

[sje]

1e+8 random games in three hours which needed about 124 GiB read from /dev/urandom (ca. 12 MiB/second). The /dev/urandom throughput is the limiting factor with on average 4.5 of the 8 hyperthreads being blocked waiting.

Code: Select all

[] rg 100000000
   checkmate 15308505 0.153085
  fiftymoves 19340471 0.193405
insufficient 56714899 0.567149
  repetition  2517152 0.0251715
   stalemate  6118973 0.0611897
Average ply length: 334.34
Maximum ply length: 1037
PT: 10:34:46.844
WT: 3:03:38.892

[sje]

1e+8 random games, again, but this time using two bytes from /dev/urandom instead of four for each random move pick.

Code: Select all

[] rg 100000000
   checkmate 15301890 0.153019
  fiftymoves 19341065 0.193411
insufficient 56717240 0.567172
  repetition  2518543 0.0251854
   stalemate  6121262 0.0612126
Average ply length: 334.36
Maximum ply length: 1055
PT: 9:24:54.925
WT: 1:54:15.471

[sje]

The above were generated on Mac OS/X machines. The following was made on a quad core 3.1 GHz AMD Athlon II X4 box:

Code: Select all

[] rg 100000000
   checkmate 15313187 0.153132
  fiftymoves 19338722 0.193387
insufficient 56709782 0.567098
  repetition  2518753 0.0251875
   stalemate  6119556 0.0611956
Average ply length: 334.331
Maximum ply length: 1067
PT: 8:02:30.765
WT: 2:01:12.606

Note that the /dev/urandom draw here is able to match the need of the game generation.

----
From:

https://en.wikipedia.org/wiki/Compariso ... generators

See:

http://www.seeedstudio.com/depot/FST01- ... -1279.html

http://ubld.it/products/truerng-hardwar ... generator/

https://www.tindie.com/products/Wayward ... ite-noise/

http://www.moonbaseotago.com/onerng/

Buy one of each and XOR the streams.

[matthewlai]

Revised code with buffering and selectable thread safety:

Code: Select all

#define PRNGBufferLen BX(20)

class PRNG
{
public:
  PRNG(const bool issafe);
  ~PRNG(void);

  ui32 NextDwrd(void);
  ui64 NextQwrd(void);
  
  ui Pick(const ui bound);
  
private:
  void LoadBuffer(void);
  void ReadFromBuffer(ui8Ptr const targetptr, const ui count);
  
  bool           isthreadsafe;
  std::ifstream *ifsptr;
  SpinLockPtr    spinlockptr;
  ui8Ptr         bufferptr;
  ui             offset;
};

Code: Select all

PRNG::PRNG(const bool issafe)
{
  isthreadsafe = issafe;
  ifsptr = new std::ifstream("/dev/urandom", std::ios::binary);
  spinlockptr = new SpinLock();
  bufferptr = new ui8[PRNGBufferLen];
  LoadBuffer();
}

PRNG::~PRNG(void)
{
  delete [] bufferptr;
  delete spinlockptr;
  delete ifsptr;
}

void PRNG::LoadBuffer(void)
{
  ifsptr->read((char *) bufferptr, PRNGBufferLen);
  offset = 0;
}

void PRNG::ReadFromBuffer(ui8Ptr const targetptr, const ui count)
{
  ui8Ptr tptr = targetptr;
  
  if (isthreadsafe)
    spinlockptr->Lock();

  ZOL(index, count)
  {
    if (offset == PRNGBufferLen)
      LoadBuffer();
    *tptr++ = bufferptr[offset++];
  };

  if (isthreadsafe)
    spinlockptr->Unlock();
}

ui32 PRNG::NextDwrd(void)
{
  ui32 nextdwrd;

  ReadFromBuffer((ui8Ptr) &nextdwrd, sizeof(nextdwrd));
  return nextdwrd;
}

ui64 PRNG::NextQwrd(void)
{
  ui64 nextqwrd;
  
  ReadFromBuffer((ui8Ptr) &nextqwrd, sizeof(nextqwrd));
  return nextqwrd;
}

ui PRNG::Pick(const ui bound)
{
  ui pick = 0;
  
  if (bound == 0)
    Die("PRNG::Pick", "zero bound");
  else
  {
    if (bound > 1)
    {
      const ui range = -bound % bound;
      ui next = NextDwrd();
      
      while &#40;next < range&#41;
        next = NextDwrd&#40;);
      pick = next % bound;
    &#125;;
  &#125;;
  return pick;
&#125;

A little off topic here, but is there a reason for all those things to be pointers? It seems like they can just be regular members and there would be no need for heap allocation/deallocation (of course, in C++11 or Boost, smart pointers would be another safe option).

Also for "isthreadsafe", it may be faster to make it a template parameter instead, so compiler can optimize it out completely if you don't need it.

[sje]

A little off topic here, but is there a reason for all those things to be pointers? It seems like they can just be regular members and there would be no need for heap allocation/deallocation (of course, in C++11 or Boost, smart pointers would be another safe option).

Also for "isthreadsafe", it may be faster to make it a template parameter instead, so compiler can optimize it out completely if you don't need it.

Pointers to member objects are quite useful for several reasons.

1. Source files which include header files may not need to also include header files for member objects as long as there is a forward declaration file included. In Symbolic, every class has a forward declaration as a class plus a declaration for a pointer to that class; this is all stuck in the header file Forward.h and every C++ file includes that. So, better encapsulation and less chance for unnecessary dependency.

2. When a thread is created, it usually gets only a moderately sized stack segment. If auto allocation objects are large. then there is the danger of undetected stack overflow when the thread runs. In fact, this would happen in the above code if more than a single PRNG instance (if it had a full megabyte buffer instead of a pointer to that buffer) were allocated on the thread stack. Using heap allocation avoids all such danger.

----

The PRNG class is too simple for template usage.

[AlvaroBegue]

The problem with having raw pointers as members is that your code is not exception safe (what happens if a constructor throws an exception?). To help with that you should probably use something like std::unique_ptr for individual objects and std::vector for arrays.

[matthewlai]

Pointers to member objects are quite useful for several reasons.

1. Source files which include header files may not need to also include header files for member objects as long as there is a forward declaration file included. In Symbolic, every class has a forward declaration as a class plus a declaration for a pointer to that class; this is all stuck in the header file Forward.h and every C++ file includes that. So, better encapsulation and less chance for unnecessary dependency.

2. When a thread is created, it usually gets only a moderately sized stack segment. If auto allocation objects are large. then there is the danger of undetected stack overflow when the thread runs. In fact, this would happen in the above code if more than a single PRNG instance (if it had a full megabyte buffer instead of a pointer to that buffer) were allocated on the thread stack. Using heap allocation avoids all such danger.

----

The buffer is the only thing that is really large. A std::vector can still be used for example, to automatically manage the buffer on the heap.

It's good to think about dependencies, but it significantly complicates the code in this case (especially if you want to do things like exceptions later), and can make it slower. Circular dependencies doesn't really happen that often when you have a well thought-out design.

The PRNG class is too simple for template usage.

What does complexity have to do with using templates or not? It just requires declaring the template parameter, and then you can use it just like a variable, except it won't actually take up space, and the compiler won't actually have to check it at run time.

[sje]

Many template classes from the STL introduce unneeded complexity plus inefficiency (like autosizing vectors). Symbolic uses templates (as inherited classes), but they're templates which I wrote myself.

Using pointers for potentially large objects works well because I (and the compiler) always know the size of a pointer regardless of what it points to. Therefore, thread stack space exhaustion becomes a non-issue.

If I can get by well without a language feature, then I don't use that feature. Less complexity = better code = easier debugging. In my book, that is. Your book may be different.

[matthewlai]

Many template classes from the STL introduce unneeded complexity plus inefficiency (like autosizing vectors). Symbolic uses templates (as inherited classes), but they're templates which I wrote myself.

Using pointers for potentially large objects works well because I (and the compiler) always know the size of a pointer regardless of what it points to. Therefore, thread stack space exhaustion becomes a non-issue.

If I can get by well without a language feature, then I don't use that feature. Less complexity = better code = easier debugging. In my book, that is. Your book may be different.

There is nothing inefficient about vectors if you just allocate all the memory you need in the beginning, like you are doing already -

Code: Select all

std&#58;&#58;vector<u8> buffer&#40;bufferSize&#41;;

The performance will be exactly the same as a raw pointer.

The size of a vector on the stack is also constant (and very small), regardless of how big the vector is.

In exchange, you get exception safety, no need to manage your own dynamic memory (with absolutely no performance hit), and less chance for bugs.

It depends on your definition of "complexity". I wouldn't say using a template parameter is more complex than adding a member variable, if you are familiar with both. It's about the same number of lines of code, and the code isn't any more complex. My book is different. My book is to use the most suitable language features for each task, even if I can do it without. In this case, a template parameter is more conceptually intuitive (because it essentially says you have 2 variants of the class, doing slightly different things), may be faster, and isn't more complex in code.

There are many things in C++ you can do without - smart pointers, standard library containers, exceptions, etc. Using them just makes the code simpler, more intuitive, and most importantly safer. I wouldn't say using a new language feature is always introducing complexity.