Run results for: Trie vs native map

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/137.0.0.0 Safari/537.36

Browser: Chrome 137

Operating system: Mac OS X 10.15.7

Device Platform: Desktop

Date tested: 10 months ago

Test name	Executions per second
Trie	7.2 Ops/sec
Native Object	5782.0 Ops/sec

Script Preparation code:

var Trie = class Trie {
  constructor() {
    this.root = { children: {} };
    this.size = 0;
  }

  add(key, value) {
    let node = this.root;
    for (let i = 0; i < key.length; ++i) {
      if (!node.children[key[i]]) node.children[key[i]] = { children: {} };
      node = node.children[key[i]];
    }
    node.value = value;
    this.size += 1;
    return value;
  }

  get(key) {
    let node = this.root;
    for (let i = 0; i < key.length; ++i) {
      if (!node.children[key[i]]) return undefined;
      node = node.children[key[i]];
    }
    return node.value;
  }

  remove(key) {
    this._remove(this.root, key, 0);
  }

  _remove(node, key, index) {
    if (!node) return undefined;

    if (index === key.length) {
      delete node.value;
      this.size -= 1;
    } else {
      const c = key[index];
      const child = this._remove(node.children[c], key, index + 1);
      if (child) node.children[c] = child;
      else delete node.children[c];
    }

    if (Object.keys(node.children).length === 0 && node.value === undefined)
      return undefined;
    return node;
  }
}

function pseudoRandom() {
  pseudoRandom.value = (pseudoRandom.value ** 2 + 3 * pseudoRandom.value + 1) % 26
  return pseudoRandom.value
}

pseudoRandom.value = 0

function createRandomString(length) {
  let s = ''
  for (let i = 0; i < length; ++i) {
    s += String.fromCharCode('a'.charCodeAt(0) + pseudoRandom())
  }
  return s
}

const N = 10000
const L = 1000
const strs = new Array(N)
for (let n = 0; n < N; ++n) strs[n] = createRandomString(L)

var ObjectWrapper = class ObjectWrapper {
  constructor() { this.data = {} }
  
  add(key, value) {
    this.data[key] = value
  }
  
  remove(key, value) {
    delete this.data[key]
  }
  
  get(key) {
    return this.data[key]
  }
}

function test(ds) {
  for (const s of strs) {
    ds.add(s, s)
  }
  for (const s of strs) {
    ds.get(s)
  }
  for (const s of strs) {
    ds.remove(s)
  }
}

Tests:

Trie
test(new Trie())
Native Object
test(new ObjectWrapper())

Run results for: Trie vs native map

I know this is really useless comparison

Trie

Native Object