Last night, I got curious if I could generate an RFC-compliant UUID4 in #JavaScript without external libraries. The obvious solution is:
crypto.randomUUID();
But how fast can I go if security isn't a concern?
I stumbled upon a StackOverflow question on exactly this topic with various approaches.
Here is my proposal, which seems to consistently come out on top.
I first started with a for-loop, then after unrolling, started tweaking.
2× improvement by replacing .toString() and .padStart() with a cached lookup.
Again, I started with a for-loop, unrolled, then tweaked. I tried a recursive function, but it was significantly slower.
Verified against the RFC 9562 test vector.
The current speed is ~2.2M ops. I'm confident I can get this north of 10M ops. I believe the speed limit with 4 calls to Math.random() is upwards of 33M ops.
I think the next "trick" here is memoization. I might need to rethink the approach, but any time/space tradeoff for speed is worth it in this case.
Did some further testing and the speed limit of four Math.random() calls generating 32-bit integers is around 4.5M - 5M ops/s on my ThinkPad.
This code is bumping right up against it. If anyone can make it faster, I'd be very interested to learn the ways of the Jedi.
https://gist.github.com/atoponce/cdba60bc83bc0df23dc1f067eccd5d58
Hold the phone. Processing 2 bytes at a time instead of 1 byte literally doubles the ops/s.
I'm comfortably getting ~8.1M ops/s. Now we're talking!
Gist updated.
@atoponce sorry to break it to you but per spec it's not a valid uuid4 implementation
Implementations SHOULD utilize a cryptographically secure pseudorandom number generator (CSPRNG) to provide values that are both difficult to predict ("unguessable") and have a low likelihood of collision ("unique"). The exception is when a suitable CSPRNG is unavailable in the execution environment.
@atoponce joking aside, you could try to inflate the bytes by running it through a hashing library 😈
I wonder how much slower that would be compared to math.random x4
@nil I agree that if the UUID is needed for anything related to security, privacy, or risk, just call crypto.randomUUID().
I mentioned this in the first post of this thread and also commented as such on that Gist. But not all UUIDs have such requirements. And this was a personal challenge.
I don't want to roll my own userspace RNG though, secure or otherwise, because getting a good seed is extremely challenging. Like, significantly so.
@nil Yeah, no worries. I wasn't getting defensive, or anything (I hope I didn't come across that way).
Really, this was just a personal challenge inspired by this stupid programming meme I saw on Reddit:
https://www.reddit.com/r/ProgrammerHumor/comments/1otspcj/howtoassignidslikeapro/
Aaron Toponce ⚛️
Anil