Performance of Random UUID generation with Java 7 or Java 6

Question

I have a web based Java application that generates random UUIDs for session information. One of our testers is claiming up to 350ms to generate UUIDs based upon his own profiling, but I have not yet been able to replicate his results. He points to this article http://www.cowtowncoder.com/blog/archives/2010/10/entry_429.html to help back up his results. I wanted to see if anyone else has ran into this limitation with Java's built-in UUID generation capability in either Java 6 or Java 7 applications.

Answer 1

Here is a test run in beta 127.

Keep in mind that this test is unrealistic, beyond any worst-case scenario I can imagine. My goal was to quiet those who bad-mouth use of UUIDs without the facts to back up their criticism.

Scenario:

• A tight loop of a million calls to java.util.UUID.randomUUID()
  • One test with just that alone. (no contention)
  • One test with contention, where 2 other threads are in a tight loop making ten million calls.
• Java 8 beta 127
  • java version "1.8.0"
  • Java(TM) SE Runtime Environment (build 1.8.0-b127)
  • Java HotSpot(TM) 64-Bit Server VM (build 25.0-b69, mixed mode)
• Run from Netbeans 7.4 IDE
• Executing inside a virtual machine
  • Parallels 9 virtual machine
  • Mountain Lion
  • 3 virtual cores
  • 4 gigs memory
• Mac mini (late 2012)
  • Mavericks
  • Intel i7 quad-core with Hyperthreading (8 apparent cores)
  • 16 gigs memory

Without Contention

Running one loop in one thread, so no contention over the synchronized methods/classes.

// Warm the random generator.
java.util.UUID uuid;
uuid = java.util.UUID.randomUUID();

long stop = 0;
long start = System.nanoTime();

int loops = 1000000;  // One million.
for ( int i = 0; i < loops; i++ ) {
    uuid = java.util.UUID.randomUUID();
}

stop = System.nanoTime();

long elapsed = ( stop - start );

System.out.println( "UUIDs: " + loops );
System.out.println( "Nanos: " + elapsed );
System.out.println( "Nanos per uuid: " + ( elapsed / loops ) + " ( micros per: " + ( elapsed / loops / 1000 ) + " )" );

Results

About 2 microseconds per UUID.

With Contention

Similar to above, but while doing a loop of a million calls, we have two other threads running where each makes ten million calls.

// Warm the random generator.
java.util.UUID uuid;
uuid = java.util.UUID.randomUUID();

int pass = 10_000_000 ;  // Ten million.
MyThread t1 = new MyThread( pass );
MyThread t2 = new MyThread( pass );


t1.start();
t2.start();
t3.start();

long stop = 0;
long start = System.nanoTime();

int loops = 1_000_000 ;  // One million.
for ( int i = 0; i < loops; i++ ) {
    uuid = java.util.UUID.randomUUID();
}

stop = System.nanoTime();

long elapsed = ( stop - start );

System.out.println( "UUIDs: " + loops );
System.out.println( "Nanos: " + elapsed );
System.out.println( "Nanos per uuid: " + ( elapsed / loops ) + " ( micros per: " + ( elapsed / loops / 1000 ) + " )" );

And the class defining each thread…

class MyThread extends Thread {

    private int loops;

    public MyThread( int loops ) {
        this.loops = loops;
    }

    @Override
    public void run() {
        java.util.UUID uuid;
        for ( int i = 0; i < this.loops; i++ ) {
            uuid = java.util.UUID.randomUUID();
        }

    }
}

Results

About 20 microseconds per UUID.

Runs were 14, 20, 20, 23, and 24 microseconds per UUID (not in that order). So under extreme contention was only about 10 times worse, with 20 microseconds being acceptable in any real-world usage I've known.

Answer 2

I tested it

    for (;;) {
        long t0 = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            UUID.randomUUID();
        }
        System.out.println(System.currentTimeMillis() - t0);
    }

on my PC it is ~1100 ms, which is pretty slow. UUID.randomUUID() uses SecureRandom internally, to make it faster we can use regular java.util.Random

    Random r = new Random();
    for (;;) {
            ..
            new UUID(r.nextLong(), r.nextLong());

it's ~80 ms

Answer 3

The random form of UUID typically uses a source of "cryptography strength" random numbers.

(If it didn't then so-called random UUIDs would be predictable, and the probability that a given UUID is reissued could increase to worrying levels. As another answer suggests, you could provide a fast (but weak) PRNG to the UUID constructor. But that would be a bad idea.)

Typical crypto-strength random number generators use a source of entropy that is external to the application. It might be a hardware random number generator, but more commonly it is accumulated "randomness" that is harvested by the operating system in normal operation. The problem is that sources of entropy have a rate limit. If you exceed that rate over a period of time, you can drain the source. What happens next is system dependent, but on some systems the syscall to read entropy will stall ... until more is available.

I expect that is what is happening on your client's system. (It is not uncommon on virtual machines ...)

One hacky work-around (for Linux systems) is to install the rngd daemon and configure it to "top up" the entropy pool using a good pseudo-random number generator. A security expert would point that:

• this will affect your UUID generator's randomness, and
• the entropy pool is used for other security-related things, so topping it up from a dubious source is weakening security for many things on your system.

I'm not sure how safe this hack would be in practice.

Here's another Q&A on the topic of slow random number generation:

• How to deal with a slow SecureRandom generator?