V8 JavaScript对象与二叉树对比

Question

有没有比使用JavaScript Object更快的方式在JavaScript中（特别是通过node.js在V8上）搜索数据，但不使用C/C++模块？ 这可能已经过时了，但它建议为每个属性动态生成一个新类。这让我想知道二叉树实现是否会更快，然而情况似乎并非如此。

二叉树实现不太平衡，因此通过平衡可能会变得更好（只有前26个值是手动平衡的）。

有人知道为什么或如何改进吗？另外一件事：动态类的概念是否意味着实际上有大约260,000个属性（在第二个链接的jsperf基准测试中），并且随后保留在内存中的动态类定义链？

- CoryG

---

这似乎是一个 XY 问题。你的使用场景是什么？你是否进行了基准测试来确定纯对象绝对不适用于你的使用场景？ - mscdex

你真的需要描述一个具体的使用情况。"更快速地搜索数据"并没有描述你实际要解决的问题。这个问题，就目前而言，过于不具体。 - jfriend00

使用案例是在数十万条记录中搜索关键字。我认为这一点从附加的自定义jsperf性能测试中可以清楚地看出差异。 - CoryG

Answer 1

V8使用“映射”这一概念来描述对象中数据的布局。

这些映射可以是“快速映射”，它们指定了从对象开头到特定属性位置的固定偏移量，或者它们可以是“字典映射”，它们使用哈希表提供查找机制。

每个对象都有一个指向描述它的映射的指针。

通常，对象最初具有快速映射。当使用快速映射向对象添加属性时，该映射会过渡到新映射，该映射描述了对象中新属性的位置。如果需要，对象将重新分配足够的空间以容纳新数据项，并将对象的映射指针设置为新映射。

旧映射保留了从中进行的转换的记录，包括指向新映射的指针和导致映射转换的属性的描述。

如果另一个具有旧映射的对象添加相同的属性（这很常见，因为同一类型的对象倾向于以相同的方式使用），那么该对象将只使用新映射 - 在这种情况下，V8不会创建新映射。

然而，一旦属性数量超过某个阈值（实际上，当前的度量标准与使用的存储空间有关，而不是实际的属性数量），对象就会改为使用字典映射。此时，对象将使用哈希表进行重写。一般来说，它不会再经历任何映射转换-添加的任何其他属性都将放入哈希表中。

快速映射允许V8生成优化代码（使用Crankshaft），其中对象内部属性的偏移量被硬编码到机器代码中。这使得它在可以这样做的情况下非常快-它避免了任何查找的需要。

显然，生成的机器代码取决于映射-如果对象的数据布局发生更改，则必须在必要时丢弃并重新优化代码。 V8具有类型分析机制，该机制收集有关在未优化代码执行期间各种对象的类型的信息。 它不会触发对代码的优化，直到满足某些稳定性约束条件为止-其中之一是函数中使用的对象的映射不经常更改。

这里有更详细的描述如何工作的。

这里有一个视频，其中V8的主要开发人员描述了诸如地图转换等内容。

针对您特定的测试用例，我认为在准备循环中添加属性时，它会经过几百个地图转换，然后最终转换为基于字典的对象。它肯定不会经过260,000次地图转换。

关于您关于二叉树的问题：一个大小适当的哈希表（具有合理的哈希函数和大量对象）将始终优于二叉树，如果您只是搜索用例（似乎您的测试代码是这样做的），因为所有插入都是在设置阶段完成的。

- sheltond