uniqid() is slow

So there I was, profiling one of our systems with XHProf and what jumped out as taking up lots of wall-clock execution time? uniqid(). This function, which provides a convenient way to generate unique identifiers, can hold up your PHP execution far more than it should if you’re not careful.

Two things about uniqid() make it a potential performance minefield:

  1. If not called with a second argument of TRUE (the “more entropy” argument), uniqid() sleeps for at least a microsecond.
  2. uniqid() relies on the system function gettimeofday() — and the Linux kernel essentially serializes access to gettimeofday() across all cores.

The Big Sleep

There are two funky things about sleeping from within uniqid(). First, why does PHP need to sleep at all? And how long does that sleep really take?

Without the “more entropy” flag set, uniqid() constructs the unique identifier entirely from the time returned from gettimeofday(): 8 hex digits from the seconds part of the time and 5 hex digits from the microseconds part of the time. So if two calls to uniqid() happen in the same microsecond, then each would return the same identifier. Not so unique!

To avoid this problem, uniqid() ensures that two calls from the same process can’t happen in the same microsecond by making sure uniqid() takes at least a microsecond to execute. The implementation of uniqid() calls usleep(1) to sleep for a microsecond, so the entire uniqid() execution will take at least that long.

In practice, though, that innocent looking usleep(1) can cause a delay of a lot more than just 1 microsecond. The man page for usleep() says “The usleep() function suspends execution of the calling thread for (at least) usec microseconds.”. That “at least” is no joke. On my test system, usleep(1) takes about 63 microseconds to execute. Depending on the resolution of the hardware clocks on your system, your results will vary.

Setting the “more entropy” flag changes this behavior. PHP skips the usleep(1) call and instead disambiguates potential same-microsecond collisions by appending data from php_combined_lcg() to the identifier. This function returns pseudorandom data; two successive calls to it from the same process will return different results.

gettimeofday() serialization

On Linux, a call to gettimeofday() from userspace ultimately ends up running the kernel code at https://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=kernel/time/timekeeping.c#l217 :

do {
  seq = read_seqbegin(&xtime_lock);
  *ts = xtime;
  nsecs = timekeeping_get_ns();

  /* If arch requires, add in gettimeoffset() */
  nsecs += arch_gettimeoffset();
} while (read_seqretry(&xtime_lock, seq));

Those read_seqbegin() and read_seqretry() calls that wrap the call to timekeeping_get_ns() are read locks that force the caller (ultimately PHP calling gettimeofday()) to retry if a write is in progress. And since the time is updated by the kernel so frequently, writes are often in progress.

What this means in practice is that there is a relatively fixed upper bound on the number of gettimeofday() calls that can happen per second across the entire system. If you just have one processor/core, this is not such a big deal, since your single processor is spending its time doing plenty of other things besides calling gettimeofday(). But if you have multiple cores (the system I was profiling was running 8 cores) then the total number of calls across all cores is that same upper bound. So each core has to queue up to get its gettimeofday() calls done.

I wrote a simple program (gettimeofday-forker) which lets you measure how fast gettimeofday() calls are on your system. Download the source code and then compile it with gcc -o gettimeofday-forker gettimeofday-forker.c. Then, initially run it with just one child and an interval of 1000000 microseconds (1 second). On my Linux system, I get this output:

$ ./gettimeofday-forker 1 1000000
[-] All children running
[0] 638146 calls in 1000000 usec = 0.64 calls/usec

With 2, 4, and 8 children, I get:

$ ./gettimeofday-forker 2 1000000
[-] All children running
[1] 366003 calls in 1000000 usec = 0.37 calls/usec
[0] 365881 calls in 1000000 usec = 0.37 calls/usec
$ ./gettimeofday-forker 4 1000000
[-] All children running
[3] 183819 calls in 1000004 usec = 0.18 calls/usec
[2] 181205 calls in 1000001 usec = 0.18 calls/usec
[1] 183655 calls in 1000000 usec = 0.18 calls/usec
[0] 183866 calls in 1000001 usec = 0.18 calls/usec
$ ./gettimeofday-forker 8 1000000
[-] All children running
[7] 91727 calls in 1000002 usec = 0.09 calls/usec
[2] 91928 calls in 1000018 usec = 0.09 calls/usec
[1] 91727 calls in 1000001 usec = 0.09 calls/usec
[6] 90878 calls in 1000441 usec = 0.09 calls/usec
[0] 91600 calls in 1000029 usec = 0.09 calls/usec
[3] 91917 calls in 1000660 usec = 0.09 calls/usec
[4] 94734 calls in 1000001 usec = 0.09 calls/usec
[5] 95827 calls in 1000001 usec = 0.10 calls/usec

The total number of gettimeofday() calls remains about constant, even as the number of child processes increases.

If you experiment with gettimeofday-forker on your own, keep in mind that you should specify an interval large enough to make sure that the time to start up all the processes is very small compared to total runtime. If some children finish before other start, your measurements will be skewed.

Solution

Our dear friend uniqid() has some performance problems. What’s the solution? In our case, we just switched to using mt_rand(). The places we were using uniqid() didn’t really need global-for-all-time unique identifiers, just identifiers that were extremely unlikely to collide with other identifiers being generated around the same time.

If you need stronger guarantees of uniqueness, you have a few options. You could build your own IDs by combining things that are unlikely to collide and cheap to obtain. For example, combine IP address of server, process ID, time at start of request, and a per-request sequence number. (If you’re running PHP in a multithreaded environment, also include thread ID.) For example:

function my_uniqid() {
  static $counter = 0;
  static $pid = -1;
  static $addr = -1;

  if ($pid == -1) { $pid = getmypid(); }
  if ($addr == -1) { $addr = ip2long($_SERVER['SERVER_ADDR']); }

  return $addr . $pid . $_SERVER['REQUEST_TIME'] . ++$counter;
}

This gives you a nice string of digits that are each guaranteed to be generated only once, unless you reset your system clock or duplicate IP addresses.

If that’s not enough, take a look at the PECL uuid extension ), which wraps libuuid. It can generate UUIDs based on things such as Ethernet MAC address. It can be told to generate time-based UUIDs, though, which in turn use gettimeofday() so be careful to avoid that if you don’t want to run into the kinds of problems outlined above.

Author: David Sklar

I'm a Distinguished Engineer at Ning, where I've worked since March 2005. I spend my time bridging boundaries -- between programming languages, platform layers, and development teams. Aside from technical challenges, I enjoy eating, elephants, and entropy.

2 thoughts on “uniqid() is slow”

  1. Hi, Frank. Interesting find! I think that the mapping-to-user-space described still is subject to the locking. For what it’s worth, the system I was testing on had /proc/sys/kernel/vsyscall64 set to 1, using a kernel 2.6.18-194.8.1.el5 on x86_64.

Comments are closed.