V8 JavaScript对象与二叉树 [英] V8 JavaScript Object vs Binary Tree
问题描述
是否有比使用JavaScript Object在JavaScript(特别是通过node.js在V8上，但没有c/c ++模块)搜索数据的更快的方法?
Is there a faster way to search data in JavaScript (specifically on V8 via node.js, but without c/c++ modules) than using the JavaScript Object?
这可能已经过时了，但它建议动态创建一个新类为每个属性生成的.这让我想知道二进制树的实现是否可能更快，但是情况如此.
This may be outdated but it suggests a new class is dynamically generated for every single property. Which made me wonder if a binary tree implementation might be faster, however this does not appear to be the case.
二叉树实现的平衡性不好，因此平衡可能会更好(只有前26个值是手工粗略平衡的.)
The binary tree implementation isn't well balanced so it might get better with balancing (only the first 26 values are roughly balanced by hand.)
有人对为什么或如何加以改进有想法吗?另一个要注意的是:动态类概念是否意味着实际上存在约260,000个属性(在第二个链接的jsperf基准测试中)，并随后在内存中保存了动态类定义链?
Does anyone have an idea on why or how it might be improved? On another note: does the dynamic class notion mean there are actually ~260,000 properties (in the jsperf benchmark test of the second link) and subsequently chains of dynamic class definitions held in memory?
推荐答案
V8使用映射"的概念，它们描述了对象中数据的布局.
V8 uses the concepts of 'maps', which describe the layout of the data in an object.
这些映射可以是快速映射"，用于指定从对象开始处可以找到特定属性的固定偏移量，也可以是字典映射"，它使用哈希表提供查找机制.
These maps can be "fast maps" which specify a fixed offset from the start of the object at which a particular property can be found, or they can be "dictionary map", which use a hashtable to provide a lookup mechanism.
每个对象都有一个指向描述它的地图的指针.
Each object has a pointer to the map that describes it.
通常，对象从快速地图开始.当将属性添加到具有快速映射的对象时，该映射将转换为描述该新属性在对象中的位置的新映射.如果有必要，可以为新数据项重新分配足够的空间来放置对象，并且该对象的映射指针将设置为新映射.
Generally, objects start off with a fast map. When a property is added to an object with a fast map, the map is transitioned to a new one which describes the location of the new property within the object. The object is re-allocated with enough space for the new data item if necessary, and the object's map pointer is set to the new map.
旧地图保留了从旧地图开始的过渡记录，包括指向新地图的指针以及对其添加导致地图过渡的属性的描述.
The old map keeps a record of the transitions from it, including a pointer to the new map and a description of the property whose addition caused the map transition.
如果另一个具有旧地图的对象添加了相同的属性(这很常见，因为相同类型的对象倾向于以相同的方式使用)，则该对象将仅使用新地图-V8不会在这种情况下，请创建一个新地图.
If another object which has the old map gets the same property added (which is very common, since objects of the same type tend to get used in the same way), that object will just use the new map - V8 doesn't create a new map in this case.
但是，一旦属性数量超过某个阈值(实际上，当前度量标准取决于所使用的存储空间，而不是实际的属性数量)，则将对象更改为使用字典映射.此时，将使用哈希表重写对象.通常，它不会再进行任何地图转换-添加的任何其他属性都只会放在哈希表中.
However, once the number of properties goes over a certain theshold (in fact, the current metric is to do with the storage space used, not the actual number of properties), the object is changed to use a dictionary map. At this point the object is re-written using a hashtable. In general, it won't undergo any more map transitions - any more properties that are added will just go in the hashtable.
快速映射允许V8生成优化的代码(使用曲轴)，其中对象内属性的偏移量被硬编码为机器代码.这样可以在某些情况下非常快-无需进行任何查找.
Fast maps allow V8 to generate optimized code (using Crankshaft) where the offset of a property within an object is hard-coded into the machine code. This makes it very fast for cases where it can do this - it avoids the need for doing any lookup.
很明显，然后生成的机器代码取决于映射-如果对象的数据布局发生更改，则必须丢弃该代码，并在必要时重新对其进行优化. V8具有类型分析机制，该机制收集有关未优化代码执行期间各种对象的类型的信息.在满足某些稳定性约束之前，它不会触发代码的优化-其中之一是该函数中使用的对象的映射不会频繁更改.
Obviously, the generated machine code is then dependent on the map - if the object's data layout changes, the code has to be discarded and re-optimized when necessary. V8 has a type profiling mechanism which collects information about what the types of various objects are during execution of unoptimized code. It doesn't trigger optimization of the code until certain stability constraints are met - one of these is that the maps of objects used in the function aren't changing frequently.
Here's a more detailed description of how this stuff works.
此处是一个视频，其中V8的主要开发人员之一介绍了地图过渡等内容.
对于您的特定测试用例，我认为在准备循环中添加属性时，它会经历数百次映射转换，然后最终将转换为基于字典的对象.当然，不会超过260,000.
For your particular test case, I would think that it goes through a few hundred map transitions while properties are being added in the preparation loop, then it will eventually transition to a dictionary based object. It certainly won't go through 260,000 of them.
关于二进制树的问题:大小合适的哈希表(具有合理的哈希函数和大量对象)在您仅作为搜索用例的情况下，其性能总是优于二进制树代码似乎可以做到(所有插入操作都在设置阶段完成).
Regarding your question about binary trees: a properly sized hashtable (with a sensible hash function and a significant number of objects in it) will always outperform a binary tree for a use-case where you're just searching, as your test code seems to do (all of the insertion is done in the setup phase).
这篇关于V8 JavaScript对象与二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
