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

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?

Answer 3

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 4

The number of threads has a huge impact on the performance of the generation of UUIDs. This can be explained by looking at the implementation of SecureRandom#nextBytes(byte[] which generates the random numbers for UUID.randomUUID():

synchronized public void nextBytes(byte[] bytes) {
    secureRandomSpi.engineNextBytes(bytes);
}

nextBytes is synchronized which leads to significant performance loss when accessed by different threads.

Answer 5

Use Version 1 Instead of 4

How about using Version 1 type of UUID?

Version 1 is based on MAC address and current time ("space and time"). Much less likely to have collisions than Version 4.

Version 4 is based on entirely being generated from random numbers using a cryptographically strong random generator.

The Oracle JVM does not provide a Version 1 generator, apparently because of security and privacy concerns. The JVM does not provide access to the MAC address of host machine.

JUG Library

There is at least one third-party library available that doe provide Version 1 UUIDs, as well as other versions: JUG – Java UUID Generator. They say features introduced in Java 6 let them get access to the MAC address.

Test Results: 20x

Read a discussion of performance with test results using Java UUID Generator version 3 in the 2010 article, More on Java UUID Generator (JUG), a word on performance. Tatu Saloranta tested various kinds of UUIDs on his MacBook.

Upshot: MAC+Time version is 20 times faster that random version.

Time-based variant (Ethernet address plus timestamp) is much faster -- almost 20 times as fast as Random-based default variant -- generating about 5 million UUIDs per second.

Answer 6

A junit test run under jdk 1.7.0_40:

package org.corba.util;

import org.junit.Test;
import org.springframework.util.StopWatch;

import java.util.UUID;

/**
 * Test of performance of Java's UUID generation
 * @author Corba Da Geek
 * Date: 1/6/14
 * Time: 3:48 PM
 */
public class TestRandomUUID {
    private static final int ITERATIONS = 1000000;

    @Test
    public void testRandomUUID() throws Exception {
        // Set up data
        StopWatch stopWatch = new StopWatch();
        stopWatch.start();

        // Run test
        for (int i = 0; i < ITERATIONS; i++)
            UUID.randomUUID();

        // Check results
        stopWatch.stop();
        final long totalTimeMillis = stopWatch.getTotalTimeMillis();
        System.out.println("Number of milliseconds: " + totalTimeMillis + " for " + ITERATIONS + " iterations.");
        System.out.println(String.format("Average time per iteration: %.7f ms", (float)totalTimeMillis/ITERATIONS));
    }
}

And the results on my i5 laptop were:

-------------------------------------------------------
 T E S T S
-------------------------------------------------------
Running org.corba.util.TestRandomUUID
Number of milliseconds: 677 for 1000000 iterations.
Average time per iteration: 0.0006770 ms
Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.746 sec

Results :

Tests run: 1, Failures: 0, Errors: 0, Skipped: 0

0.0006770 ms per invocation.

Answer 7

I did the same test as the others and my results are more like 300 NANOseconds per UUID generation. Results are on a i7 quad-core WIN7 64 PC. I tried with a jdk1.7.0_67 and with a jdk1.8.0_40 64 bits JVMs.

I'm kind of perplex my results are so different than all others... But 1 ms for generating a random number seemed a LOT !

public static void main(String[] args) throws Exception {
    long start = System.nanoTime();
    int loops = 1000000; // One million.

    long foo = 0;

    for (int i = 0; i < loops; i++) {
        UUID uuid = java.util.UUID.randomUUID();

        //this is just to make sure there isn't some kind of optimization
        //that would prevent the actual generation
        foo += (uuid.getLeastSignificantBits()
                + uuid.getMostSignificantBits());
    }

    long stop = System.nanoTime();

    long elapsed = (stop - start);

    System.out.println(String.format("UUIDs              : %,d", loops));
    System.out.println(String.format("Total time (ns)    : %,d", elapsed));
    System.out.println(String.format("Time per UUID (ns) : %,d", (elapsed / loops)));

    System.out.println();
    System.out.println(foo);
}

The output :

UUIDs              : 1 000 000
Total time (ns)    : 320 715 288
Time per UUID (ns) : 320

5372630452959404665