binarySearch string indexing vs charCodeAt

Benchmark created on

Setup

const haystackSize = 0xfff0;

let haystack = "";
for (let i = 0; i < haystackSize; i++) {
  haystack += String.fromCharCode(i);
}

function byIndex(s, key) {
  let low = 0;
  let high = s.length - 1;
  while (low <= high) {
    const mid = (low + high) >>> 1;
    const midVal = s[mid];
    if (midVal < key) {
      low = mid + 1;
    } else if (midVal > key) {
      high = mid - 1;
    } else {
      return mid; // key found
    }
  }
  return -(low + 1);
}

function byCharCodeAt(s, key) {
  let low = 0;
  let high = s.length - 1;
  while (low <= high) {
    const mid = (low + high) >>> 1;
    const midVal = s.charCodeAt(mid);
    if (midVal < key) {
      low = mid + 1;
    } else if (midVal > key) {
      high = mid - 1;
    } else {
      return mid; // key found
    }
  }
  return -(low + 1);
}

// Returns the index of the first occurrence in the given sorted array,
// or the two's complement of the index of the first element greater than the key.
function byIndexLinear(/** @type {string} */ s,  /** @type {string} */ char) {
  const length = s.length;
  let index = 0;
  while (index < length && s[index] < char) {
    index++;
  }
  if (s[index] === char) {
    return index;
  } else {
   return ~index;
  }
}

function byCharCodeAtLinear(/** @type {string} */ s,  /** @type {number} */ key) {
  const length = s.length;
  let index = 0;
  while (index < length && s.charCodeAt(index) < key) {
    index++;
  }
  if (s.charCodeAt(index) === key) {
    return index;
  } else {
    return ~index;
  }
}

function getRandomInt(max) {
  return Math.floor(Math.random() * max);
}

function getRandomChar(max) {
  const i = getRandomInt(max);
  return String.fromCharCode(i)
}

Test runner

const needle = getRandomChar(0xffff);
byIndex(haystack, needle);

const needle = getRandomInt(0xffff);
byCharCodeAt(haystack, needle);

const needle = getRandomChar(0xffff);
haystack.indexOf(needle);

const needle = getRandomChar(0xffff);
byIndexLinear(haystack, needle);

const needle = getRandomInt(0xffff);
byCharCodeAtLinear(haystack, needle);

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on