FreeBASIC's PRNG #2

[paul doe]

A final word on something which has not been mentioned. Bot PCG32II and MsWs have something in common: They are both thread safe.

MSWS (the class, not the PRNG) is thread safe by virtue of it being immutable. The state may be, but the class is not (there's no way to either modify or refer to the internal state from outside the class; you can only access copies of the current state through properties). Recall the code I posted in the second version of the MSWS class:

Code: Select all

/'
  ...
'/
?
? "How to clone your instance..."
?

var anotherRandomNumber = MsWs( _
  randomNumber.seed, _
  randomNumber.weilSequence, _
  randomNumber.sequence )

for i as integer = 1 to 100
  ? randomNumber.one(), anotherRandomNumber.one()
next


This shows a very simple basis for concurrency: all functions (or objects) are to be immutable (and, if at all possible, stateless; but I have yet to see a stateless PRNG =D), so they can be processed in parallel. The above code clones the instance, and then you have two PRNGs that will output the same values, at the same time (provided you call them synchronously, of course). Put each one of them in its own thread, and presto! Multithreaded RNG =D

[deltarho[1859]]

@paul doe

Quite so. I was actually referring to the code and not the PRNGs. On page #2 of this thread, I showed an example of using PCG32II in either a primary thread or a primary thread and a secondary thread. I didn't use a clone but two different sequences. With a quad-core and hyperthreading I could have 8*MsWs running at the same speed, roughly, churning out 4.8GB of random numbers. The mind boggles.

[jj2007]

Compliments, auguri, Glückwunsch, félicitations!

Code: Select all

#include "Windows.bi"
Dim shared As ULongInt m_x, m_weilSeq, randomNumber, sum

function MsWs() as ulong
  m_x *= m_x : m_weilSeq += &Hfedc65a1ce2d9587 : m_x += m_weilSeq
  m_x = ( m_x shr 32 ) or ( m_x shl 32 )
  return( m_x )
end function

Function Get64Bit() As UlongInt
  return (Cast( Ulongint, Rnd*(2^32) ) Shl 32) Or Cast( Ulongint, Rnd*(2^32) )
End Function

' optional:
' Randomize , 5
' m_x=Get64Bit()
' m_weilSeq=Get64Bit()

Dim as integer ticks
For i as integer=1 To 5
  ticks=GetTickCount()
  For i as integer=1 To 100000000
   ' asm int 3
   sum+=MsWs()
   asm nop
  Next
ticks=GetTickCount()-ticks
Print "Sum=";sum;" at ";ticks;" ms"
Next
sleep

Did you notice a difference between compilers...?

-arch x86_64 -gen gcc -Wc -O3 -s console

Code: Select all

Sum=214742728534211153 at  406 ms
Sum=429483246759424011 at  405 ms
Sum=644221988769156103 at  406 ms
Sum=858959962788555036 at  406 ms
Sum=1073703138807556447 at  405 ms

-t 8000 -s console

Code: Select all

Sum=214742728534211153 at  3151 ms
Sum=429483246759424011 at  3151 ms
Sum=644221988769156103 at  3136 ms
Sum=858959962788555036 at  3135 ms
Sum=1073703138807556447 at  3136 ms

I had a look under the hood, it's hilarious what the 32-bit compilers produce. What are you using?

[dafhi]

no anomalies between x86 and 64 here w/ -O 3

i wonder what could be the issue with my csg project. maybe i need shared ..

[paul doe]

no anomalies between x86 and 64 here w/ -O 3

He's referring to the GAS backend which, as you know, was coded by hand and does very basic optimizations (unlike GCC with -O3; -Ofast is even better, but far stricter with the code semantics)

i wonder what could be the issue with my csg project. maybe i need shared ..

What issues are you referring to?

[jj2007]

no anomalies between x86 and 64 here w/ -O 3

Can you post your 32-bit vs 64-bit timings with the code above? I am curious, since I get that factor 8 difference even with -O3 (GAS). With Gcc, it's 1.6 times slower in 32-bit. And a quick look under the hood reveals that gcc has never heard of the existence of SIMD instructions.

[dafhi]

timings:
421 ms .. 64 -O 3
545 ms .. 32

2900 .. 32 -O 2
1000 .. 64

@paul doe - in my source i wrote

Code: Select all

    I found problems with gcc -O 3 when requesting n-bit size > 32.  (check code example above)
    presumably not an issue with fbc 64.


[edit]

Code: Select all

    I found problems with gcc -O 3 when requesting n-bit size > 32.  (last section of code)
    presumably not an issue with fbc 64.


[paul doe]

Can you post your 32-bit vs 64-bit timings with the code above? I am curious, since I get that factor 8 difference even with -O3 (GAS).

GAS doesn't use the -O3 switch, that's for GCC.

And a quick look under the hood reveals that gcc has never heard of the existence of SIMD instructions.

GCC does indeed use SIMD, we just don't have any way to use it from FB (that I know of).

[paul doe]

@paul doe - in my source i wrote

Code: Select all

    I found problems with gcc -O 3 when requesting n-bit size > 32.  (check code example above)
    presumably not an issue with fbc 64.


Yes, I'm looking at it just now. I'll see what I can tell you.

[dafhi]

thank you :-)

it's also an issue x64

[deltarho[1859]]

Sum=214742728534211153 at 250 ms
Sum=429483246759424011 at 266 ms
Sum=644221988769156103 at 250 ms
Sum=858959962788555036 at 266 ms
Sum=1073703138807556447 at 265 ms

Sum=214742728534211153 at 1969 ms
Sum=429483246759424011 at 1937 ms
Sum=644221988769156103 at 1969 ms
Sum=858959962788555036 at 1953 ms
Sum=1073703138807556447 at 1969 ms

WinFBE 1.79 (gcc 8.1 fbc 1.06)

[deltarho[1859]]

I don't know exactly how Bernard Widynski created his seed.h and I have no justification for doing this other than a gut feeling but I replaced the s value taken from seed.h with a 64-bit prime number, namely the one used in PCG32 (&H5851F42D4C957F2D). I used MsWs(Get64Bit).

What I am about to show you is something that I have never seen before in all the years that I have using PractRand. If it was the first ever test on a PRNG I then I would have been concerned but sine MsWs is doing so well I am OK with it.

It is a PractRand 1TB clean sweep. Perhaps I was lucky and the next test with the seed.h s value would have been a clean sweep. I will try another test later.

UPDATE: Make that a PractRand 2 TB clean sweep.

Code: Select all

RNG_test using PractRand version 0.94
RNG = RNG_stdin32, seed = unknown
test set = core, folding = standard (32 bit)
 
rng=RNG_stdin32, seed=unknown
length= 256 megabytes (2^28 bytes), time= 2.7 seconds
  no anomalies in 165 test result(s)
 
rng=RNG_stdin32, seed=unknown
length= 512 megabytes (2^29 bytes), time= 5.7 seconds
  no anomalies in 178 test result(s)
 
rng=RNG_stdin32, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 11.4 seconds
  no anomalies in 192 test result(s)
 
rng=RNG_stdin32, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 22.3 seconds
  no anomalies in 204 test result(s)
 
rng=RNG_stdin32, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 43.3 seconds
  no anomalies in 216 test result(s)
 
rng=RNG_stdin32, seed=unknown
length= 8 gigabytes (2^33 bytes), time= 86.2 seconds
  no anomalies in 229 test result(s)
 
rng=RNG_stdin32, seed=unknown
length= 16 gigabytes (2^34 bytes), time= 170 seconds
  no anomalies in 240 test result(s)
 
rng=RNG_stdin32, seed=unknown
length= 32 gigabytes (2^35 bytes), time= 334 seconds
  no anomalies in 251 test result(s)
 
rng=RNG_stdin32, seed=unknown
length= 64 gigabytes (2^36 bytes), time= 673 seconds
  no anomalies in 263 test result(s)
 
rng=RNG_stdin32, seed=unknown
length= 128 gigabytes (2^37 bytes), time= 1342 seconds
  no anomalies in 273 test result(s)
 
rng=RNG_stdin32, seed=unknown
length= 256 gigabytes (2^38 bytes), time= 2650 seconds
  no anomalies in 284 test result(s)
 
rng=RNG_stdin32, seed=unknown
length= 512 gigabytes (2^39 bytes), time= 5353 seconds
  no anomalies in 295 test result(s)
 
rng=RNG_stdin32, seed=unknown
length= 1 terabyte (2^40 bytes), time= 10713 seconds
  no anomalies in 304 test result(s)

[paul doe]

I don't know exactly how Bernard Widynski created his seed.h and I have no justification for doing this other than a gut feeling but I replaced the s value taken from seed.h with a 64-bit prime number, namely the one used in PCG32 (&H5851F42D4C957F2D). I used MsWs(Get64Bit).

What I am about to show you is something that I have never seen before in all the years that I have using PractRand. If it was the first ever test on a PRNG I then I would have been concerned but sine MsWs is doing so well I am OK with it.

It is a PractRand 1TB clean sweep. Perhaps I was lucky and the next test with the seed.h s value would have been a clean sweep. I will try another test later.

UPDATE: Make that a PractRand 2 TB clean sweep.

Wow, very nice! Glad you're having so much fun! =D

Since Bernard asked me which values from seed.h do fail PractRand, I shall setup PractRand and conduct the tests myself, not to bother you (will take AGES here). Any assistance will be greatly appreciated =D

[paul doe]

Ok, setup's complete. David, would you mind posting your full command line for PractRand, so I can test it consistently with your results? If you've already posted them, sorry to ask =D.

My, it's ungodly slow here. It will take me ages to make a report for all the seeds. Hang on, Bernard! Don't die yet! I've just passed 128 MB XD

[deltarho[1859]]

Hi Paul. I use a very simple command line for PractRand.

<whatever.exe> | rng_test stdin32 -multithreaded

where <whatever.exe> is the name of the piping program.

On a side note if a test fails at PractRand's first hurdle then try

<whatever.exe> | rng_test stdin32 -tlmin 1KB -multithreaded

This will start PractRand at 1KB. I had to do this for the LCG tests which were failing at 4KB or 8KB.

On my machine the '-multithreaded' switch sees PractRand run about 25% faster.