broofa's answer is pretty slick, indeed - impressively clever, really... RFC4122 compliant, somewhat readable, and compact. Awesome!

But if you're looking at that regular expression, those many `replace()`

callbacks, `toString()`

's and `Math.random()`

function calls (where he's only using four bits of the result and wasting the rest), you may start to wonder about performance. Indeed, joelpt even decided to toss out an RFC for generic GUID speed with `generateQuickGUID`

.

**But, can we get speed ***and* RFC compliance? I say, YES! Can we maintain readability? Well... Not really, but it's easy if you follow along.

But first, my results, compared to broofa, `guid`

(the accepted answer), and the non-rfc-compliant `generateQuickGuid`

:

` Desktop Android broofa: 1617ms 12869ms e1: 636ms 5778ms e2: 606ms 4754ms e3: 364ms 3003ms e4: 329ms 2015ms e5: 147ms 1156ms e6: 146ms 1035ms e7: 105ms 726ms guid: 962ms 10762ms generateQuickGuid: 292ms 2961ms - Note: 500k iterations, results will vary by browser/CPU. `

So by my 6th iteration of optimizations, I beat the most popular answer by over **12 times**, the accepted answer by over **9 times**, and the fast-non-compliant answer by **2-3 times**. And I'm still RFC 4122 compliant.

Interested in how? I've put the full source on http://jsfiddle.net/jcward/7hyaC/3/ and on http://jsperf.com/uuid-generator-opt/4

For an explanation, let's start with broofa's code:

`function broofa() { return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) { var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8); return v.toString(16); }); } console.log(broofa())`

So it replaces `x`

with any random hexadecimal digit, `y`

with random data (except forcing the top two bits to `10`

per the RFC spec), and the regex doesn't match the `-`

or `4`

characters, so he doesn't have to deal with them. Very, very slick.

The first thing to know is that function calls are expensive, as are regular expressions (though he only uses 1, it has 32 callbacks, one for each match, and in each of the 32 callbacks it calls Math.random() and v.toString(16)).

The first step toward performance is to eliminate the RegEx and its callback functions and use a simple loop instead. This means we have to deal with the `-`

and `4`

characters whereas broofa did not. Also, note that we can use String Array indexing to keep his slick String template architecture:

`function e1() { var u='',i=0; while(i++<36) { var c='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'[i-1],r=Math.random()*16|0,v=c=='x'?r:(r&0x3|0x8); u+=(c=='-'||c=='4')?c:v.toString(16) } return u; } console.log(e1())`

Basically, the same inner logic, except we check for `-`

or `4`

, and using a while loop (instead of `replace()`

callbacks) gets us an almost 3X improvement!

The next step is a small one on the desktop but makes a decent difference on mobile. Let's make fewer Math.random() calls and utilize all those random bits instead of throwing 87% of them away with a random buffer that gets shifted out each iteration. Let's also move that template definition out of the loop, just in case it helps:

`function e2() { var u='',m='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx',i=0,rb=Math.random()*0xffffffff|0; while(i++<36) { var c=m[i-1],r=rb&0xf,v=c=='x'?r:(r&0x3|0x8); u+=(c=='-'||c=='4')?c:v.toString(16);rb=i%8==0?Math.random()*0xffffffff|0:rb>>4 } return u } console.log(e2())`

This saves us 10-30% depending on platform. Not bad. But the next big step gets rid of the toString function calls altogether with an optimization classic - the look-up table. A simple 16-element lookup table will perform the job of toString(16) in much less time:

`function e3() { var h='0123456789abcdef'; var k='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'; /* same as e4() below */ } function e4() { var h=['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f']; var k=['x','x','x','x','x','x','x','x','-','x','x','x','x','-','4','x','x','x','-','y','x','x','x','-','x','x','x','x','x','x','x','x','x','x','x','x']; var u='',i=0,rb=Math.random()*0xffffffff|0; while(i++<36) { var c=k[i-1],r=rb&0xf,v=c=='x'?r:(r&0x3|0x8); u+=(c=='-'||c=='4')?c:h[v];rb=i%8==0?Math.random()*0xffffffff|0:rb>>4 } return u } console.log(e4())`

The next optimization is another classic. Since we're only handling four bits of output in each loop iteration, let's cut the number of loops in half and process eight bits in each iteration. This is tricky since we still have to handle the RFC compliant bit positions, but it's not too hard. We then have to make a larger lookup table (16x16, or 256) to store 0x00 - 0xFF, and we build it only once, outside the e5() function.

`var lut = []; for (var i=0; i<256; i++) { lut[i] = (i<16?'0':'')+(i).toString(16); } function e5() { var k=['x','x','x','x','-','x','x','-','4','x','-','y','x','-','x','x','x','x','x','x']; var u='',i=0,rb=Math.random()*0xffffffff|0; while(i++<20) { var c=k[i-1],r=rb&0xff,v=c=='x'?r:(c=='y'?(r&0x3f|0x80):(r&0xf|0x40)); u+=(c=='-')?c:lut[v];rb=i%4==0?Math.random()*0xffffffff|0:rb>>8 } return u } console.log(e5())`

I tried an e6() that processes 16-bits at a time, still using the 256-element LUT, and it showed the diminishing returns of optimization. Though it had fewer iterations, the inner logic was complicated by the increased processing, and it performed the same on desktop, and only ~10% faster on mobile.

The final optimization technique to apply - unroll the loop. Since we're looping a fixed number of times, we can technically write this all out by hand. I tried this once with a single random variable, `r`

, that I kept reassigning, and performance tanked. But with four variables assigned random data up front, then using the lookup table, and applying the proper RFC bits, this version smokes them all:

`var lut = []; for (var i=0; i<256; i++) { lut[i] = (i<16?'0':'')+(i).toString(16); } function e7() { var d0 = Math.random()*0xffffffff|0; var d1 = Math.random()*0xffffffff|0; var d2 = Math.random()*0xffffffff|0; var d3 = Math.random()*0xffffffff|0; return lut[d0&0xff]+lut[d0>>8&0xff]+lut[d0>>16&0xff]+lut[d0>>24&0xff]+'-'+ lut[d1&0xff]+lut[d1>>8&0xff]+'-'+lut[d1>>16&0x0f|0x40]+lut[d1>>24&0xff]+'-'+ lut[d2&0x3f|0x80]+lut[d2>>8&0xff]+'-'+lut[d2>>16&0xff]+lut[d2>>24&0xff]+ lut[d3&0xff]+lut[d3>>8&0xff]+lut[d3>>16&0xff]+lut[d3>>24&0xff]; } console.log(e7())`

Modualized: http://jcward.com/UUID.js - `UUID.generate()`

The funny thing is, generating 16 bytes of random data is the easy part. The whole trick is expressing it in *string* format with RFC compliance, and it's most tightly accomplished with 16 bytes of random data, an unrolled loop and lookup table.

I hope my logic is correct -- it's very easy to make a mistake in this kind of tedious bit work. But the outputs look good to me. I hope you enjoyed this mad ride through code optimization!

**Be advised:** my primary goal was to show and teach potential optimization strategies. Other answers cover important topics such as collisions and truly random numbers, which are important for generating good UUIDs.