Performance of key lookup in JavaScript object

Question

I just read this question: are there dictionaries in javascript like python?

One of the answers said that you can use JavaScript objects like Python dictionaries. Is that true? What is the performance of a key lookup in an object? Is it O(1)? Is adding a key to the object also constant time (hashing)?

Solution 1

The V8 design docs imply lookups will be at least this fast, if not faster:

Most JavaScript engines use a dictionary-like data structure as storage for object properties - each property access requires a dynamic lookup to resolve the property's location in memory. This approach makes accessing properties in JavaScript typically much slower than accessing instance variables in programming languages like Java and Smalltalk. In these languages, instance variables are located at fixed offsets determined by the compiler due to the fixed object layout defined by the object's class. Access is simply a matter of a memory load or store, often requiring only a single instruction.

To reduce the time required to access JavaScript properties, V8 does not use dynamic lookup to access properties. Instead, V8 dynamically creates hidden classes behind the scenes. [...] In V8, an object changes its hidden class when a new property is added.

It sounds like adding a new key might be slightly slower, though, due to the hidden class creation.

Solution 2

Yes, you can assume that adding a key, and later using it for access are effectively constant time operations.

Under the hood the JS engine may apply some techniques to optimize subsequent lookups, but for the purposes of any algorithm, you can assume O(1).

Solution 3

Take a look at a similar question How does JavaScript VM implements Object property access? and the answer. Here I described the optimization technique used by JS engines and how it affects the key lookup performance. I hope these details help you write more efficient JS code.

Comments

[Saher Ahwal]

Thanks Domenic! so it seems to be safe for me to use Object lookups as dictionary lookups if I am doing more lookups than hashing.

[Randhir Rawatlal]

For V8, is it true that dynamic lookup is not used for both the dot notation as well as the square brackets notation?

[Yixing Liu]

Compare with var first = new Map([ [1, 'one'], [2, 'two'], [3, 'three'], ]); How efficient is var second={'1': one, '2': two, '3': 'three'}?