A faster random

Although ActionScript has its own random number function, Math.random(), like most library calls it is not especially fast. But it is easy to replace, to provide a significant speed up, as well as make it easier to do other optimisations.


The basic idea is very simple: instead of calling Math.random()while the game is running call it a number of times at startup to populate a list, then at runtime pull values out of that list. This would not work in all games: it might produce predictable or repetitive outcomes in some cases. But in games where random numbers are used for effect or to provide some variability in a number of ways it is often indistinguishable from Math.random() (which is not truly random anyway).

To replace calls to Math.random() with accessing the list, incrementing the index into the Vector each time this is done, looping back to the start (a Vector is used instead of an Array – this is one case where it is faster). E.g. replace
                fRand = Math.random();

with

                fRand = aRand[iRandIndex++];

                if (iRandIndex >= kRandNum) iRandIndex = 0;

where kRandNum is the size of the list. This is many times faster, three to four times faster in a simple loop. This is not the fastest way to do it though: there are a couple of optimisations for a further speedup.

First if the list size is a power of two the second line which sets the index back to zero at the end can be replaced with bitfield and. The code then becomes

                fRand = aRand[iRandIndex++ & kRandMask];

Where kRandMax is the one less than the list size which must be a power of 2. The speedup from this is barely measurable though. Clearly conditional statements involving if aren't that expensive in ActionScript.

Another optimisation is possible if random numbers are needed a few times, for example when initialising statistics for an enemy or an encounter. As long as the number is limited the check in case the end of the list is reached can be deferred. 

                fRand1 = aRand[iRandIndex++];

                fRand2 = aRand[iRandIndex++];

                fRand3 = aRand[iRandIndex++];

                fRand4 = aRand[iRandIndex++];

                if (iRandIndex >= kRandNum){

                    iRandIndex -= kRandNum;

                }

To do this the Vector needs to be larger, by at least as much as the maximun number of access to the array done before the index is checked.

The code to benchmark this is here: http://wonderfl.net/c/vL0N. I won't embed it as it simply prints the results, reproduced below. These are, in milliseconds:

Library call to Math.random(): 199ms

Pull values from an Vector: 66ms

Replace if with a bitwise operation: 63ms

Only reset the index every four values: 49ms

The biggest optimisation is replacing calls to Math.random() with accessing a Vector. The other optimisations are far less beneficial. It's also worth noting that the actual speed up is small, and on its own is not going to measurably improve the speed of most games. Most of the optimisations here though have other uses, such as to optimise calls to other library functions. If optimisations like this are carried out throughout code it can  make a noticeable difference.

Doing it this way has other benefits too. It can help debugging: if a game crashes when a particular random number is input it can be useful to have it visible in the debugger. If random numbers are to be transformed someway then this can be done when the list is initially calculated. If for example if random percentages are wanted the random numbers can be multiplied by 100 before as they are stored in the list. Or int could be used instead of Number, avoiding an expensive type conversion at runtime.