* * *

Author Topic: Threadsafe Random  (Read 563 times)

Thaddy

  • Hero Member
  • *****
  • Posts: 3195
Threadsafe Random
« on: March 29, 2017, 08:18:46 am »
Random is not thread safe.
Would there be anything against declaring RandSeed and the state array of the Mersenne Twister as Threadvar?
That's all that is needed.
Then I can prepare a patch.
« Last Edit: March 29, 2017, 08:25:58 am by Thaddy »

Jonas Maebe

  • Hero Member
  • *****
  • Posts: 554
Re: Threadsafe Random
« Reply #1 on: March 29, 2017, 08:29:35 am »
Random will not be made thread-safe. An important property of the system unit's Random/RandSeed is that it provides a reproducible sequence of pseudo-random numbers based on the initial value of RandSeed. If you make it thread-safe and call it from multiple threads, that property can never be guaranteed unless you start recording/replaying in which order the threads called random(). That is obviously overkill, and impossible in many scenarios (threads can come and go at will).

If you need custom random functionality or do not require the properties of the system unit's random, use a custom random class/routine.

Thaddy

  • Hero Member
  • *****
  • Posts: 3195
Re: Threadsafe Random
« Reply #2 on: March 29, 2017, 08:52:20 am »
@Jonas
I already have such a beast (fully compatiblei). Would that be a candidate for inclusion? then I submit it.
It presumes every thread has its own fully independent Prng so data that relies on a sequence can only be used by that thread. The sequence is guaranteed for the thread (But it does mean that if data is stored and the Randseed is known the sequence is reproducable by a single threaded application.)
I also have a pair of fully Delphi compatible randoms (lcgrandom, see wiki) to include for if compatibility with Delphi's Random is required.. (E.g. for current data that relies on Delphi's random)
Third I have a set of Marsaglia Prng's and some more like that. (I also have WELLXXX, but that has license issue)
I would be willing to create a randoms unit a a single place to find all kind of different implementations is a uniform way.

Eugene Loza

  • Sr. Member
  • ****
  • Posts: 347
    • Decoherence Studio :)
Re: Threadsafe Random
« Reply #3 on: March 29, 2017, 11:45:48 am »
Castle Game Engine has a thread-safe xorshift random algorithm (with thread-safe random initialization) for this reason:
https://github.com/castle-engine/castle-engine/blob/master/src/base/castlerandom.pas
Actually the unit relies on CastleTimeUtils, however, it can be replaced with SysUtils.GetTickCount64 in FPC 3.x. and therefore be used independently of the Engine.
My games in Lazarus/CastleGameEngine:
Project Helena (TBS/RPG) http://sourceforge.net/projects/projecthelena/ (Alpha)
Fire Madness (bullet hell) https://github.com/eugeneloza/FireMadness/ (release candidate)
Decoherence: beyond Wizardry (RPG) https://github.com/eugeneloza/Mazer (just started)

Thaddy

  • Hero Member
  • *****
  • Posts: 3195
Re: Threadsafe Random
« Reply #4 on: March 29, 2017, 01:11:36 pm »
@ Eugene Loza
My purpose is to stick with standards - I happen to need this for statistics - , but still have a thread safe implementation if Multi-threaded..

To see what I mean I have attached what I am proposing to add to the rtl (this is not complete, I am re-defining everything into a common style):
This already works just like
a) Free Pascal if required
b) Delphi if required
c) (Not here, but in the codebase) C and C++ standards compatibility.

Essentially, eventually I would like to have pluggable Randoms, like in C++11 and higher.

The unit also shows that data  that relies on a specific pseudo random number generator (like Delphi's) can be processed by FPC if the source and seed are known.
This is all about randoms in the scientific sense (repeatable random sequences, A.K.A PRNG's) , not in a gaming sense.
« Last Edit: March 29, 2017, 01:22:44 pm by Thaddy »

Eugene Loza

  • Sr. Member
  • ****
  • Posts: 347
    • Decoherence Studio :)
Re: Threadsafe Random
« Reply #5 on: March 29, 2017, 01:22:35 pm »
This is all about randoms in the scientific sense (repeatable random sequences) , not in a gaming sense.
Oops. Sorry I've been unattentive - I didn't see who authored the first post :-[. I've seen your article on random generation :)  I've thought it was just another "general" question.
My games in Lazarus/CastleGameEngine:
Project Helena (TBS/RPG) http://sourceforge.net/projects/projecthelena/ (Alpha)
Fire Madness (bullet hell) https://github.com/eugeneloza/FireMadness/ (release candidate)
Decoherence: beyond Wizardry (RPG) https://github.com/eugeneloza/Mazer (just started)

Thaddy

  • Hero Member
  • *****
  • Posts: 3195
Re: Threadsafe Random
« Reply #6 on: March 29, 2017, 01:24:14 pm »
Tnx for re-reading, and understanding the matter! I would highly appreciate your opinion about the attached code, btw. :)

Eugene Loza

  • Sr. Member
  • ****
  • Posts: 347
    • Decoherence Studio :)
Re: Threadsafe Random
« Reply #7 on: March 29, 2017, 02:21:14 pm »
I would highly appreciate your opinion about the attached code, btw. :)
I'll try to have a closer look today evening (thou, I'm really not an experienced programmer :)).
At first glance: randomization is not thread-safe.
I.e. if one randomizes the generator in 8 semi-simultaneous threads, he'll get exactly the same random seeds (what is not really expected of threaded random generation).
I've found three sources of semi-random seed: current tickcount (as system.Randomize does, however, once one calls this function it results in an abrupt change in system's random seed (which might be unexpected if not documented properly) plus the "number of random sequences" is very limited e.g. regularly approx ~200 000 of possible high(longword) in xorshift or much more in Mersenne Twister), current date&time (yes, they are synchronous with tickcount, but still semi-independent, because they count from two different non-linked events) and memory allocation (e.g. trying to get address of a pointer to local variable, which is guaranteed to be different for different threads and has some extent of randomness of its own). Of course, one may just read /dev/urandom on Linux (maybe, with more caution on all *nix platforms) for much better results.
« Last Edit: March 29, 2017, 02:27:03 pm by Eugene Loza »
My games in Lazarus/CastleGameEngine:
Project Helena (TBS/RPG) http://sourceforge.net/projects/projecthelena/ (Alpha)
Fire Madness (bullet hell) https://github.com/eugeneloza/FireMadness/ (release candidate)
Decoherence: beyond Wizardry (RPG) https://github.com/eugeneloza/Mazer (just started)

Thaddy

  • Hero Member
  • *****
  • Posts: 3195
Re: Threadsafe Random
« Reply #8 on: March 29, 2017, 02:30:33 pm »
@Eugeno Loza:
You missed the point that all the state variables are threadvar. That is enough to make it threadsafe...  :D O:-) The rest of the code does not matter.
And if you look up Marsaglia in our wiki you will see I intend to also add these in the same way..
« Last Edit: March 29, 2017, 02:37:03 pm by Thaddy »

Eugene Loza

  • Sr. Member
  • ****
  • Posts: 347
    • Decoherence Studio :)
Re: Threadsafe Random
« Reply #9 on: March 29, 2017, 02:45:14 pm »
You missed the point that all the state variables are threadvar.
emm... maybe no.
I'm not speaking of random being non-threadsafe. I'm speaking of randomization being non-treadsafe (maybe I'm using a wrong terminology).
Saying that I mean that if we start 2 simultaneous threads and randomize the random - simultaneously - system.Random will return equal random seeds.
And therefore 2 identical random sequences will be spawned.
(yes, it has been addressed many times, that re-using Randomize actually harms random and should be used only once per program)

Yes, I'm thinking from game point of view :)
I'm generating a maze. I can generate 8 mazes simultaneously on my 8-core CPU.
I create (almost simultaneously) 8 generation threads each initializing its own random seed.
If I won't make precautions and use system.Randomize (or directly gettickcount) I'll get 8 identical mazes instead of 8 different mazes.

Moreover, I count that system.random following a deterministic pseudo-random sequence.
If I start a threaded random I'll have a background call to system.Randomize which will break the deterministic random sequence.
E.g. if I want to have a one thread that uses system.Random with a predefined seed, and my threaded random will run (randomize) in background. I'll get different results with the same predefined seed. In other words, I count that if I have a seed "123" it should generate identical maze. But once launched the thread I find myself with a different mazes with nearly impossible to get the reason that caused it.

One more point is that when I launch the computer, gettickcount is zero. E.g. let's imagine a situation. I come home. I launch the computer to play my maze. Eventually I find myself in the very same maze I've been playing yesterday! Why? Because gettickcount while has a step of less than a second, but updates only 64 times per second, therefore, if I launch the game at the very same second after start-up I get only 64 variants for my mazes, one minute gives less than 4000 variants, which is while large, but still can repeat by accident.
Quote
And if you look up Marsaglia in our wiki you will see I intend to also add these in the same way..
Missed the update of your post. I've read this article, but I should look closer.
(upd) No, that wiki article doesn't deal with randomization... Yes, it's a fantastic collection of algorithms, but I was speaking of randomization (which might be used in any random number generation algorithm).
« Last Edit: March 29, 2017, 04:13:18 pm by Eugene Loza »
My games in Lazarus/CastleGameEngine:
Project Helena (TBS/RPG) http://sourceforge.net/projects/projecthelena/ (Alpha)
Fire Madness (bullet hell) https://github.com/eugeneloza/FireMadness/ (release candidate)
Decoherence: beyond Wizardry (RPG) https://github.com/eugeneloza/Mazer (just started)

Thaddy

  • Hero Member
  • *****
  • Posts: 3195
Re: Threadsafe Random
« Reply #10 on: March 29, 2017, 05:05:03 pm »
The goal is to provide Pseudo random number generators (Prng's) that are:
- a) thread safe within the limitation that a given thread will have its own independent random generator. This goal is achieved for FPC with my code.
- b) provide a compatibility mode with Delphi to be able to process Delphi generated statistical data in a verifiably identical way.This goal is also achieved with my code
- c) provide a compatibility option to use Data that relies on a particular Prng to be processed with FPC. This goal is achieved for MT19937(In  C++11+ standards) and others just need code clean up.

The underlying rationale is that Prng's are often used in science and statistics to generate tests for conformity. These tests assume a defined Prng. A Defined, plugable, Prng is something that e.g. C++11 already has.
I am trying to provide the same feature for Free Pascal because it is important in the fields of statistics, computer science and science in general.
The average programmer does not care about all this. But scientists and statisticians care  *a lot* about this.

Problem is most people on the forum do not know the difference between a Prng and truly random - in grumpy mode I would write j*ck sh*t  >:D  :D ;)- they often do not even know that a Prng has a repeatable sequence on purpose. Worse, you will get silly comments... sigh... (not yours)
Which makes it hard to explain in layman computing terms. Trust me. It is important for the language.
If you find a flaw in the code your critique is appreciated within this context:
- the threads have their own, repeatable and afterwards  reproducible, random if the seed is known, that is totally independent from the same random generator in other threads.
- the Prng's that pretend to implement a certain compatibility can be verified to provide that compatibility.

Note that Jonas Maebe's comment was geared towards another kind of thread safety: that where the Random number generator is a singleton Prng per process and access to e.g. RandSeed is handled in a thread safe manner.
That's NOT what my code is for. My code is about having a singleton Prng on a per thread basis. I can already prove this approach works. And it makes more sense.
Probably Jonas can confirm this given this explanation. Jonas wrote the Mersenne Twister that FPC uses and he knows in depth about the theory behind it.
« Last Edit: March 29, 2017, 05:48:25 pm by Thaddy »

 

Recent

Get Lazarus at SourceForge.net. Fast, secure and Free Open Source software downloads Open Hub project report for Lazarus