Javascript Object Big-O

Question

Coming from Java, Javascript object reminds me of HashMap in Java.

Javascript:

var myObject = {
    firstName: "Foo",
    lastName: "Bar",
    email: "foo@bar.com"
};

Java:

HashMap<String, String> myHashMap = new HashMap<String, String>();
myHashMap.put("firstName", "Foo");
myHashMap.put("lastName", "Bar");
myHashMap.put("email", "foo@bar.com");

In Java HashMap, it uses the hashcode() function of the key to determine the bucket location (entries) for storage, and retrieval. Majority of the time, for basic operations such as put() and get(), the performance is constant time, until a hash collision occurs which becomes O(n) for these basic operations because it forms a linked list in order to store the collided entries.

My question is:

1. How does Javascript stores object?
2. What is the performance of operations?
3. Will there ever be any collision or other scenarios which will degrade the performance like in Java

Thanks!

Answer 1

Javascript looks like it stores things in a map, but that's typically not the case. You can access most properties of an object as if they were an index in a map, and assign new properties at runtime, but the backing code is much faster and more complicated than just using a map.

There's nothing requiring VMs not to use a map, but most try to detect the structure of the object and create an efficient in-memory representation for that structure. This can lead to a lot of optimizations (and deopts) while the program is running, and is a very complicated situation.

This blog post, linked in the question comments by @Zirak, has a quite good discussion of the common structures and when VMs may switch from a struct to a map. It can often seem unpredictable, but is largely based on a set of heuristics within the VM and how many different objects it believes it has seen. That is largely related to the properties (and their types) of return values, and tends to be centered around each function (especially constructor functions).

There are a few questions and articles that dig into the details (but are hopefully still understandable without a ton of background):

• slow function call in V8 when using the same key for the functions in different objects
• Why is getting a member faster than calling hasOwnProperty?
• http://mrale.ph/blog/2013/08/14/hidden-classes-vs-jsperf.html (and the rest of this blog)

The performance varies greatly, based on the above. Worst case should be a map access, best case is a direct memory access (perhaps even a deref).

There are a large number of scenarios that can have performance impacts, especially given how the JITter and VM will create and destroy hidden classes at runtime, as they see new variations on an object. Suddenly encountering a new variant of an object that was presumed to be monomorphic before can cause the VM to switch back to a less-optimal representation and stop treating the object as an in-memory struct, but the logic around that is pretty complicated and well-covered in this blog post.

You can help by making sure objects created from the same constructor tend to have very similar structures, and making things as predictable as possible (good for you, maintenance, and the VM). Having known properties for each object, set types for those properties, and creating objects from constructors when you can should let you hit most of the available optimizations and have some awfully quick code.