如何在不分配的情况下迭代 Javascript 映射或对象？

Question

我正在 Javascript 开发一款游戏，其中涉及尽快运行渲染循环。我注意到 GC（垃圾收集器）尖峰中断了平滑的帧速率，并且在分析之后我发现我的实体查询系统正在生成大量垃圾。

在这样做的过程中，我发现在 Javascript 中。在我的代码的一部分中，我正在做这样的事情：

let minimumSet = this.getSmallestEntitySet(componentTypes);

for (let entity of minimumSet) {
  // handle entity
}

不幸的是，只是执行 for of 循环会导致分配（因为每次循环运行时它都会创建一个新的迭代器对象），并且由于这是运行如此频繁，所以产生大量垃圾。我环顾四周，找不到是否有一种方法可以在不执行分配的情况下迭代 Set、Map 或 Object。例如，对于 Javascript 数组，您可以对其进行迭代，同时避免这样的分配：

for (let i = 0; i < arr.length; i++) {
  let item = arr[i];

  // handle item
}

但是我找不到一种方法来像这样使用常规的 for 循环迭代 Map 或 Set。可能吗？

假设这是不可能的，我假设解决方法是使用排序数组而不是映射，对吧？唯一的问题是插入和删除是 O(log n) 而不是 O(1)，但我想这可能是值得的，只是为了避免分配。

我最好的选择是有没有一种方法可以在不执行分配的情况下迭代这些集合？

Answer 1

我想到了临时解决方法，直到找到更好的方法。基本上，只使用稀疏集。

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);
  }
}

然后可以这样增删：

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

并在不执行分配的情况下进行迭代：

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

Answer 2

（此处为 V8 开发人员。）

正如您链接到的问题所指出的，JavaScript 引擎（至少 V8）确实优化了迭代协议的规范文本所讨论的临时对象；尽管完整的答案（通常如此）是“视情况而定”。

一个影响是优化编译器所做的事情是优化事物，而那些不会立即启动（因为通常情况下，这会浪费精力）。所以如果你只运行一个函数几次，你会看到它的未优化版本分配短暂的垃圾。但这很快就会改变（具体取决于引擎），只要该功能被认为是“热门”并得到优化。

您可能运行遇到的另一个问题是直接迭代 Map（如：let map = new Map(); ...; for (let e of map) {...} 指定为 return e每次作为一个数组[key, value]。这个数组没有被优化掉；它必须在每次迭代中分配。但是如果你只对处理值感兴趣，你可以通过迭代来避免创建它值：for (let v of map.values()) {...} 不分配任何短期对象。迭代 map.keys() 也是如此。

如果您同时需要键和值，您可以将对键的迭代与映射查找相结合：for (let key of map.keys()) { let value = map.get(key); ...}，但是这比对值进行迭代要慢很多。如果您的对象按照您的答案实现 interface Entry，即它们有一个属性携带它们的密钥，那么您可以改用它：for (let value of map.values()) { let key = value.id; ...}.

综上所述：如果 SparseSet 解决方案适合您，那当然也很棒。你甚至可以让它更有效率一点：如果你将 add 更改为 add(item: T) { let key = item.id; ...} 并更新 delete 以包含 this.sparse.delete(key)，那么集合本身可以保证其内部数据是始终一致，然后 contains 可以像 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)

排序数组的插入和删除是 O(n)，因为您可能需要移动整个内容。（如果您使用二进制搜索，则通过排序键查找元素需要 O(log n)。）但是，使用 unsorted 数组可能比直觉上预期的要快，只要它们保持小规模（大约几十个条目）。类似于：

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;
  }
}

这为您提供了 O(1) 的插入、无开销的经典迭代 (for (let i = 0; i < unsorted_array.size(); i++) { let entry = unsorted_array.get_by_index(i); ...})、删除和 O(n) 的 has。我预计 has 一旦超过 30-50 个元素，实际上只会比对有序数组进行二进制搜索慢；当然，has 性能是否重要取决于您的用例。

如何在不分配的情况下迭代 Javascript 映射或对象？

How to iterate a Javascript Map or Object without allocating?

javascript

performance

iterator

set

v8