How to iterate a Javascript Map or Object without allocating?

(V8 developer here.)

As the question you've linked to points out, JavaScript engines (at least V8) do optimize away the temporary objects that the spec text for the iteration protocol talks about; though the full answer (as so often) is "it depends".

One effect is that optimizing things away is something that optimizing compilers do, and those don't kick in right away (because more often than not, that would be a waste of effort). So if you only run a function a few times, you'll see its unoptimized version allocate short-lived garbage. But that'll change soon (specifics depend on the engine), as soon as the function is deemed "hot" and gets optimized.

Another issue you might be running into is that iterating over a Map directly (as in: let map = new Map(); ...; for (let e of map) {...} is specified to return e as an array [key, value] every time. This array is not optimized away; it has to be allocated on every iteration. But if you're only interested in processing the values anyway, you can avoid it being created by iterating over just the values: for (let v of map.values()) {...} does not allocate any short-lived objects. The same is true for iterating over map.keys().

If you need both key and value, you could combine an iteration over the keys with a map lookup: for (let key of map.keys()) { let value = map.get(key); ...}, however this is quite a bit slower than iterating over the values. If your objects implement interface Entry as in your answer, i.e. they have a property carrying their key, then you can use that instead: for (let value of map.values()) { let key = value.id; ...}.

All that said: if the SparseSet solution works for you, then of course that's cool too. You can even make it a little more efficient: if you change add to add(item: T) { let key = item.id; ...} and update delete to include this.sparse.delete(key), then the set itself can guarantee that its internal data is always consistent, and then contains can be as simple as return this.sparse.get(key) !== undefined;.

I assume the work-around for this is to instead use a sorted array instead of a map, right? The only issue with that is that insertion and deletion is O(log n)

Insertion and deletion on sorted arrays are O(n), because you may have to shift the entire contents around. (Looking up an element by its sorted key is what takes O(log n) if you use binary search for that.) However, using unsorted arrays can be faster than one might expect intuitively, as long as they remain small-ish (a couple dozen entries or so). Something like:

class UnsortedArray<T extends Entry> {
  contents: Array<T> = [];

  add(item: T) { contents.push(T); }  // optional: check for duplicates first
  private find(key: number) {
    for (let i = 0; i < contents.length; i++) {
      if (contents[i].id == key) return i;
    }
    return -1;
  }
  size() { return contents.length; }
  get_by_index(index: number) { return contents[index]; }
  get_by_key(key: number) { return contents[find(key)]; }
  has(item: T) { return find(T.id) >= 0; }
  delete(item: T) {
    let index = find(T.id);
    if (index < 0) return;
    let last = contents.pop();
    if (index !== contents.length) contents[index] = last;
  }
}

That gives you insertion in O(1), classic iteration without overhead (for (let i = 0; i < unsorted_array.size(); i++) { let entry = unsorted_array.get_by_index(i); ...}), deletion and has in O(n). I expect has will only actually be slower than doing binary search on an ordered array once you exceed 30-50 elements; and of course it depends on your use case whether has performance matters at all.

Temporary work-around I thought of until I find something better. Basically, just using a Sparse Set.

interface Entry {
  id: number;
}

export class SparseSet<T extends Entry> {
  dense: Array<T>;
  sparse: Map<number, number>;
  
  constructor() {
    this.dense = [];
    this.sparse = new Map<number, number>();
  }

  get size() {
    return this.dense.length;
  }
  
  contains(key: number) {
    let denseIndex = this.sparse.get(key);
  
    if (denseIndex === undefined || denseIndex >= this.dense.length) {
      return false;
    }
  
    let denseItem = this.dense[denseIndex];
  
    return denseItem.id === key;
  }

  delete(key: number) {
    if (!this.contains(key)) { return; }

    let denseIndex = this.sparse.get(key);

    let lastItem = this.dense.pop();

    if (this.dense.length > 0) {
      this.dense[denseIndex] = lastItem; 
      
      this.sparse.set(lastItem.id, denseIndex);
    }
  }

  add(key: number, item: T) {
    if (this.contains(key)) { return; }
  
    this.sparse.set(key, this.dense.length);
    this.dense.push(item);
  }
}

Then you can add and delete like this:

let entity = new Entity();
let items = new SparseSet<Entity>();
items.add(entity.id, entity);
items.delete(entity.id);

And iterate without performing allocations like this:

for (let i = 0; i < items.size; i++) {
  let item = items.dense[i];
}