A fast equivalent for System.Random

• Download source - 4.06 Kb

Introduction

Here I present a class that can be substituted in place for the the .NET framework's System.Random class to provide some advantages:

1. Based on a simple and fast XOR-shift pseudo random number generator (RNG) specified in the paper: Marsaglia, George. (2003). Xorshift RNGs). This particular implementation of XOR-shift has a period of 2^128-1. See the above paper to see how this can be easily extended if you need a longer period. At the time of writing, I could find no information on the period of System.Random for comparison.
2. Faster than System.Random. Up to 8x faster, depending on which methods are called and which CLR is used (see table below).
3. Direct replacement for System.Random. This class implements all of the methods that System.Random does plus some additional methods for generating random uints and booleans. The like named methods are functionally equivalent to those in System.Random.
4. Allows fast re-initialization with a seed, unlike System.Random which accepts a seed at construction time only, which then executes a relatively expensive initialization routine. This provides a vast speed improvement if you need to reset the pseudo-random number sequence many times, e.g., if you want to re-generate the same sequence many times. An alternative might be to cache random numbers in an array, but that approach is limited by memory capacity and the fact that you may also want a large number of different sequences cached. Each sequence can be represented by a single seed value (int).

Background

I created FastRandom in order to achieve greater speed in a prey capture simulation within another project, SharpNEAT. That simulation requires that the RNG be reset with a given seed 1000s of times per second. FastRandom's Reinitialise() methods, therefore, provide a nice performance boost over System.Random in that case. I then discovered that a number of further performance improvements could be made to the Next*() methods. The first version of FastRandom posted on CodeProject used a multiply-with-carry (MWC) algorithm devised by George Marsaglia. Forum posters pointed out that some seeds generated a sequence of the same number, and whilst investigating the solution, I came across another of Marsaglia's algorithms utilizing an XOR-shift technique that was even faster than MWC. The current version of FastRandom therefore implements XOR-shift and should also provide good random sequences for all seed values (including 0).

The Math

The random number generator (RNG) used generates new numbers using just bitwise XOR and left and right shifts. The method NextUInt provides the simplest example because it returns the generated 32 bit number (uint) without any further manipulation:

public uint NextUInt() 
{
   uint t= (x^(x<<11)); 
   x=y;
   y=z; 
   z=w;
   return (w= (w^(w>>19))^(t^(t>>8)));
}

The state of the RNG is described by the four uint variables x, y, z and w. w represents most recently generated number, and a history of the last four generated numbers is maintained with the inclusion of the x, y and z variables. New numbers are generated by applying various shifts and XORs to x, which represents the number generated four calls ago. Storing and using the history of the last four numbers in this manner results in an RNG with a longer period, here the period is 2^128-1. The period can be shortened or lengthened by adjusting the amount of history variables stored. For more information on this, see the paper referred to above.

All of the other Next*() methods are variations of this technique, taking the 32 bits generated and manipulating them into double, int, bytes, etc.

Reinitialise() methods

The Reinitialise methods allow the caller to reset FastRandom with a single integer seed value and thus generate the same set of random numbers over again. This can sometimes be useful, e.g., in simulations where you might want to recreate the same scenario exactly as before. Note that System.Random provides no such method for re-initializing (re-seeding) the class once it is constructed; the only option is to construct a new instance and pass the seed in to the constructor, which then executes code to build an array of seed data. By allowing re-initialization and avoiding the need to build a seed data array, FastRandom provides a significant performance improvement where reseeding is required.

Other Performance Improvements (in comparison to System.Random)

• Avoid use of floating point arithmetic where possible. This applies to Next() and NextBytes(byte[]).
• Where floating point arithmetic is used, ensure that casts are performed from int to double, and not from uint to double. In tests, casting from uint took twice as long as casting from int. This speed-up applies to NextDouble(), Next(int) and Next(int,int).
• Don't declare methods as virtual. The virtual method table generates some overhead even in released, optimized code where the methods haven't actually been overridden. System.Random's methods are declared as virtual and therefore generate this overhead. There may be sound reasons for this within the .NET framework, but if you just want a fast RNG today, then we can omit the virtual keyword in our declarations.
• In the NextBytes method, we generate 32 bits at a time and fill the byte array in 4 byte chunks.

Performance Comparison Table

For prior readers of this article please note that this is an updated version of the table that takes into account improvements made to FastRandom.cs made since the article was first posted and also to the .NET runtime engine between .NET 1.1 and .NET 2.0.

Other notes:

• Both FastRandom and System.Random run faster on the .NET 2.0 CLR than on .NET 1.1. However, System.Random does benefit more than FastRandom and so the performance gap between the two classes is narrower in .NET 2.0.
• One exception to the above point is Next(int,int) with a long range between the two integer parameters, on the .Net 1.1 CLR FastRandom's version actually ran slower, however on .NET 2.0 this result is now reversed as can be seen in the table below.

The following performance figures were obtained using released, optimized code executing on an Intel Core 2 Duo E660 overclocked to 3.11Ghz. This is a dual core chip, however these performance figures are for a single core only:

	System.Random (millions calls/sec)	FastRandom (millions calls/sec)	Speed increase
Next()	103.252	220.750	2.14x
Next(int)	51.826	142.247	2.14x
Next(int,int)	34.506	87.680	2.54x
Next(int,int) <long range>*	16.182	30.261	1.87x
NextDouble()	87.680	185.528	2.12x
NextBytes() 1024 byte array in tests	0.105	0.927	8.83x
NextUInt()	n/a	261.437	n/a
NextInt()	n/a	256.081	n/a
NextBool()	n/a	312.500	n/a

* - An alternative execution path occurs when the range between the lower and upper limits will not fit within an int. This results in a different performance figure.

Note the last three methods which are extra methods not present on System.Random. NextUint() is provided because uint is the underlying data type behind FastRandom and so is very fast to generate. NextInt() returns an int (Int32<?CODE>) but unlike Next() the range is between 0 and int.MaxValue instead of between 0 and int.MaxValue-1. This subtle difference allows an optimization to be made (elimination of an 'if' statement). NextBool() is implemented by generating 32 bits (uint) and buffering them for future calls, hence the high speed.

Conclusion

System.Random is actually very fast and achieves its speed mostly by only using simple and fast arithmetic operations such as shift and add. However, the whole class is based around a central Sample() method that returns a double between 0.0 and 1.0, and thus there is some unnecessary floating point arithmetic used to generate integer values. FastRandom utilizes a completely different algorithm for generating random numbers that is inherently slightly faster, and in FastRandom we provide a further boost by avoiding floating point arithmetic wherever possible and implementing some further refinements. Finally, FastRandom also allows for fast re-seeding which allows repeat random number sequences to be re-generated very quickly.