为什么“地图"操作比“对象"慢得多.在 JavaScript (v8) 中用于整数键? [英] Why "Map" manipulation is much slower than "Object" in JavaScript (v8) for integer keys?

问题描述

我很高兴使用 Map 在我的 JavaScript 代码库中的任何地方进行索引访问，但我刚刚偶然发现了这个基准:https://stackoverflow.com/a/54385459/365104

I was happily using Map for indexed accessed everywhere in my JavaScript codebase, but I've just stumbled upon this benchmark: https://stackoverflow.com/a/54385459/365104

我也在这里重新创建了它:https://jsben.ch/HOU3g

I've re-created it here as well: https://jsben.ch/HOU3g

基准测试所做的基本上是用 100 万个元素填充地图，然后对它们进行迭代.

What benchmark is doing is basically filling a map with 1M elements, then iterating over them.

我希望 Map 和 Object 的结果相当，但它们有很大的不同 - 有利于 Object.

I'd expect the results for Map and Object to be on par, but they differ drastically - in favor of Object.

这是预期的行为吗?可以解释吗?是因为订货要求吗?或者因为地图正在做一些关键的散列?或者仅仅因为 Map 允许任何对象作为键(我希望它使用指针地址作为键，不需要任何散列)?Map 和 Object 索引算法有什么区别?

Is this expected behavior? Can it be explained? Is it because of the ordering requirement? Or because map is doing some key hashing? Or just because Map allows any object as key (I'd expect it using pointer address for key then, which does not need any hashing)? What is the difference between the Map and Object indexing algorithms?

这是非常出乎意料和令人沮丧的 - 基本上我将不得不恢复到老派的对象即地图"编码风格.

This is quite unexpected and discouraging - basically I'll have to revert back to the old-school "object as map" coding style.

更新 #1

正如评论中所建议的，对象可能被优化为数组(因为它是按整数索引的，从零开始).

As suggested in comments, the Object might be optimized to Array (since it is indexed by integer, starting from the zero).

将迭代顺序从 size 更改为 0 - 对象仍然是 快 2 倍.使用字符串作为索引时，Map 的性能提高了 2 倍.

Changing the iteration order from size to 0 - Object is still 2x faster. When using strings as index, Map performs 2x better.

推荐答案

(此处为 V8 开发人员.)

(V8 developer here.)

我将不得不恢复到老式的对象即地图"编码风格.

I'll have to revert back to the old-school "object as map" coding style.

如果您这样做，您将成为误导性微基准测试的受害者.

If you do that, you will have fallen victim to a misleading microbenchmark.

在使用连续整数作为键的非常特殊的情况下，一个普通的 Object 会更快，是的.在这种情况下，没有什么比连续数组更胜一筹了.因此，如果您提到的代码库中随处可见的索引访问"确实使用了索引集，例如从 0 到 1M 的整数，那么使用对象或数组是个好主意.但那是特例.如果索引空间很稀疏，事情看起来已经不一样了.

In the very special case of using consecutive integers as keys, a plain Object will be faster, yes. Nothing beats a contiguous array in that scenario. So if the "indexed accesses everywhere in your codebase" that you mentioned are indeed using index sets like the integers from 0 to 1M, then using an Object or Array is a good idea. But that's a special case. If the index space is sparse, things will already look different.

在以随机顺序使用任意字符串的一般情况下，Map 的性能明显优于 Object.更重要的是，这种对象属性访问的处理方式(在 V8 中，很可能在其他引擎中也是如此)具有非本地效果:如果一个函数对对象的慢速路径施加过大的压力属性查找处理系统，那么这可能会减慢一些其他函数的速度，这些函数依赖于相同的慢路径来访问它们的属性.

In the general case of using arbitrary strings in random order, a Map will perform significantly better than an Object. Even more importantly, the way such object property accesses are handled (in V8, and quite possibly in other engines too) has non-local effects: if one function puts excessive stress on the slow path of the object property lookup handling system, then that will likely slow down some other functions relying on that same slow path for their property accesses.

根本原因是引擎针对不同的使用模式优化不同的东西.引擎可以在引擎盖下实现几乎相同的对象和地图；但这不是理想的行为，因为不同的使用模式受益于不同的内部表示和实现选择.所以引擎允许你给他们提供一个提示:如果你使用一个 Map，引擎会知道你打算把这个东西用作一个地图(废话！)，随机键会出现在那里去.如果您使用 Object，那么引擎将(至少在开始时)假设您想要最适合您的平均对象的优化集，其中属性集相当小且静态.如果您使用 Array(或仅具有整数属性的 Object，这在 JS 中几乎相同)，那么您就可以让引擎轻松地为您提供快速整数索引访问.

The fundamental reason is that engines optimize different things for different usage patterns. An engine could implement Objects and Maps pretty much the same under the hood; but that wouldn't be the ideal behavior, because different usage patterns benefit from different internal representations and implementation choices. So engines allow you to provide them with a hint: if you use a Map, the engine will know that you're planning to use the thing as a map (duh!), where random keys will come and go. If you use an Object, then the engine will (at least at first) assume that you want the set of optimizations that work best for your average object, where the set of properties is fairly small and static. If you use an Array (or Object with only integer properties, which is nearly the same thing in JS), then you're making it easy for the engine to give you fast integer-indexed accesses.

使用 "x" + i 作为键是一个很好的建议，它展示了微基准可以多快地更改，从而产生相反的结果.但这里有一个剧透:如果您(仅)进行此修改，那么您测量的大部分内容将是数字到字符串的转换和字符串内部化，而不是 Map/Object 访问性能本身.

Using "x" + i as key is a good suggestion to demonstrate how quickly a microbenchmark can be changed so it appears to produce opposite results. But here's a spoiler: if you do (only) this modification, then a large part of what you're measuring will be number-to-string conversion and string internalization, not Map/Object access performance itself.

当心微基准；它们具有误导性.您确实必须非常深入地分析它们(通过分析和/或检查生成的代码，和/或通过跟踪其他引擎内部结构)以确保它们正在测量您认为它们的内容.重新测量，因此产生的结果告诉您您认为他们告诉您的内容.

Beware of microbenchmarks; they are misleading. You really have to analyze them quite deeply (by profiling, and/or by inspecting generated code, and/or by tracing other engine internals) to be sure that they're measuring what you think they're measuring, and hence are producing results that are telling you what you think they're telling you.

通常，强烈建议使用代表性测试用例进行性能测量.理想情况下，您的应用程序本身；或者通过将其中的真实部分提取到对真实数据进行操作的测试用例中.如果您无法通过对整个生产应用程序的压力测试来衡量两个实现选择之间的差异，那么就不必担心差异.使用微基准(即几条人工制作的线)，我几乎可以证明"任何不适用于一般情况的东西.

In general, it is strongly recommended to use representative test cases for performance measurements. Ideally, your app itself; or by extracting a realistic part of it into a testcase operating on realistic data. And if you can't measure a difference between two implementation choices with a stress test for your entire production app, then it's not a difference worth worrying about it. With a microbenchmark (i.e. a couple of artificially crafted lines), I can "prove" almost anything that doesn't apply to the general case.

这篇关于为什么“地图"操作比“对象"慢得多.在 JavaScript (v8) 中用于整数键?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！