Code1.bas simply calculates an estimate of the speed of FreeBASIC's default random number generator, the Mersenne Twister(MT).

The eagle-eyed amongst you will see that I am forcing the code to run on a single core which may seem a bit daft for just a primary thread but more of that shortly.

Running the code as is gives me: 87 mill/sec.

Nothing unusual there.

If we now remove the comment from the line 'hThread = ...' and swap the Prints to display two speeds instead of just one, I now get: 45 mill/sec 45 mill/sec.

Nothing unusual there. Although we are using a secondary thread of execution because of a single core the 'bandwidth' of MT gets halved.

If we now comment the three line single core code starting with 'Dim hProcess As Handle' I get this: 16 mill/sec 16 mill/sec.

Clearly, something decidedly untoward has occurred.

There is only one instance of RND and the two cores are 'fighting over it' - we have memory collisions. RND is not thread safe. Windows will do some very fancy caching but we have made its life difficult. The faster the generator the greater the likelihood of collisions and the greater the 'throttling'.

The bad news is that we have the same problem with all the generators that I have published here and any that you may have written.

The good news is that all mine can be made thread safe and yours as well. There is a simple solution: Code duplication.

Taking my PCG32, for example, all instances of PCG32 was firstly replaced with PCG32A and then with PCG32B. Code2.bas sees the primary thread using PCG32A and the secondary thread using PCG32B.

As is, Code2.bas has 'hThread = ...' commented and just one timing Print giving me: 208 mill/sec.

If we now remove the comment from the line 'hThread = ...' and swap the Prints to display two speeds instead of just one, I now get: 208 mill/sec 205 mill/sec.

Look ma, no collisions. <smile>

There is a bonus in using PCG - the state vector has two Ulongints: state and inc. If we ensure that inc is not the same for each generator not only do we get independent generators but different sequences as well.

If more than two threads require random numbers it may be worthwhile to examine the code duplication with a view to condensing to the original number of functions with some parameter passing but in the above example I don't think it worth the effort and, of course, any parameter passing will slow the generators.

So, how many applications do I have requiring random numbers in two or more threads?

I don't have any - but what has that got to do with it. <laugh>

Code1.bas

Code: Select all

`#include once "windows.bi"`

Dim As Ulong i

Dim As Double t1, y

Dim Shared As Double t2

Dim Shared As Ulong ltime

Dim As Any Ptr hThread, x

Sub SecondThread( x As Any Ptr)

Dim As Ulong i

Dim As Double y

t2 = Timer

For i = 1 To ltime

y = Rnd

Next

t2 = Timer - t2

End Sub

Dim hProcess As Handle

hProcess = GetCurrentProcess()

SetProcessAffinityMask( hProcess, 1) ' ie CPU 0

ltime = 100000000

'hThread = ThreadCreate( @SecondThread, 0 )

t1 = Timer

For i = 1 To ltime

y = Rnd

Next

t1 = Timer - t1

Threadwait( hThread )

Print Int(100/t1);" mill/sec"

'Print Int(100/t1);" miil/sec", int(100/t2);" mill/sec"

Sleep

Code2.bas

Code: Select all

`' Generator PCG32A`

Type pcg32A_random_t

As Ulongint state, inc

End Type

Dim Shared pcg32A As pcg32A_random_t

Function pcg32A_random_r(Byval rng As pcg32A_random_t Ptr) As Ulong

Dim As Ulongint oldstate = rng->state

' Advance internal state

rng->state = oldstate * 6364136223846793005ULL + (rng->inc Or 1)

'' Calculate output function (XSH RR), uses old state for max ILP

' rotate32((state ^ (state >> 18)) >> 27, state >> 59)

Dim As Ulong xorshifted = ((oldstate Shr 18u) xor oldstate) Shr 27u

Dim As Ulong rot = oldstate Shr 59u

Return (xorshifted Shr rot) Or (xorshifted Shl ((-rot) And 31))

End Function

Sub Randomizepcg32A( Seed As Ulongint = 0 )

Dim i As Integer

If Seed = 0 Then

Randomize , 5

pcg32A.state = Rnd*(2^64)

pcg32A.inc = Rnd*(2^63)

Else

pcg32A.state = Seed

End If

For i As Integer = 1 To 200

pcg32A_random_r(@pcg32A)

Next i

End Sub

Function pcg32AS() As Single

Dim TempVar As Ulong

Dim rng As pcg32A_random_t Ptr = @pcg32A

Dim As Ulongint oldstate = rng->state

'' Advance internal state

rng->state = oldstate * 6364136223846793005ULL + (rng->inc Or 1)

'' Calculate output function (XSH RR), uses old state for max ILP

Dim As Ulong xorshifted = ((oldstate Shr 18u) xor oldstate) Shr 27u

Dim As Ulong rot = oldstate Shr 59u

Tempvar = (xorshifted Shr rot) Or (xorshifted Shl ((-rot) And 31))

Asm

mov eax, dword Ptr [TempVar]

movd xmm0, eax

psrlq xmm0, 9

mov eax, 1

cvtsi2ss xmm1, eax

por xmm0, xmm1

subss xmm0, xmm1

movd [Function], xmm0

End Asm

End Function

' Generator PCG32B

Type pcg32B_random_t

As Ulongint state, inc

End Type

Dim Shared pcg32B As pcg32B_random_t

Function pcg32B_random_r(Byval rng As pcg32B_random_t Ptr) As Ulong

Dim As Ulongint oldstate = rng->state

' Advance internal state

rng->state = oldstate * 6364136223846793005ULL + (rng->inc Or 1)

'' Calculate output function (XSH RR), uses old state for max ILP

' rotate32((state ^ (state >> 18)) >> 27, state >> 59)

Dim As Ulong xorshifted = ((oldstate Shr 18u) xor oldstate) Shr 27u

Dim As Ulong rot = oldstate Shr 59u

Return (xorshifted Shr rot) Or (xorshifted Shl ((-rot) And 31))

End Function

Sub Randomizepcg32B( Seed As Ulongint = 0 )

Dim i As Integer

If Seed = 0 Then

Randomize , 5

pcg32B.state = Rnd*(2^64)

pcg32B.inc = Rnd*(2^63)

Else

pcg32B.state = Seed

End If

For i As Integer = 1 To 200

pcg32B_random_r(@pcg32B)

Next i

End Sub

Function pcg32BS() As Single

Dim TempVar As Ulong

Dim rng As pcg32B_random_t Ptr = @pcg32B

Dim As Ulongint oldstate = rng->state

'' Advance internal state

rng->state = oldstate * 6364136223846793005ULL + (rng->inc Or 1)

'' Calculate output function (XSH RR), uses old state for max ILP

Dim As Ulong xorshifted = ((oldstate Shr 18u) xor oldstate) Shr 27u

Dim As Ulong rot = oldstate Shr 59u

Tempvar = (xorshifted Shr rot) Or (xorshifted Shl ((-rot) And 31))

Asm

mov eax, dword Ptr [TempVar]

movd xmm0, eax

psrlq xmm0, 9

mov eax, 1

cvtsi2ss xmm1, eax

por xmm0, xmm1

subss xmm0, xmm1

movd [Function], xmm0

End Asm

End Function

'--------------------------------------------

Dim As Ulong i

Dim As Double t1, y

Dim Shared As Double t2

Dim Shared As Ulong ltime

Dim As Any Ptr hThread, x

Sub SecondThread( x As Any Ptr )

Dim As Ulong i

Dim As Double y

t2 = Timer

For i = 1 To ltime

y = PCG32BS

Next

t2 = Timer - t2

End Sub

Randomizepcg32A

Randomizepcg32B

ltime = 100000000

'hThread = ThreadCreate( @SecondThread, 0 )

t1 = Timer

For i = 1 To ltime

y = PCG32AS

Next

t1 = Timer - t1

Threadwait( hThread )

Print Int(100/t1);" mill/sec"

'Print Int(100/t1);" miil/sec", int(100/t2);" mill/sec"

Sleep