Fast random integers

General FreeBASIC programming questions.
dodicat
Posts: 5937
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Fast random integers

Postby dodicat » Oct 17, 2018 18:48

Nice Graphics example for #4 deltarho.
Of course #4 is 100% predictable.

Code: Select all

 

randomize ,4
redim as double a(16777216)
for n as long=0 to 16777216
    a(n)=rnd
next
print "Press a key at will"

dim as string key
dim as long counter
do
    counter+=1
    var r=rnd
    key=inkey
    if len(key) then
        print "Random value  ";tab(25); r
        for n as long=0 to ubound(a)
            if a(n)=r then
                print "Next value forecast ";tab(25); a(n+1)
                exit for
                end if
            next
            print "Next value is ";tab(25); rnd
            print "Loop counter ";tab(25);counter
            print
    end if
loop until key=chr(27)
sleep

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

Re: Fast random integers

Postby deltarho[1859] » Oct 17, 2018 20:15

Provoni wrote:I would also like to test PCG32II but have no clue how to use it.

It is your lucky day. See the link at the bottom of the opening post here.
And possibly also a small example of how you determine the Mhz of a RNG?

Code: Select all

#Include "PCG32II.bas"
Dim As Ulong i, n = 10^8
Dim As Double t, x
Dim As pcg32 pcg
t = Timer
For i =1  To n
  x = pcg.randse ' Double - 32-bit granularity
Next
t = Timer - t
Print Int(100/t);" MHz"
Sleep
deltarho[1859]
Posts: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Re: Fast random integers

Postby deltarho[1859] » Oct 17, 2018 20:22

dodicat wrote:Nice Graphics example for #4 deltarho.

That stretched my graphics ability. <laugh>
Of course #4 is 100% predictable.

Which has given me an idea - the 100% bit I mean.

I won't mention what I am thinking about because it may not come to anything. Most of my ideas don't but as long as they keep coming every now and again one of them hits terra firma.
badidea
Posts: 1543
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Fast random integers

Postby badidea » Oct 17, 2018 20:34

I cannot run PCG32II, but would a speed measurement like this not be better:

Code: Select all

Dim As Ulong i, n = 10^8
Dim As Double t, x, dt0, dt1

'dummy loop
t = Timer
For i = 1  To n
   x = 0
Next
dt0 = Timer - t

'rnd loop
t = Timer
For i = 1  To n
   x = rnd
Next
dt1 = Timer - t

Print Int(100/(dt0));" MHz"
Print Int(100/(dt1));" MHz"
Print Int(100/(dt1-dt0));" MHz"
Sleep
deltarho[1859]
Posts: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Re: Fast random integers

Postby deltarho[1859] » Oct 17, 2018 22:38

badidea wrote:but would a speed measurement like this not be better

No, because the loop overhead is not influential.

On my machine: ( dt1 - dt0 )/dt1 = 0.9999999121202331
I cannot run PCG32II

Why not?
badidea
Posts: 1543
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Fast random integers

Postby badidea » Oct 17, 2018 23:16

I did get a significant difference, maybe your c-compiler back-end understands that the first loop does nothing? And reduces it to nothing?

I saw a windows.bi which my pc probably does not understand.
Last edited by badidea on Oct 18, 2018 19:44, edited 1 time in total.
deltarho[1859]
Posts: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Re: Fast random integers

Postby deltarho[1859] » Oct 18, 2018 0:10

badidea wrote:And reduces it to nothing?

Good point, I keep forgetting that.

Previously, 0.9999999121202331 indicates seven significant figures when I only wanted four at most.

Inserting 'asm nop' stops the compiler messing with the loop.

Code: Select all

For i = 1  To n
   x = 0
   asm nop
Next

I now get 0.9483 indicating less than one significant figure giving "a significant difference". <smile>
I saw a windows.bi which my pc probably does not understead.

windows.bi is only used in this code so only if the target is Win32

Code: Select all

#ifdef __FB_WIN32__
  #Include Once "windows.bi"
  #Inclib "bcrypt"
  #Include Once "win/wincrypt.bi"
  ........
Provoni
Posts: 318
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Fast random integers

Postby Provoni » Oct 18, 2018 8:27

Instead of using "asm nop" it is better to do "x += rnd" and print x after the measurement because then the compiler can still do loop optimizations resulting in a higher and more realistic Mhz.
deltarho[1859]
Posts: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Re: Fast random integers

Postby deltarho[1859] » Oct 18, 2018 10:59

Provoni wrote:Instead of using "asm nop" it is better to do "x += rnd" and print x after the measurement because then the compiler can still do loop optimizations resulting in a higher and more realistic Mhz.

I am using 'asm nop' in the dummy loop. You are not suggesting we use 'x += rnd' in the dummy loop, are you?

Although 'asm nop' tells the compiler to 'back off' it introduces its own distortion. We should also include 'asm nop' in the rnd loop so that it gets eliminated in the 'dt1-dto' calculation.

All seemed to be going well with most of the generators showing higher 'true' speeds until I tested CryptoS in CryptoRNDII where I got a negative MHz. It transpired that the rnd loop was running faster than the dummy loop which is, obviously, nonsense. There wasn't much in it but the result was negative nonetheless.

I then swapped the order of execution - rnd loop and then dummy loop. This time the rnd loop was far to slow compared to the dummy loop giving much smaller MHz. I increased the loops from 10^8 to 10^9; 10^8 is too small considering the speed of the generators. I then increased the tests from 1 to 9 so as to use the median and included a small Sleep between them to avoid the 9 tests running without allowing some idle time between them.

I sometimes think that with all the shenanigans going on executing code in the CPU cache compared to years gone by and optimizing compilers sometimes being too clever for their own good when it comes to our timing code we are on a hiding to nothing.

Why 'x = CryptoS' seems to be faster than 'x = 0' is testing me somewhat.

This is why I favor giving generators a specific task and then compare how much work they get through given the same time for each of them to do their stuff. The question then is do we test all in one application or test them individually to avoid the order of execution anomaly.

BTW, Provoni, did you get the PCG32II Help file?
jj2007
Posts: 1230
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Fast random integers

Postby jj2007 » Oct 18, 2018 12:22

deltarho[1859] wrote:All seemed to be going well with most of the generators showing higher 'true' speeds until I tested CryptoS in CryptoRNDII where I got a negative MHz.
Is that reproducible? There is no such thing as negative cycles, but there are situations where you start measuring on one core and finish measuring on another one. On Windows, try SetThreadAffinityMask(GetCurrentThread(), 1). Or use QueryPerformanceCounter, which is what Micros**t recommends.
deltarho[1859]
Posts: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Re: Fast random integers

Postby deltarho[1859] » Oct 18, 2018 13:53

@jj2007

I tried SetThreadAffinityMask(GetCurrentThread(), 1) but to no avail. I wasn't surprised because my CPU has an invariant time stamp and the Performance Counter is synched with all cores so context switching is neither here nor there.

I am getting a negative cycle because I am getting one code block running faster than another when it absolutely should not. I get different timings when I swap the code blocks.

I will go through the code with a fine tooth comb.
deltarho[1859]
Posts: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Re: Fast random integers

Postby deltarho[1859] » Oct 18, 2018 14:18

Tried something else first. I don't get a negative cycle if I don't use any compiler optimization.

With optimization, the code block which should run slower is being optimized to a greater extent than the code block which should run faster. I cannot believe this. Back to plan A - fine tooth comb. <laugh>
badidea
Posts: 1543
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Fast random integers

Postby badidea » Oct 18, 2018 17:32

deltarho[1859] wrote:windows.bi is only used in this code so only if the target is Win32

Check, PCG32II with your test program (above) works fine.
Provoni
Posts: 318
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Fast random integers

Postby Provoni » Oct 18, 2018 18:41

deltarho[1859] wrote:Why 'x = CryptoS' seems to be faster than 'x = 0' is testing me somewhat.

I cannot reproduce this, x = cryptos is always slower than x = 0 for me:

Code: Select all

screenres 640,480,32

dim as double t,x
dim as ulongint i,n=10^8

Const _WIN32_WINNT = &h0602
'#define algo 2 ' For Intel RdRand
#Include "CryptoRndII.bas"

t=timer
For i = 1  To n
   x = 0
   asm nop
next
print timer-t

t=timer
For i = 1  To n
   x = cryptos
   asm nop
next
print timer-t

sleep
dodicat
Posts: 5937
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Fast random integers

Postby dodicat » Oct 18, 2018 19:32

Same here
Win 10
64 bit
-gen gcc -Wc -O3
0.03730944660492241
1.863307968946174

I am using the official 1.05.0 build.
I don't have gcc 8.1 or 8.2, or fb 1.06

Return to “General”

Who is online

Users browsing this forum: No registered users and 29 guests