Add your own alternative version
Stats
204.8K views 2.8K downloads 61 bookmarked
Posted
31 Dec 2004
Licenced
|
Comments and Discussions
|
|
I don't seem to be getting random values. Setting a seed and doing myRandom.Next(1000) gives me the same value after I reinitialize myRandom with a new seed.
Just taking the values from myRandom.Next() I can see that the values are not distributed over much range (and bigger seeds get bigger values of Next()) . I'm wondering if there is some other initialization step that I missed or if in fact this does not actually produce random values?
|
|
|
|
|
Testing against Random is like shooting fish in a barrel. Random is thread safe and has to update an atomic variable at each call. Fair benchmarking should be against an instance of ThreadLocalRandom, which is not thread safe.
Moreover, you can improve the speed by using 64-bit shifts, which are as fast as 32-bit shifts on modern CPUs. You can find some speed comparison here:
http://dsiutils.di.unimi.it/docs/it/unimi/dsi/util/XorShift64StarRandom.html
As you can see, beating ThreadLocalRandom is entirely another matter. The generator used in ThreadLocalRandom (congruential) is horrible, but it is very fast.
|
|
|
|
|
What are you talking about? .net does not have a ThreadLocalRandom class and the Random class is by no means thread safe msdn says the following:
The System.Random class and thread safety
Instead of instantiating individual Random objects, we recommend that you create a single Random instance to generate all the random numbers needed by your app. However, Random objects are not thread safe. If your app calls Random methods from multiple threads, you must use a synchronization object to ensure that only one thread can access the random number generator at a time. If you don't ensure that the Random object is accessed in a thread-safe way, calls to methods that return random numbers return 0.
|
|
|
|
|
Shouldn't you also add a line to Reinitialise():
bitMask=1;
To make sure you are starting from the same place every time (if you are specifying seeds)?
|
|
|
|
|
Hi, yes you are correct. For now if you need to use this class I would recommend obtaining a more up-to-date version with this and other fixes, available at:
http://sharpneat.svn.sourceforge.net/svnroot/sharpneat/trunk/SharpNeatV2/src/SharpNeatLib/Utility/FastRandom.cs
Thanks for the feedback,
Colin.
|
|
|
|
|
I saw a framerate improvement in my XNA game when I changed NextBytes to fill an array of uints (that I allocate in the constructor) and then copy this array to the output byte array using Buffer.BlockCopy.
I don't have specific performance metrics, but, intuitively, it makes sense that this should work.
public void NextBytes(byte[] buffer)
{
if (buffer.Length / 4 > mScratch.Length)
{
return;
}
uint x = this.x, y = this.y, z = this.z, w = this.w;
int i = (buffer.Length >> 2) - 1;
uint t;
while ( i >= 0 )
{
t = (x ^ (x << 11));
x = y; y = z; z = w;
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
mScratch[i] = w;
i--;
}
Buffer.BlockCopy(mScratch, 0, buffer, 0, buffer.Length);
this.x = x; this.y = y; this.z = z; this.w = w;
}
|
|
|
|
|
One of greate problems of the original Random of System is the non existence of NextFloat (min,max) function.
How is possible implement a good function for this ?
Mauricio Cunha
www.mcunha98.cjb.net
mcunha98@terra.com.br
|
|
|
|
|
I wrote a simple benchmark in c# and to me it seems like System.Random is the fastest.
In 3 seconds FastRandom could do 4559590 iterations,
compared to System.Random with 4855556 iterations.
The numbers can variate a bit but in general the picture is the same. System.Random is fastest.
Note that I'm using .Net 3.5 libraries.
Benchmark code below.
using System;
public static class benchmark {
public static void RunAll(){
RunFastRandom();
RunRandom();
}
public static void RunRandom(){
Random randomNumber = new Random();
int num = -1;
int iterations = 0;
TimeSpan maxTime = new TimeSpan(0, 0, 3);
DateTime timer = DateTime.Now;
while(maxTime > (DateTime.Now - timer)){
num = randomNumber.Next();
iterations++;
}
Console.WriteLine("Iterations in " + maxTime + " seconds width System.Random: " + iterations);
}
public static void RunFastRandom(){
FastRandom randomNumber = new FastRandom();
int num = -1;
int iterations = 0;
TimeSpan maxTime = new TimeSpan(0, 0, 3);
DateTime timer = DateTime.Now;
while(maxTime > (DateTime.Now - timer)){
num = randomNumber.Next();
iterations++;
}
Console.WriteLine("Iterations in " + maxTime + " seconds width FastRandom: " + iterations);
}
}
|
|
|
|
|
Hi, thanks for the feedback.
There are a couple of points I'd like to make to anyone taking this benchmark as definitive. Firstly you get very different result if you run benchmarks with the debugger attached, also running released(optimised) code can make a substantial difference with this type of code. Running released code without the debugger I got:
FastRandom - 13,729,267 iterations
System.Random - 13,082,906
With the debugegr attached they both came out slower and System.Random won. However, your benchmark code calls DateTime.Now once on each loop and it turns out that the majority of CPU time is spent inside that property. If I iterate a fixed number of loops and time how long they take I get:
For 10^9 loops:
FastRandom - 3,140ms
System.Random - 12,500ms
Which equates to iterations per/sec of:
FastRandom - 318M
System.Random - 80M
The speed variations observed in your benchmark code are essentially showing us how the two random number classes are interacting with DateTime.Now and surrounding code, e.g. what code is left is CPU caches and registers etc. It's not an invalid test but I felt I need to qualify it here to any passing readers.
Out of interest I looked at System.Random in .Net Reflector and it looks liek the same code as in .Net 1.0 and 1.1.
Regards,
Colin.
|
|
|
|
|
I don't care for speed. I'll use your pseudo-random number generator for a platform independent project, because I need to generate a sequence of numbers for a given seed again and again. The implementations of System.Random in .NET and mono return different sequences for the same seed, so my application would not really do the same on every platform. Thanks for this nice alternative!
_____________________________________________________
This statement is false.
|
|
|
|
|
Hi Colin,
I've recently developed a managed library for random number generators and distributions and published it here[^] on CodeProject. I'd known your article (greate work by the way) for some time and decided to include a XorShift RNG. As you stated in a previous post that you're happy for your code to be reused, I took your FastRandom class as basis for my implementation which of course includes your summary and a reference to your article. When doing this, I've found a minor "error" and a performance improvement.
1.) The comment for the Next method states that "Values returned are over the range 0 to int.MaxValue-1". But int.MaxValue (0x7FFFFFFF) can also occur (tested it) as your code generates a uint with full range and then does a bitwise AND with 0x7FFFFFFF. So int.MaxValue is returned when the unsigned integer 0xFFFFFFFF is generated.
If added a simple if-else that returns the generated integer if its unequal int.MaxValue or generates a new one otherwise.
2.) In the NextBytes method it's possible to leave out the bitwise AND of w and e.g. 0x000000FF before casting to byte as the cast only involves the rightmost 8 bits and doesn't care for the rest.
buffer[i++] = (byte)( w&0x000000FF); --> buffer[i++] = (byte)w;
buffer[i++] = (byte)((w&0x0000FF00) >> 8); --> buffer[i++] = (byte)(w >> 8);
Best regards, Stefan
"Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook www.troschuetz.de
|
|
|
|
|
Hi Stefan,
Thanks for the feedback and apologies for not responding sooner. Yeh sure no problem with re-using the code in your library. The librray looks very useful by the way. In the past when I've wanted to generate number sequences with different distributions I've had to resort to hacking/porting parts of randlib from C, which in turn was ported from Fortran I think and quite frankly that code is a mess!
With regard to point (1), I think the better solution would be simply to AND with 0x7FFFFFFE instead of 0x7FFFFFFF. My initial thought was that this would generate an uneven distribution of generated numbers, but of course each bit is random independently of all other bits so that masking out some bits still leaves an even distribution.
On point (2), thanks for this, I tried it and it is indeed functionally equivalent and also about 6% faster in the test I did.
I'm about to update the article and the file with these two changes, plus an update to the performance table as I noticed the figures are all out by a factor of 1000! Also the performance of System.Random and FastRandom under .Net 2.0 is very different than under .Net 1.1. FastRandom still wins though
Regards
Colin
|
|
|
|
|
Hello again!
colgreen wrote: apologies for not responding sooner
No problem I'm very patient
colgreen wrote: I think the better solution would be simply to AND with 0x7FFFFFFE instead of 0x7FFFFFFF
I thought about this one too, but it has a major drawback: the rightmost bit will always be zero and therefor only even numbers will be generated. Although they may be evenly distributed, I think this isn't very practical and favor using the if-else-approach.
Best Regards, Stefan
"Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook www.troschuetz.de
|
|
|
|
|
i needed a fast source for random bytes for filling files ans drives with random bytes. therefore i tried to optimize your code a bit. i measured the performance after each step multiple times with realtime priority. i noticed that reversing the loop (from length - 1 to 0) increased throughput considerably. setting i to uint improved perf by 1%. i unrolled the loop 4 times to allow for out-of-order-execution and to reduce the impact of the loop code. faster code was generated, when i used uintptr[i] instead of *uintptr++.
public unsafe void GetBytes(byte* buffer, int length)
{
uint x = this.x, y = this.y, z = this.z, w = this.w;
uint t;
uint* uintptr = (uint*)buffer;
length /= 4;
for (uint i = (uint)(length - 4); ; i -= 4)
{
t = x ^ (x << 11);
x = y; y = z; z = w;
w ^= t ^ (w >> 19) ^ (t >> 8);
uintptr[i] = w;
t = x ^ (x << 11);
x = y; y = z; z = w;
w ^= t ^ (w >> 19) ^ (t >> 8);
uintptr[i + 1] = w;
t = x ^ (x << 11);
x = y; y = z; z = w;
w ^= t ^ (w >> 19) ^ (t >> 8);
uintptr[i + 2] = w;
t = x ^ (x << 11);
x = y; y = z; z = w;
w ^= t ^ (w >> 19) ^ (t >> 8);
uintptr[i + 3] = w;
if (i == 0) { break; }
}
this.x = x; this.y = y; this.z = z; this.w = w;
}
|
|
|
|
|
We are developing an open source cross-platform product on Mono and DotNET. We are in need of a portable Random Number generator like the one published here (http://www.codeproject.com/csharp/fastrandom.asp). What legal licenses, if any, are placed on this code?
jnorman
|
|
|
|
|
Hi jnorman,
I suppose the answer is that there isn't one (a license), apart from whatever I agreed to when I posted the article. However, I'm happy for the code to be reused in whatever context so if you want I can send a modified version of the source with extra license blurb and get them to update the zip file on here.
Right now I'm thinking of switching over my other project (sharpneat) to a license less strict and more legally digestable than the L(GPL) - Something like the MIT or Apache licenses.
http://www.opensource.org/licenses/mit-license.php
I take it that would be ok?
Colin.
|
|
|
|
|
(I tried emailing you in addition to this comment, sorry if you get this twice)
I still don't see a license mentioned. Any chance you could choose one?
Great work and thanks!
Dan
|
|
|
|
|
Reinitializing with the same seed should produce the same random sequence. Try this:
FastRandom r = new FastRandom();
r.Reinitialise(0);
int r1 = r.Next();
int r2 = r.Next();
r.Reinitialise(0);
int r3 = r.Next();
r1 and r3 should be the same number. I think you need to add this to the Reinitialise function:
y = 842502087;
z = 3579807591;
w = 273326509;
Thanks for the great article,
Jeremy
|
|
|
|
|
Ahh yes, silly mistake. Thanks for the feedback, I've submitted an updated zip file with this fix.
Colin
|
|
|
|
|
Nice article!
I wrote an additional routine, NextBytesUnsafe , that does NextBytes but with pointer arithmetic, and copies the w, x, y and z fields to local variables to speed it up even more.
Since w is already a random uint 4 bytes long, the routine copies the whole thing, and increments the pointer 4 bytes at a time.
The two downsides are that it needs /unsafe, and that the input buffer size must be divisble by 4.
Here's the code:
<br />
public unsafe void NextBytesUnsafe(byte[] buffer)<br />
{<br />
if(buffer.Length % 4 != 0)<br />
throw new ArgumentException("Buffer length must be divisible by 4", "buffer");<br />
<br />
uint x = this.x, y = this.y, z = this.z, w = this.w;<br />
uint t;<br />
<br />
fixed(byte* pByte0 = buffer)<br />
{<br />
uint* pDWord = (uint*)pByte0;<br />
for(int i = 0, len = buffer.Length/4; i < len; i++)<br />
{<br />
t=(x^(x<<11));<br />
x=y; y=z; z=w;<br />
*pDWord++ = w = (w^(w>>19))^(t^(t>>8));<br />
}<br />
}<br />
<br />
this.x = x; this.y = y; this.z = z; this.w = w;<br />
}<br />
On my Pentium 4 2.4ghz HT machine, the original implementation takes 3.078 seconds to generate 1024 random bytes 1,000,000 times, while the unsafe implementation takes 1.406 seconds -- about 2 times faster.
|
|
|
|
|
Hi,
Brilliant! Thanks for the feedback and the extra NextBytes method, I hadn't considered this approach at all so I learned something today
Just to confirm for the benefit of others, I looked over the new method and it checks out and does indeed run over 2x faster than the safe method. A few additional points then:
1) When i revisited the performance tests I noticed that the unchanged safe methods ran noticably slower with the /unsafe compilation flag on. Worth noting.
2) The technique of copying the class variables into local variables does indeed have significant benefit because the variables are heavily used within the main loop. However the same technique can also be applied to the safe version of NextBytes, doing so increases speed from about 389 calls/sec to 450 calls/sec on my AMD Athlon 2400+ (with /unsafe switched off). Still a lot slower than the unsafe method but of benefit if you can't or dont want to use the unsafe method.
3) The divide by 4 in the new method can be achieved ever so slightly more efficiently with a shift-to-right by 2 bits operation, e.g.
for(int i = 0, len = buffer.Length>>2; i < len; i++)
but this is only executed once per call to the method so it doesn't have any noticeable effect on performance. Even so, I always like to squeeze out as many clock cycles as possible from a simple re-usable routine like this - Yes I know that optimisation is the root of all evil
Thanks again,
Colin.
|
|
|
|
|
colgreen wrote:
Still a lot slower than the unsafe method but of benefit if you can't or dont want to use the unsafe method.
Sorry my bad, didn't mean to confuse the local copies idea with using /unsafe
By the way, I'm writing a realtime cloud generator right now, and your article really saved the day for me.
Thanks again!
|
|
|
|
|
I know that there probably isn't, but is there an equivalent for this method (NextBytesUnsafe) for VB? If not, I'll just use C#. (And yes, I know VB doesn't have equivalents for pointers and that is why there probably isn't a VB equivalent for the code)
|
|
|
|
|
Nope, that's one of the very few things C# can do that VB can't.
You could compile the class in C# and add a reference to it from VB though... not sure how that'd affect performance but maybe it's worth a try.
|
|
|
|
|
To address a problem with seeding I have now re-coded FastRandom to use a completely different algorithm, namely an xor-shift method. Although there was a much simpler fix for the problem, I found this new algorithm a little faster so I decided to switch.
The algorithm itself is explained in a paper linked from the top of the article.
|
|
|
|
|
|
General News Suggestion Question Bug Answer Joke Praise Rant Admin
Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.
|
|