如何在不分配的情况下迭代Javascript映射或对象? [英] How to iterate a Javascript Map or Object without allocating?

问题描述

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

I'm developing a game in Javascript and that involves running the render loop as quickly as possible. I've noticed GC (Garbage Collector) spikes interrupt the smooth frame-rate and after profiling I've discovered that my entity querying system is generating a ton of garbage.

这样做，我发现迭代器会导致分配在Javascript中.在我的代码的一部分中，我正在做这样的事情:

In doing so, I've found that iterators cause allocations in Javascript. In one section of my code I'm doing something like this:

let minimumSet = this.getSmallestEntitySet(componentTypes);

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

不幸的是，仅对 for 进行循环会导致分配(因为每次循环运行时都会创建一个新的迭代器对象)，并且由于经常运行，因此会产生大量垃圾.我环顾四周，无法找出是否无需执行即可迭代 Set ， Map 或 Object 的方法分配.例如，使用Javascript数组，您可以迭代它，同时避免这样的分配:

Unfortunately just doing a for of loop causes allocations (because it creates a new iterator object every time the loop is run), and since this is run so often, a ton of garbage is generated. I was looking around and I couldn't find out whether or not there was a way to iterate a Set, Map, or Object without performing allocations. For example, with a Javascript array you can iterate it while avoiding allocations like this:

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

  // handle item
}

但是我找不到像常规的for循环那样迭代 Map 或 Set 的方法.有可能吗?

But I couldn't find a way to do iterate Map or Set like this with just a regular for loop. Is it possible?

假设这是不可能的，那么我认为解决方法是改用排序数组而不是映射，对吗?唯一的问题是插入和删除是 O(log n)而不是 O(1)，但是我想这样做可能是值得的，只是避免分配.

Assuming this is not possible, 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) instead of O(1), but it might be worth it I suppose just to avoid allocations.

我最好的选择是是否有办法在不执行分配的情况下迭代这些集合?

Is that my best option is there a way to iterate these collections without performing allocations?

推荐答案

(此处为V8开发人员.)

(V8 developer here.)

正如您所链接的问题所指出的那样，JavaScript引擎(至少是V8)确实优化了迭代协议规范文本所讨论的临时对象；尽管完整的答案(通常如此)是取决于".

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.

您可能会遇到的另一个问题是直接遍历 Map (如: let map = new Map(); ...; for(用于map的e)){...} 被指定为每次将 e 作为数组 [key，value] 返回.但是，如果您只想对值进行处理，则可以通过仅对值进行迭代来避免创建它: for(map.values()的v){...}不分配任何短期对象，对于遍历 map.keys()的情况也是如此.

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().

如果您既需要键又需要值，则可以将键的迭代与地图查找结合起来: for(让map.keys()的键){let value = map.get(key);...} ，但是，这比遍历这些值要慢得多.如果您的对象像答案中那样实现 interface Entry ，即它们具有携带其键的属性，那么您可以改用它: for(map.values()的值){let键= value.id;...} .

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

所有所说的:如果 SparseSet 解决方案适合您，那么当然也很酷.您甚至可以提高效率:如果将 add 更改为 add(item:T){let key = item.id;...} 并更新 delete 以包含 this.sparse.delete(key)，那么集合本身可以保证其内部数据始终保持一致，然后 contains 就可以像 return this.sparse.get(key)！== undefined; .

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

我认为解决此问题的方法是改用排序数组而不是映射，对吗?唯一的问题是插入和删除是 O(log n)

在已排序数组上的插入和删除为O(n)，因为您可能必须将整个内容移到其他位置.(如果使用二进制搜索，则通过其排序键查找元素就是O(log n)的原因.)但是，只要 unsorted 数组可以比人们直观地期望的快，只要它们仍然很小(大约几十个条目).像这样:

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

这使您可以插入O(1)，而无需开销的经典迭代( for(let i = 0; i< unsorted_array.size(); i ++)){let entry = unsorted_array.get_by_index(i);...} )，删除并在O(n)中具有 .我希望 has 实际上只会比在超过30-50个元素时对有序数组进行二进制搜索要慢；当然，这取决于您的用例，是否性能根本不重要.

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.

这篇关于如何在不分配的情况下迭代Javascript映射或对象?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！