Performance problems with rnd function while multi-threading

General FreeBASIC programming questions.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Performance problems with rnd function while multi-threading

Post by deltarho[1859] »

The following code illustrates that RND, out of the box, is not thread safe.

With '#define Twin False' I get 87 MHz which is what I would expect of Mersenne Twister on my machine.

With '#define Twin True' I get '16 MHz 16 MHz'.

This is indicative of massive collisions. That 16 MHz varies, sometimes it may be 15 MHz, 20 MHz and so on. So, the throughput has been seriously curtailed. Suppose the primary thread gets a RND update the secondary thread of execution gets nothing and will re-use the last RND it got which will have a profound effect on the distribution and, therefore, the randomness of RND. I have an Intel CPU with 4 cores/4 threads. Running RND in eight threads will see the throughput experienced in each thread drop like a stone and the randomness will be totally shot.

If we replace RND with my PCG32II, which is thread safe, I get 497 MHz with Twin as false and '495 MHz 521 MHz' with Twin as true. OK, the throughput's for Twin as true are not identical, but we are talking a multi-tasking operating system and I very much doubt that a user will notice. Running on eight threads will see about 4000 MHz of random floats being pushed through.

Code: Select all

#define Twin False
'#define Twin True

Dim As Ulong i
Dim As Double t1, y
Dim Shared As Double t2
Dim Shared As Ulong counter
Dim As Any Ptr hThread

Randomize

Sub SecondThread( byval dummy as any ptr)
Dim As Ulong i
Dim As Double y

  t2 = Timer
  For i = 1 To counter
    y = Rnd
  Next
  t2 = Timer - t2
End Sub

counter = 10^8 ' 100 million
#if Twin
  hThread = Threadcreate( @SecondThread, 0 )
#endif
t1 = Timer
For i = 1 To counter
  y = Rnd
Next
t1 = Timer - t1
#if Twin
  Threadwait( hThread )
#endif

#if Twin
  Print Int(100/t1);" MHz", Int(100/t2);" MHz"
#else
  Print Int(100/t1);" MHz"
#endif

Sleep

deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Performance problems with rnd function while multi-threading

Post by deltarho[1859] »

caseih wrote:Being slow doesn't make it unsafe.
I did another test with a small code edit. In the primary thread I included this

Code: Select all

For i = 1 To counter
  y = Rnd
  If y = copy then duplicate += 1
  copy = y
Next
and printed 'duplicate' at the end of the code.

With Twin as false I didn't get any duplication. With Twin as true, on three runs, I got duplicate as 27129, 25819, 19362. This is also indicative of collisions. On a duplication the secondary thread was getting the update.

It is worth noting that the edit will slow down the primary thread's throughput. Without the edit the collisions would be higher. Unsafe generators running faster than Mersenne Twister will see a greater percentage of collisions.

Provoni's comment is worth noting, there should be a note in Help advising RND is not threadsafe.
caseih
Posts: 2157
Joined: Feb 26, 2007 5:32

Re: Performance problems with rnd function while multi-threading

Post by caseih »

Fair enough.
fxm
Moderator
Posts: 12083
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Performance problems with rnd function while multi-threading

Post by fxm »

Indeed you are right.

The problem for noting this in the documentation is that lots of keywords are not thread-safe, and that it would be a very big job to test them all, in order to have a consistent documentation on this problem.
(but this is only my personal opinion)
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Performance problems with rnd function while multi-threading

Post by deltarho[1859] »

I don't have an axe to grind on this because I don't use Rnd.
Provoni
Posts: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Performance problems with rnd function while multi-threading

Post by Provoni »

fxm wrote:Indeed you are right.

The problem for noting this in the documentation is that lots of keywords are not thread-safe, and that it would be a very big job to test them all, in order to have a consistent documentation on this problem.
(but this is only my personal opinion)
But if you don't note that RND slows down when used across multiple threads then the documentation is also inconsistent with the expected behaviour. There is always two sides. :)
fxm
Moderator
Posts: 12083
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Performance problems with rnd function while multi-threading

Post by fxm »

KeyPgRnd → fxm [Rnd is not thread-safe]
+
#914 RND is not thread-safe
Provoni
Posts: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Performance problems with rnd function while multi-threading

Post by Provoni »

fxm wrote:KeyPgRnd → fxm [Rnd is not thread-safe]
+
#914 RND is not thread-safe
Thank you
badidea
Posts: 2586
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Performance problems with rnd function while multi-threading

Post by badidea »

You encryption experts probably know this, but just to be sure:
If you have 2 (or more) instances of a random number generator each in a separate thread, you do need to seed them differently. Else they produce the same number sequence.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Performance problems with rnd function while multi-threading

Post by deltarho[1859] »

badidea wrote:you do need to seed them differently.
It depends which generator you are using. If you use PCG32II or MsWs, threadsafe generators, they both have a Contructor which invokes their randomize function ( MyRandomize() ) using cryptographic random data so they will be seeded differently, and we have nothing to do. If we need a fixed seed it is a simple matter to call MyRandomize() with our chosen seeds.

As far as I know PCG32II and MsWS are the only two threadsafe generators for FreeBASIC. I use PCG32II because it has had further development and more features than you would expect from a generator and why I wrote a Help file for it, including an example of multithreading.
Post Reply