tree vs array finders populate

Benchmark created on November 21, 2025

Setup

const valueSymbol = Symbol('value')

class TreeFinder {
  constructor() {
    this.map = new Map();
  }

  set(path, value) {
    let current = this.map
    for (let i = 0; i < path.length; i++) {
      let next = current.get(path[i]);
      if (next === undefined) {
        next = new Map();
        current.set(path[i], next);
      }

      current = next;
    }

    current.set(valueSymbol, value);
  }

  get(path) {
    let current = this.map
    for (let i = 0; i < path.length; i++) {
      let next = current.get(path[i]);
      if (next === undefined) {
        return undefined;
      }

      current = next;
    }

    return current.get(valueSymbol);
  }
}

class ArrayFinder {
  constructor() {
    this.arr = [];
  }

  set(path, value) {
    for (let item of this.arr) {
      if (arraysEqual(item.path, path)) {
        item.value = value;
        return;
      }
    }

    this.arr.push({path, value});
  }

  get(path) {
    for (let item of this.arr) {
      if (arraysEqual(item.path, path)) {
        return item.value;
      }
    }

    return undefined;
  }
}

function arraysEqual(a, b) {
  if (a === b) {
    return true;
  }
  if (a.length !== b.length) {
    return false;
  }
  const len = a.length;
  for (let i = 0; i < len; i++) {
    if (a[i] !== b[i]) {
      return false;
    }
  }
  return true;
}

const N = 100;

function populate(finder) {
  for (let i = 0; i < N; i++) {
    finder.set([i + 0, i + 1], i);
  }

  for (let i = 0; i < N; i++) {
    finder.set([2 * i + 0, 2 * i + 1, 2 * i + 2], i);
  }

  for (let i = 0; i < N; i++) {
    finder.set([3 * i + 0, 3 * i + 1, 3 * i + 2, 3 * i + 3], i);
  }
}

function test(finder) {
  for (let i = 0; i < N; i++) {
    if (finder.get([i + 0, i + 1]) !== i) { throw new Error(); }
  }

  for (let i = 0; i < N; i++) {
    if(finder.get([2 * i + 0, 2 * i + 1, 2 * i + 2]) !== i) { throw new Error() }
  }

  for (let i = 0; i < N; i++) {
    if(finder.get([3 * i + 0, 3 * i + 1, 3 * i + 2, 3 * i + 3]) !== i) { throw new Error() }
  }
}

const t = new TreeFinder();
const a = new ArrayFinder();

populate(t);
populate(a);

Test runner

test(t);

test(a);

Revisions

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

• Revision 1: published on November 21, 2025