## Fast random integers

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

### Re: Fast random integers

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

Code: Select all

` randomize ,4redim as double a(16777216)for n as long=0 to 16777216    a(n)=rndnextprint "Press a key at will"dim as string keydim as long counterdo    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 ifloop until key=chr(27)sleep     `
deltarho[1859]
Posts: 2157
Joined: Jan 02, 2017 0:34
Location: UK

### Re: Fast random integers

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^8Dim As Double t, xDim As pcg32 pcgt = TimerFor i =1  To n  x = pcg.randse ' Double - 32-bit granularityNextt = Timer - tPrint Int(100/t);" MHz"Sleep`
deltarho[1859]
Posts: 2157
Joined: Jan 02, 2017 0:34
Location: UK

### Re: Fast random integers

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.
Posts: 1774
Joined: May 24, 2007 22:10
Location: The Netherlands

### Re: Fast random integers

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

Code: Select all

`Dim As Ulong i, n = 10^8Dim As Double t, x, dt0, dt1'dummy loopt = TimerFor i = 1  To n   x = 0Nextdt0 = Timer - t'rnd loopt = TimerFor i = 1  To n   x = rndNextdt1 = Timer - tPrint Int(100/(dt0));" MHz"Print Int(100/(dt1));" MHz"Print Int(100/(dt1-dt0));" MHz"Sleep`
deltarho[1859]
Posts: 2157
Joined: Jan 02, 2017 0:34
Location: UK

### Re: Fast random integers

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?
Posts: 1774
Joined: May 24, 2007 22:10
Location: The Netherlands

### Re: Fast random integers

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: 2157
Joined: Jan 02, 2017 0:34
Location: UK

### Re: Fast random integers

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 nopNext`

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: 347
Joined: Jan 05, 2014 12:33
Location: Belgium

### Re: Fast random integers

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: 2157
Joined: Jan 02, 2017 0:34
Location: UK

### Re: Fast random integers

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: 1318
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

### Re: Fast random integers

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: 2157
Joined: Jan 02, 2017 0:34
Location: UK

### Re: Fast random integers

@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: 2157
Joined: Jan 02, 2017 0:34
Location: UK

### Re: Fast random integers

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>
Posts: 1774
Joined: May 24, 2007 22:10
Location: The Netherlands

### Re: Fast random integers

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: 347
Joined: Jan 05, 2014 12:33
Location: Belgium

### Re: Fast random integers

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,32dim as double t,xdim as ulongint i,n=10^8Const _WIN32_WINNT = &h0602'#define algo 2 ' For Intel RdRand#Include "CryptoRndII.bas"t=timerFor i = 1  To n   x = 0   asm nopnextprint timer-tt=timerFor i = 1  To n   x = cryptos   asm nopnextprint timer-tsleep`
dodicat
Posts: 6148
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Fast random integers

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