XORShift vs Random performance in Java

Java’s Random class uses a linear congruential generator, which has mediocre quality at best,  and then to add insult to injury, wrapped more crap around it (configurable number of bits per call, useless thread safety) to make it slow to boot!

I had a need for medium quality 64 bit random numbers, but speed was of the essence!  Enter http://en.wikipedia.org/wiki/Xorshift, a class of clever random number generators that use just  a few shift and xor operations, which are very fast on processors.

While there are many possible Xorshift generators, the simplest one I found for 64 bit numbers was here.  It’s incredibly short!

public long randomLong() {
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  return x;
}

This is a full period generator that will generate all bit patterns except for 0.  The period is 2^64-1.  One must also avoid using 0 as a seed.  Now all we have to do is wrap this up in a class and benchmark it vs Java’s Random class:

class XORShift64 {
  long x;
  public XORShift64(long seed) {
    x = seed==0 ? 0xdeadbeef : seed;
  }
  public long randomLong() {
    x ^= (x << 21); 
    x ^= (x >>> 35);
    x ^= (x << 4);
    return x;
  }
}

And the results on a 64 bit JVM:

Java’s Random:  45.7 million longs per second

XORShift64: 320.6 million longs per second, or 7 times faster!

Advertisements
This entry was posted in java, performance and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s