Create GUID / UUID in JavaScript?

Question

I'm trying to create globally-unique identifiers in JavaScript. I'm not sure what routines are available on all browsers, how "random" and seeded the built-in random number generator is, etc..

The GUID / UUID should be at least 32 characters and should stay in the ASCII range to avoid trouble when passing them around.

Answer 1

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 4 bits of the result and wasting the rest), you may start to wonder about performance. Indeed, joelpt even decided to toss out 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 12X, the accepted answer by over 9X, and the fast-non-compliant answer by 2-3X. And I'm still rfc4122 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:

'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);
});

So it replaces x with any random hex digit, y with random data (except forcing the top 2 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;
}

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
}

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
}

The next optimization is another classic. Since we're only handling 4-bits of output in each loop iteration, let's cut the number of loops in half and process 8-bits 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
}

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 re-assigning, 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];
}

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.

Answer 2

Simple JavaScript module as a combination of best answers in this thread.

var crypto = window.crypto || window.msCrypto || null; // IE11 fix

var Guid = Guid || (function() {

  var EMPTY = '00000000-0000-0000-0000-000000000000';

  var _padLeft = function(paddingString, width, replacementChar) {
    return paddingString.length >= width ? paddingString : _padLeft(replacementChar + paddingString, width, replacementChar || ' ');
  };

  var _s4 = function(number) {
    var hexadecimalResult = number.toString(16);
    return _padLeft(hexadecimalResult, 4, '0');
  };

  var _cryptoGuid = function() {
    var buffer = new window.Uint16Array(8);
    window.crypto.getRandomValues(buffer);
    return [_s4(buffer[0]) + _s4(buffer[1]), _s4(buffer[2]), _s4(buffer[3]), _s4(buffer[4]), _s4(buffer[5]) + _s4(buffer[6]) + _s4(buffer[7])].join('-');
  };

  var _guid = function() {
    var currentDateMilliseconds = new Date().getTime();
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(currentChar) {
      var randomChar = (currentDateMilliseconds + Math.random() * 16) % 16 | 0;
      currentDateMilliseconds = Math.floor(currentDateMilliseconds / 16);
      return (currentChar === 'x' ? randomChar : (randomChar & 0x7 | 0x8)).toString(16);
    });
  };

  var create = function() {
    var hasCrypto = crypto != 'undefined' && crypto !== null,
      hasRandomValues = typeof(window.crypto.getRandomValues) != 'undefined';
    return (hasCrypto && hasRandomValues) ? _cryptoGuid() : _guid();
  };

  return {
    newGuid: create,
    empty: EMPTY
  };
})();

// DEMO: Create and show GUID
console.log(Guid.newGuid());

Usage:

Guid.newGuid()

"c6c2d12f-d76b-5739-e551-07e6de5b0807"

Guid.empty

"00000000-0000-0000-0000-000000000000"

Answer 3

The better way:

function(
  a,b                // placeholders
){
  for(               // loop :)
      b=a='';        // b - result , a - numeric variable
      a++<36;        // 
      b+=a*51&52  // if "a" is not 9 or 14 or 19 or 24
                  ?  //  return a random number or 4
         (
           a^15      // if "a" is not 15
              ?      // genetate a random number from 0 to 15
           8^Math.random()*
           (a^20?16:4)  // unless "a" is 20, in which case a random number from 8 to 11
              :
           4            //  otherwise 4
           ).toString(16)
                  :
         '-'            //  in other cases (if "a" is 9,14,19,24) insert "-"
      );
  return b
 }

Minimized:

function(a,b){for(b=a='';a++<36;b+=a*51&52?(a^15?8^Math.random()*(a^20?16:4):4).toString(16):'-');return b}

Answer 4

For those wanting an rfc4122 version 4 compliant solution with speed considerations (few calls to Math.random()):

function UUID() {
    var nbr, randStr = "";
    do {
        randStr += (nbr = Math.random()).toString(16).substr(2);
    } while (randStr.length < 30);
    return [
        randStr.substr(0, 8), "-",
        randStr.substr(8, 4), "-4",
        randStr.substr(12, 3), "-",
        ((nbr*4|0)+8).toString(16), // [89ab]
        randStr.substr(15, 3), "-",
        randStr.substr(18, 12)
        ].join("");
}

The above function should have a decent balance between speed and randomness.

Answer 5

You can use node-uuid (https://github.com/kelektiv/node-uuid)

Simple, fast generation of RFC4122 UUIDS.

Features:

• Generate RFC4122 version 1 or version 4 UUIDs
• Runs in node.js and browsers.
• Cryptographically strong random # generation on supporting platforms.
• Small footprint (Want something smaller? Check this out!)

---

Install Using NPM:

npm install uuid

---

Or Using uuid via browser:

Download Raw File (uuid v1): https://raw.githubusercontent.com/kelektiv/node-uuid/master/v1.js Download Raw File (uuid v4): https://raw.githubusercontent.com/kelektiv/node-uuid/master/v4.js

---

Want even smaller? Check this out: https://gist.github.com/jed/982883

---

Usage:

// Generate a v1 UUID (time-based)
const uuidV1 = require('uuid/v1');
uuidV1(); // -> '6c84fb90-12c4-11e1-840d-7b25c5ee775a'

// Generate a v4 UUID (random)
const uuidV4 = require('uuid/v4');
uuidV4(); // -> '110ec58a-a0f2-4ac4-8393-c866d813b8d1'

// Generate a v5 UUID (namespace)
const uuidV5 = require('uuid/v5');

// ... using predefined DNS namespace (for domain names)
uuidV5('hello.example.com', v5.DNS)); // -> 'fdda765f-fc57-5604-a269-52a7df8164ec'

// ... using predefined URL namespace (for, well, URLs)
uuidV5('http://example.com/hello', v5.URL); // -> '3bbcee75-cecc-5b56-8031-b6641c1ed1f1'

// ... using a custom namespace
const MY_NAMESPACE = '(previously generated unique uuid string)';
uuidV5('hello', MY_NAMESPACE); // -> '90123e1c-7512-523e-bb28-76fab9f2f73d'

---

ES6:

import uuid from 'uuid/v4';
const id = uuid();

Answer 6

Weird that no one has mentioned this yet but for completeness, there's a plethora of guid generators on npm I'm willing to bet most of them work in browser too.