array-contains-vs-map-has.js

function createPackedSmiArray(n) {
  const arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(i);
  }
  return arr;
}

function createHoleySmiArray(n) {
  return Array.from({ length: n }, (_, i) => i);
}

function createSmiMap(n) {
  const map = new Map();
  for (let i = 0; i < n; i++) {
    map.set(i, i);
  }
  return map;
}

function createPackedArray(n) {
  const arr = [];
  for (let i = 0; i < n; i++) {
    arr.push({});
  }
  return arr;
}

function createHoleyArray(n) {
  return Array.from({ length: n }, () => ({}));
}

function createMap(n) {
  const map = new Map();
  for (let i = 0; i < n; i++) {
    map.set(i, {});
  }
  return map;
}

function measureArrayIncludes(arr) {
  let n = 1000;
  let timeMs = 0;
  while (timeMs < 20) {
    let bh = true;
    const start = performance.now();
    for (let i = 0; i < n; i++) {
      const NON_EXISTENT_ITEM = Math.random();
      // a = a XOR b; boolean accumulator without short-circuit
      bh = bh !== arr.includes(NON_EXISTENT_ITEM);
    }
    timeMs = performance.now() - start;
    if (Math.random() === 0) {
      console.log(bh);
    }
    n *= 2;
  }
  return (timeMs * 1000000) / n;
}

function measureMapHas(map) {
  let n = 1000;
  let timeMs = 0;
  while (timeMs < 20) {
    let bh = true;
    const start = performance.now();
    for (let i = 0; i < n; i++) {
      const NON_EXISTENT_ITEM = Math.random();
      bh = bh !== map.has(NON_EXISTENT_ITEM);
    }
    timeMs = performance.now() - start;
    if (Math.random() === 0) {
      console.log(bh);
    }
    n *= 2;
  }
  return (timeMs * 1000000) / n;
}

const MAX_SIZE = 100;

console.log("Allocating arrays and maps...");
const arrays = [];
for (let size = 1; size <= MAX_SIZE; size++) {
  arrays.push({
    size,
    packedSmiArray: createPackedSmiArray(size),
    holeySmiArray: createHoleySmiArray(size),
    smiMap: createSmiMap(size),
    packedArray: createPackedArray(size),
    holeyArray: createHoleyArray(size),
    map: createMap(size),
  });
}

console.log("Measuring...");
const results = [];
for (const {
  size,
  packedSmiArray,
  holeySmiArray,
  smiMap,
  packedArray,
  holeyArray,
  map,
} of arrays) {
  const r = {
    size,
    packedSmiArrayTime: measureArrayIncludes(packedSmiArray),
    holeySmiArrayTime: measureArrayIncludes(holeySmiArray),
    smiMapTime: measureMapHas(smiMap),
    packedArrayTime: measureArrayIncludes(packedArray),
    holeyArrayTime: measureArrayIncludes(holeyArray),
    mapTime: measureMapHas(map),
  };

  const averageArrayTime =
    (r.packedSmiArrayTime +
      r.holeySmiArrayTime +
      r.packedArrayTime +
      r.holeyArrayTime) /
    4;
  const averageMapTime = (r.smiMapTime + r.mapTime) / 2;
  const deltaAbs = Math.abs(averageArrayTime - averageMapTime);
  const deltaRel =
    (deltaAbs / Math.min(averageArrayTime, averageMapTime)) * 100;
  const faster = averageArrayTime < averageMapTime ? "array" : "map";
  console.log(
    `size: ${size} - ${faster} is faster by ~${Math.round(
      deltaAbs
    )}ns ~${Math.round(deltaRel)}%`
  );
  results.push(r);
}

console.log("Time in nanoseconds per operation:");
console.table(results);