19947

V8 JavaScript Object vs Binary Tree

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.

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

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?

Answer1:

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.

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.

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.

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.

Here's a video where one of the lead developers of V8 describes stuff like map transitions and lots more.

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

Recommend

  • Why is creating an .exe from a java program not recommended? [duplicate]
  • Excel 2007 Change colour of bars in a single series, based on another field
  • Haskell: List Created Evaluating List Elements
  • RDF - Distributing rdf:type to all items in the list
  • Add spaces between words in spaceless string
  • HALF_PTR Windows data type
  • Convert two columns Pandas data frame to dictionary of list with first column as keys
  • div fade-in when window is scrolled a certain distance from the top
  • How to define an array of floats in Shader properties?
  • Find longest path less than or equal to given value of an acyclic, directed graph in Python
  • How do I bind multiple properties in an Android layout element
  • Reading space separated values file in c++ error
  • A new chart every sheet
  • How do I mock an exported typescript function in a jasmine test?
  • WPF version of .ScaleControl?
  • Check all values in string[] for length?
  • Git describe fails to return most recent annotated tag
  • Android Activity.onWindowFocusChanged doesn't get called from within TabHost
  • Is there a way to do normal logging with EureakLog?
  • $wpdb not working in file of WordPress plugin
  • Asynchronous UI Testing in Xcode With Swift
  • RectangularRangeIndicator format like triangular using dojo
  • angularjs unit test when to use $rootScope.$new()
  • How to add a column to a Pandas dataframe made of arrays of the n-preceding values of another column
  • script to move all files from one location to another location
  • How to model a transition system with SPIN
  • Large data - storage and query
  • align graphs with different xlab
  • AT Commands to Send SMS not working in Windows 8.1
  • using conditional logic : check if record exists; if it does, update it, if not, create it
  • InvalidAuthenticityToken between subdomains when logging in with Rails app
  • Rails 2: use form_for to build a form covering multiple objects of the same class
  • python regex in pyparsing
  • How do I configure my settings file to work with unit tests?
  • Android Google Maps API OnLocationChanged only called once
  • Is it possible to post an object from jquery to bottle.py?
  • Running Map reduces the dimensions of the matrices
  • Android Heatmap on canvas or ImageView
  • How can I use threading to 'tick' a timer to be accessed by other threads?
  • jQuery Masonry / Isotope and fluid images: Momentary overlap on window resize