performance - Javascript Object Big-O - Stack Overflow

admin管理员组

文章数量:1291568

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

Javascript:

var myObject = {
    firstName: "Foo",
    lastName: "Bar",
    email: "[email protected]"
};

Java:

HashMap<String, String> myHashMap = new HashMap<String, String>();
myHashMap.put("firstName", "Foo");
myHashMap.put("lastName", "Bar");
myHashMap.put("email", "[email protected]");

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 bees 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!

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

Javascript:

var myObject = {
    firstName: "Foo",
    lastName: "Bar",
    email: "[email protected]"
};

Java:

HashMap<String, String> myHashMap = new HashMap<String, String>();
myHashMap.put("firstName", "Foo");
myHashMap.put("lastName", "Bar");
myHashMap.put("email", "[email protected]");

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 bees 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!

• javascript
• performance
• big-o

Share Improve this question Follow edited Feb 4, 2015 at 20:15 Peter Lawrey 534k8282 gold badges770770 silver badges1.2k1.2k bronze badges asked Feb 4, 2015 at 19:34 user2712937user2712937 29133 silver badges1111 bronze badges 7

• check out this link, it has some good information on your question: github./benblack86/java-snippets/blob/master/resources/… – Evan Bechtol Commented Feb 4, 2015 at 19:38
• 1 @EvanBechtol that paper is about Java, and this question is about JavaScript performance. – Pointy Commented Feb 4, 2015 at 19:39
• 2 Object storage is implementation dependent. That said, this question can be answered for v8 and spidermonkey, but these are long answers. – Florian Margaine Commented Feb 4, 2015 at 19:39
• This question is under the Java tag. Regardless, this is a good resource for JS javascript.crockford./survey.html stackoverflow./questions/7374171/… – Evan Bechtol Commented Feb 4, 2015 at 19:41
• 1 Good question! The answer is, unfortunately, implementation dependent. Basically, all js object handling is O(1). v8 (Chrome's engine) starts off by creating a struct for your object, giving you the fastest possible access. Once a key count is exceeded, it falls back to basically hash-table mode. More on that here. – Zirak Commented Feb 4, 2015 at 19:46

 |  Show 2 more ments

1 Answer 1

Sorted by: Reset to default 10

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 plicated 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 plicated situation.

This blog post, linked in the question ments by @Zirak, has a quite good discussion of the mon 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 plicated 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.

本文标签： performanceJavascript Object BigOStack Overflow