perf: remove superfluous call to toLowerCase

[LinusU]

From the discussion and experimentation in #676 I found that we are running toLowerCase on every generated id instead of once when constructing byteToHex.

In fact, toString(16) seems to already return lower case, but I cannot be sure that this is guaranteed by the spec after reading it, and since it doesn't do any harm I kept it:

https://tc39.es/ecma262/multipage/ecmascript-data-types-and-values.html#sec-numeric-types-number-tostring

npm run test:benchmark is returning some strange results though:

Name	Before change	After change
uuid.stringify()	x 4,494,323 ops/sec ±0.14%	x 3,529,389 ops/sec ±0.13%
uuid.parse()	x 4,021,155 ops/sec ±0.05%	x 4,015,847 ops/sec ±0.06%
uuid.v1()	x 4,612,946 ops/sec ±0.18%	x 6,409,517 ops/sec ±0.12%
uuid.v1() fill existing array	x 10,069,463 ops/sec ±0.13%	x 10,022,300 ops/sec ±0.13%
uuid.v4()	x 22,898,259 ops/sec ±1.66%	x 23,060,288 ops/sec ±1.67%
uuid.v4() fill existing array	x 8,156,566 ops/sec ±0.23%	x 8,225,266 ops/sec ±0.20%
uuid.v3()	x 560,691 ops/sec ±0.28%	x 600,164 ops/sec ±0.32%
uuid.v5()	x 665,117 ops/sec ±0.43%	x 639,418 ops/sec ±0.31%

uuid.v1 is much faster, but uuid.stringify is slower? 🤔

If I benchmark this with hyperfine (see #676 for details) then this unsafeStringify is 1.66 times faster than the one currently in main.

The only thing I can think would cause stringify to be slower, would be if V8 sets some kind of "is ascii" or similar flag on the string when running toLowerCase, and then uses this flag to chose another regex engine 🤷‍♂️

Indeed, adding toLowerCase to the validate function (before passing it to an case-insensitive regex 😅) brings the speed of the uuid.stringify() up to x 4,465,165 ops/sec ±0.12% (98 runs sampled) again.

Hyperfine seems to support this:

lc-1.js

const byteToHex = [];

for (let i = 0; i < 256; ++i) {
  byteToHex.push((i + 0x100).toString(16).slice(1));
}

function unsafeStringify(arr, offset = 0) {
  // Note: Be careful editing this code!  It's been tuned for performance
  // and works in ways you may not expect. See https://github.com/uuidjs/uuid/pull/434
  return (
    byteToHex[arr[offset + 0]] +
    byteToHex[arr[offset + 1]] +
    byteToHex[arr[offset + 2]] +
    byteToHex[arr[offset + 3]] +
    '-' +
    byteToHex[arr[offset + 4]] +
    byteToHex[arr[offset + 5]] +
    '-' +
    byteToHex[arr[offset + 6]] +
    byteToHex[arr[offset + 7]] +
    '-' +
    byteToHex[arr[offset + 8]] +
    byteToHex[arr[offset + 9]] +
    '-' +
    byteToHex[arr[offset + 10]] +
    byteToHex[arr[offset + 11]] +
    byteToHex[arr[offset + 12]] +
    byteToHex[arr[offset + 13]] +
    byteToHex[arr[offset + 14]] +
    byteToHex[arr[offset + 15]]
  );
}

const arr = [195, 134, 237, 159, 29, 92, 23, 173, 126, 71, 146, 180, 222, 111, 192, 148];
const regex =
  /^(?:[0-9a-f]{8}-[0-9a-f]{4}-[1-5][0-9a-f]{3}-[89ab][0-9a-f]{3}-[0-9a-f]{12}|00000000-0000-0000-0000-000000000000)$/i;

const string = unsafeStringify(arr);

for (let i = 0; i < 40_000_000; i++) {
  regex.test(string);
}

lc-2.js (diff)

--- lc-1.js	2023-01-11 18:55:02
+++ lc-2.js	2023-01-11 18:52:40
@@ -35,7 +35,7 @@
 const regex =
   /^(?:[0-9a-f]{8}-[0-9a-f]{4}-[1-5][0-9a-f]{3}-[89ab][0-9a-f]{3}-[0-9a-f]{12}|00000000-0000-0000-0000-000000000000)$/i;
 
-const string = unsafeStringify(arr);
+const string = unsafeStringify(arr).toLowerCase();
 
 for (let i = 0; i < 40_000_000; i++) {
   regex.test(string);

$ hyperfine 'node lc-1a.js' 'node lc-2a.js'
Benchmark 1: node lc-1a.js
  Time (mean ± σ):      2.714 s ±  0.002 s    [User: 2.703 s, System: 0.009 s]
  Range (min … max):    2.712 s …  2.716 s    10 runs
 
Benchmark 2: node lc-2a.js
  Time (mean ± σ):      2.718 s ±  0.006 s    [User: 2.706 s, System: 0.010 s]
  Range (min … max):    2.712 s …  2.727 s    10 runs
 
Summary
  'node lc-1a.js' ran
    1.00 ± 0.00 times faster than 'node lc-2a.js'

---

I've created a test case that shows the current code we have, the changes proposed in this PR, and a third option that adds .toLowerCase only in the "safe" stringify function.

https://jsbench.me/u4lcs1i0oy/1

In Safari, the solution here faster. But on V8, probably due to the quirk mentioned above, calling toLowerCase before passing to Regex#test is faster, so both 1 & 3 is faster.

I'm not really sure what is best to optimize for, but this PR should improve performance on every runtime for the v1, v3, v4, and v5 functions. If we on top of that want to insert a weird optimization (calling toLowerCase before Regex#test) just to optimize on V8, that's fine with me.

---

Even without the performance benefits, I also think that this code change makes sense. Why lowercase the result every time, instead of building it from parts with the correct case from the beginning?

[broofa]

In fact, toString(16) seems to already return lower case, but I cannot be sure that this is guaranteed by the spec after reading it

I think this verbiage is the bit you're looking for:

The digits used in the representation of a number using radix r are taken from the first r code units of "0123456789abcdefghijklmnopqrstuvwxyz" in order.

I.e. toString() will always return lowercase strings, so we can remove the toLowerCase() call(s) altogether where bytesToHex is concerned.

[Edit: heh ... looks like you ninja'd me and already did so]

[LinusU]

Okay, toString(16) is guaranteed to return a lower case string! It's in the ECMAScript specification.

ref: https://stackoverflow.com/a/19751935/148072

So I've updated the PR to remove the toLowerCase call.

[LinusU]

@broofa hehe, we commented at the same time. Yes, we can skip the call! 🙌

[LinusU]

Name	Before	After
uuid.stringify()	x 4,012,874 ops/sec ±0.14%	x 3,500,266 ops/sec ±0.17%
uuid.parse()	x 3,773,568 ops/sec ±0.07%	x 3,964,479 ops/sec ±0.13%
uuid.v1()	x 4,003,997 ops/sec ±0.16%	x 6,224,810 ops/sec ±0.18%
uuid.v1() fill existing array	x 9,990,061 ops/sec ±0.16%	x 10,021,774 ops/sec ±0.14%
uuid.v4()	x 22,870,980 ops/sec ±1.75%	x 22,648,164 ops/sec ±1.65%
uuid.v4() fill existing array	x 8,012,358 ops/sec ±0.20%	x 8,100,356 ops/sec ±0.14%
uuid.v3()	x 553,683 ops/sec ±0.27%	x 598,661 ops/sec ±0.27%
uuid.v5()	x 651,688 ops/sec ±0.41%	x 662,520 ops/sec ±0.44%

This change makes the bundle smaller, and the uuid generation faster. On V8 it makes stringify slower. I think that this is enough to make this a good change that we want to land.

Potentially we want to add .toLowerCase() to stringify as a V8-specific optimization, if we feel that it is worth it.

[broofa]

Me calculating how many cpu-decades have been wasted in toLowerCase() here...

[LinusU]

Haha, yeah, it's a bit funny that it has been in there all the time 😂

[Cadienvan]

That's awesome!

I'm happy my tests proven something closer that made this library better!

[broofa]

[kkntl]

Apparently the .toLowerCase() was introduced in #434 not to actually convert to lower case, but as a workaround for a memory issue.

Can you confirm that this issue was considered and is not relevant anymore ?

// Note: Be careful editing this code!  It's been tuned for performance
// and works in ways you may not expect. See https://github.com/uuidjs/uuid/pull/434
// `toLowerCase` used to fix memory issue caused by concatenation: https://bugs.chromium.org/p/v8/issues/detail?id=3175#c4

(I see this statement proven true: #267 (comment):

... using tolowercase though might be a little more confusing to anyone else looking at the code.

)

[broofa]

@kkntl Good question!

@LinusU , did you consider the memory consumption issue when putting up this PR? It looks like that toLowerCase() call was actually there to avoid retaining references to the individual substrings that are concatenated together. (A point I'd completely forgotten about!)

Testing this, it does still appear to be an issue.
[Edit: Re-ran tests with node v20.6.0, better screenshots.]

It's worth noting that if this is a regression - as it seems to be - the impact is mitigated somewhat by #600, which short-circuits this project's use of v4() in preference for crypto.randomUUID(). Not that this justifies not fixing this. 🤷

---

Running this script both with and without the toLowerCase() call ...

const {v4} = require('uuid');

// Using empty `options` to prevent `uuid` from short-circuiting to
// `crypto.randomUUID()`, which isn't what we want to test
const opts = {}; // empty `options` to

// Call v4() once to prime entropy cache
v4(opts);

// Create memory snapshot here, prior to creating 10K IDs
//
const ids = [];
for (let i = 0; i < 10000; i++) ids.push(v4(opts));

// Create memory snapshot here, after creating 10K IDs, and
// use the "comparison" view in Chrome debugger to inspect
// the difference.

console.log('done');

With code on main branch (no toLowerCase()) (adds ~475 bytes/uuid):

Adding toLowerCase() call back into stringify() (adds 56 bytes/uuid):

[ctavan]

It sounds like we should bring this back and improve the comment?