feat: Improve performance of Uint8Array Hex functions

[johnzhou721]

Refs #1503 for the source of inspiration to do this. This PR significantly improves the performance of Uint8array hex functions.

Benchmarks / Console logs on IE11 for from hex (including final performance of from-hex functions in addition to all the moments used for the decisions of what do put)

// Define the functions for the two methods: parseInt and manual hex-to-decimal with bitwise operations

// parseInt method
function parseIntMethod(hex) {
  return parseInt(hex, 16);
}

// hexCharToDecimal method with bitwise operations
function hexCharToDecimal(hex) {
  var firstDigitValue = (hex.charCodeAt(0) >= 48 && hex.charCodeAt(0) <= 57)  // '0' to '9'
    ? hex.charCodeAt(0) - 48 
    : (hex.charCodeAt(0) >= 97 && hex.charCodeAt(0) <= 102)  // 'a' to 'f'
    ? hex.charCodeAt(0) - 87 
    : hex.charCodeAt(0) - 55;  // 'A' to 'F'
    
  var secondDigitValue = (hex.charCodeAt(1) >= 48 && hex.charCodeAt(1) <= 57)  // '0' to '9'
    ? hex.charCodeAt(1) - 48 
    : (hex.charCodeAt(1) >= 97 && hex.charCodeAt(1) <= 102)  // 'a' to 'f'
    ? hex.charCodeAt(1) - 87 
    : hex.charCodeAt(1) - 55;  // 'A' to 'F'
  
  return (firstDigitValue << 4) | secondDigitValue;  // Bitwise operation to combine digits
}

// Function to run the benchmark
function runBenchmark() {
  var testCases = ["aa", "Af", "Bf", "0f", "bA"];
  var iterations = 10000;
  
  // Test with parseInt
  console.time("parseInt");
  for (var i = 0; i < iterations; i++) {
    for (var j = 0; j < testCases.length; j++) {
      parseIntMethod(testCases[j]);
    }
  }
  console.timeEnd("parseInt");

  // Test with hexCharToDecimal (Bitwise)
  console.time("hexCharToDecimal");
  for (var i = 0; i < iterations; i++) {
    for (var j = 0; j < testCases.length; j++) {
      hexCharToDecimal(testCases[j]);
    }
  }
  console.timeEnd("hexCharToDecimal");
}

// Run the benchmark
runBenchmark();
undefined
parseInt: 27.6ms
hexCharToDecimal: 73.5ms

// Test string
var testString = "13933920394"; // Example string to be tested

// Method 1: Split into 2-character pieces and run regex on each
function method1(str) {
  // Split string into 2-character chunks
  var chunks = str.match(/.{1,2}/g); // .match is supported in IE11
  
  // Ensure every chunk passes the regex test
  return chunks.every(function(chunk) {
    return !/[^\da-f]/i.test(chunk); // Run the regex on each chunk
  });
}

// Method 2: Run regex on the entire string
function method2(str) {
  return !/[^\da-f]/i.test(str); // Run the regex on the entire string
}

// Benchmark function
function runBenchmark() {
  var iterations = 10000; // Number of iterations for the test
  console.time("Method 1");
  for (var i = 0; i < iterations; i++) {
    method1(testString);
  }
  console.timeEnd("Method 1");

  console.time("Method 2");
  for (var i = 0; i < iterations; i++) {
    method2(testString);
  }
  console.timeEnd("Method 2");
}

// Run the benchmark
runBenchmark();
undefined
Method 1: 43.2ms
Method 2: 4.9ms


function uncurryThis(fn) {
  return function() {
    return Function.prototype.call.apply(fn, arguments);
  };
}

var NOT_HEX = /[^\da-f]/i;
var exec = uncurryThis(NOT_HEX.exec);
var stringMatch = uncurryThis(''.match);

exp = function (string, into) {
  var stringLength = string.length;
  if (stringLength & 1) throw new SyntaxError('String should be an even number of characters');
  if (exec(NOT_HEX, string)) throw new SyntaxError('String should only contain hex characters');
  var maxLength = into && into.length < stringLength >> 1 ? into.length : stringLength >> 1;
  var bytes = into || new Uint8Array(maxLength);
  var segments = stringMatch(string, /.{2}/g)
  var written = 0;
  while (written < maxLength) {
    bytes[written++] = parseInt(segments[written-1], 16);
  }
  return { bytes: bytes, read: written * 2 };
};

var testString = "deadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabe";
var iterations = 10000;

console.time("hexToBytes benchmark");
for (var i = 0; i < iterations; i++) {
  exp(testString);
}
console.timeEnd("hexToBytes benchmark");
undefined
hexToBytes benchmark: 290.2ms

function uncurryThis(fn) {
  return function() {
    return Function.prototype.call.apply(fn, arguments);
  };
}

var NOT_HEX = /[^\da-f]/i;
var exec = uncurryThis(NOT_HEX.exec);
var stringSlice = uncurryThis(''.slice);

exp = function (string, into) {
  var stringLength = string.length;
  if (stringLength % 2 !== 0) throw new SyntaxError('String should be an even number of characters');
  var maxLength = into ? min(into.length, stringLength / 2) : stringLength / 2;
  var bytes = into || new Uint8Array(maxLength);
  var read = 0;
  var written = 0;
  while (written < maxLength) {
    var hexits = stringSlice(string, read, read += 2);
    if (exec(NOT_HEX, hexits)) throw new SyntaxError('String should only contain hex characters');
    bytes[written++] = parseInt(hexits, 16);
  }
  return { bytes: bytes, read: read };
};

var testString = "deadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabe";
var iterations = 10000;

console.time("hexToBytes benchmark");
for (var i = 0; i < iterations; i++) {
  exp(testString);
}
console.timeEnd("hexToBytes benchmark");
undefined
hexToBytes benchmark: 3,495.5ms
document.documentMode
11

[johnzhou721]

My older benchmarks used buggy implementations. The newer benchmarks comparing the 3 approaches is posted below:

IE11 benchmarks for from-hex

Variant 0

(Original polyfill)

function uncurryThis(fn) {
  return function() {
    return Function.prototype.call.apply(fn, arguments);
  };
}


var min = Math.min;
var NOT_HEX = /[^\da-f]/i;
var exec = uncurryThis(NOT_HEX.exec);
var stringSlice = uncurryThis(''.slice);

exp = function (string, into) {
  var stringLength = string.length;
  if (stringLength % 2 !== 0) throw new SyntaxError('String should be an even number of characters');
  var maxLength = into ? min(into.length, stringLength / 2) : stringLength / 2;
  var bytes = into || new Uint8Array(maxLength);
  var read = 0;
  var written = 0;
  while (written < maxLength) {
    var hexits = stringSlice(string, read, read += 2);
    if (exec(NOT_HEX, hexits)) throw new SyntaxError('String should only contain hex characters');
    bytes[written++] = parseInt(hexits, 16);
  }
  return { bytes: bytes, read: read };
};


var testString = "deadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabe";
var iterations = 10000;

console.time("hexToBytes benchmark");
for (var i = 0; i < iterations; i++) {
  exp(testString);
}
console.timeEnd("hexToBytes benchmark");

Results:

undefined
hexToBytes benchmark: 2,327.2ms

Variant 1

(Using exec with each segment)

function uncurryThis(fn) {
  return function() {
    return Function.prototype.call.apply(fn, arguments);
  };
}


var min = Math.min;
var NOT_HEX = /[^\da-f]/i;
var exec = uncurryThis(NOT_HEX.exec);
var stringSlice = uncurryThis(''.slice);

exp = function (string, into) {
  var stringLength = string.length;
  if (stringLength & 1) throw new SyntaxError('String should be an even number of characters');
  var maxLength = (into && into.length < (stringLength >> 1) ? into.length : (stringLength >> 1));
  var bytes = into || new Uint8Array(maxLength);
  var segments = stringMatch(string, /.{2}/g);
  for (var written = 0; written < maxLength; written++) {
    if (exec(NOT_HEX, segments[written])) {throw new SyntaxError("String!!!")};
    var result = parseInt(segments[written], 16);
    bytes[written] = result;
  }
  return { bytes: bytes, read: written << 1 };
};


var testString = "deadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabe";
var iterations = 10000;

console.time("hexToBytes benchmark");
for (var i = 0; i < iterations; i++) {
  exp(testString);
}
console.timeEnd("hexToBytes benchmark");

Result:

undefined
hexToBytes benchmark: 1,109.4ms

Variant 2

(used)

var $Number = Number;
var $isNaN = $Number.isNaN;
var stringMatch = uncurryThis(''.match);

exp = function (string, into) {
  var stringLength = string.length;
  if (stringLength & 1) throw new SyntaxError('String should be an even number of characters');
  var maxLength = (into && into.length < (stringLength >> 1) ? into.length : (stringLength >> 1));
  var bytes = into || new Uint8Array(maxLength);
  var segments = stringMatch(string, /.{2}/g);
  for (var written = 0; written < maxLength; written++) {
    var result = $Number("0x" + segments[written]);
    if ($isNaN(result) && result.trim() === result) throw new SyntaxError('String should only contain hex characters');
    bytes[written] = result;
  }
  return { bytes: bytes, read: written << 1 };
};
var testString = "deadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabedeadbeefcafebabe";
var iterations = 10000;

console.time("hexToBytes benchmark");
for (var i = 0; i < iterations; i++) {
  exp(testString);
}
console.timeEnd("hexToBytes benchmark");

Result:

undefined
hexToBytes benchmark: 678.2ms

[johnzhou721]

@zloirock This is ready for you take a look at. I'll leave the base64 aspects to another PR.

[johnzhou721]

@zloirock It's been a few days -- if you've got a moment, could you please take a look at this? Thanks.

[zloirock]

Use .exec if it's possible, since, unlike .match, it does not have significant side effects. I think here it's OK. But I'm not sure that it's good for performance.

[johnzhou721]

It is very good for performance -- with one of the benchmarks for IE11 in my original post (the last few are wrong implementations...) it speeds up a few times than slicing every time.

[johnzhou721]

@zloirock Done with requested changes.

[johnzhou721]

@zloirock It's been a few days, when you've got time after you're done fixing various bugs, can you take a look at this again? Thanks.

[zloirock]

Since Number constructor is polyfilled before this module, it definitely can't be fast.

[zloirock]

If you really wanna make it fast, you could just iterate by chars and check char codes.

[johnzhou721]

@zloirock tried that, actually benchmarked slower.

[zloirock]

@johnzhou721 it can't be slower. In any engine. It can be bad tests.

[zloirock]

Thanks.

[johnzhou721]

@zloirock Thanks for the reviews, and yes you're right about the bad testing... i got myself confused here with all the different parsing options I was testing.

Also sorry for the repeated pings... I wanted to make sure nothing was missed. I see you pushing a lot to the main branch but being less responsive on issues/prs -- were you just really busy with the long list of bugs you have at hand, and only check periodically? If so, I'll respect that.