62

For some algorithm I was writing recently I thought that a hash would be excellent. I thought that I could probably just use the member variables in an object as key value pairs. I am not sure if this is optimal since I don't really know what is going on behind the scenes. I also suppose that V8 does it differently than other environments. I do however imagine that looking up member variables would be pretty quick (hopefully)?

That all said, I am wondering if the run time complexity of writing, reading, creating and removing member variables in JavaScript objects are all O(1). If there are differences in environment (v8 vs others) what are they?

Improve this question
5
  • If you want to lookup for your object by some field why do you care about adding and removing? ID is not supposed to change after object instanciation. Commented Sep 3, 2012 at 3:42
  • @aviad I suppose adding and removing isn't as big of deal. I don't see a use case for more than a few million pairs, and even that is most likely ridiculous for this use case in particular. Then again, people may want to use this specific function for other things. I'd like to provide some guidance. Commented Sep 3, 2012 at 3:52
  • "use the member variables in a object as key value pairs" - That's pretty much what the "member variables" are, isn't it? Commented Sep 3, 2012 at 4:07
  • @nnnnnn well I haven't necessarily seen any guarantees made about the performance. They are key value pairs, but you can say that about any variable in any language. Commented Sep 4, 2012 at 0:15
  • "They are key value pairs, but you can say that about any variable in any language" - No you can't: in most languages strings, numbers and booleans are just values with no associated keys. My point was that a JS object's job is to hold a collection of key/value pairs (where the value might be a reference to a function or other object). I realise this doesn't help you with your question about performance. Commented Sep 4, 2012 at 3:46

3 Answers 3

Reset to default
74

Performance wise, it seems safe to treat them as hashes. Historically there were a lot of articles that said not to trust this. From what I've experienced there are definitely cases where an Object may be more ergonomic than Map.

Benchmarked here - https://jsfiddle.net/soparrissays/Lt0znmxw/

You can see that that regardless of the size of the object each CRUD operation is able to perform around the same number of ops/sec indicating that each operation is O(1). The following run is in Chrome:

100 keys (create) x 13,326,160 ops/sec ±9.42% (34 runs sampled) 1k Keys (create) x 13,757,260 ops/sec ±9.15% (34 runs sampled) 100k Keys (create) x 12,434,691 ops/sec ±7.91% (34 runs sampled) 1M Keys (create) x 12,678,435 ops/sec ±13.12% (38 runs sampled) 100 keys (read) x 80,126,804 ops/sec ±0.24% (101 runs sampled) 1k Keys (read) x 80,333,384 ops/sec ±0.14% (102 runs sampled) 100k Keys (read) x 80,154,201 ops/sec ±0.17% (103 runs sampled) 1M Keys (read) x 80,259,463 ops/sec ±0.13% (98 runs sampled) 100 keys (update) x 71,771,379 ops/sec ±0.19% (100 runs sampled) 1k Keys (update) x 71,851,829 ops/sec ±0.13% (103 runs sampled) 100k Keys (update) x 71,804,254 ops/sec ±0.13% (103 runs sampled) 1M Keys (update) x 71,770,332 ops/sec ±0.13% (98 runs sampled) 100 keys (destroy) x 22,673,628 ops/sec ±0.52% (100 runs sampled) 1k Keys (destroy) x 20,852,449 ops/sec ±0.60% (93 runs sampled) 100k Keys (destroy) x 21,137,940 ops/sec ±0.86% (97 runs sampled) 1M Keys (destroy) x 21,436,091 ops/sec ±0.56% (96 runs sampled)

In the past, I had seen other browsers behave similarly.

2023 update

I should have just read the source code - If I'm reading this right, it's a map with more functionality around it https://github.com/v8/v8/blob/2b79cfd81f6acdfec29661ce2b39d60f4a45b14f/src/objects/js-objects.cc#L2391

MaybeHandle<JSObject> JSObject::New(Handle<JSFunction> constructor, Handle<JSReceiver> new_target, Handle<AllocationSite> site) { // If called through new, new.target can be: // - a subclass of constructor, // - a proxy wrapper around constructor, or // - the constructor itself. // If called through Reflect.construct, it's guaranteed to be a constructor. Isolate* const isolate = constructor->GetIsolate(); DCHECK(constructor->IsConstructor()); DCHECK(new_target->IsConstructor()); DCHECK(!constructor->has_initial_map() || !InstanceTypeChecker::IsJSFunction( constructor->initial_map().instance_type())); Handle<Map> initial_map; ASSIGN_RETURN_ON_EXCEPTION( isolate, initial_map, JSFunction::GetDerivedMap(isolate, constructor, new_target), JSObject); constexpr int initial_capacity = V8_ENABLE_SWISS_NAME_DICTIONARY_BOOL ? SwissNameDictionary::kInitialCapacity : NameDictionary::kInitialCapacity; Handle<JSObject> result = isolate->factory()->NewFastOrSlowJSObjectFromMap( initial_map, initial_capacity, AllocationType::kYoung, site); return result; }

I'll speculate that Map may buy you some performance, but its clear objects are plenty fast, and their properties appear to belong to a hash under the hood. So of course choose the right tool for the job. If you need all the tooling built up around Objects, its still safe to use them clearly!

Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

It may not affect your statistics, but in the teardown function, n is undefined. You specified a global but jsPerf has wrapped the code in a function. So the function (if called) is throwing an error that seems to be ignored by jsPerf.
@RobG thanks for that catch. I made one update to: jsperf.com/objects-as-hashes-100k/2 It didn't seem to affect performance that much. Actually it was slightly faster in all ops. Constant time change. I think I'll just leave it for now. Although, I should definitely fix that.
So the summary is that it IS constant time for all CRUD operations ?
@temporary_user_name YES! see the below answer from Matt Ball. I don't know why this answer is the top one it doesn't really get to the meat of the question.
@yunggun at the time this post was created there was no guarantee that this was the case. In fact, all articles that existed out there said "objects are not hashes stop treating them like they are". To prove that this was the case, I ran some perf tests. It showed that it was indeed true that everything was constant time. There is no specification that says this must be true (at least none that I could find at the time). Objects are objects not dictionaries, it just so happens that the common implementation in JS is that they are hashes.
|
13

JavaScript objects are hashes. I cannot imagine any sane implementation that would not provide constant-time CRUD operations on object properties.

Are you seeing specific performance issues with this approach?

Improve this answer

9 Comments

No performance issues yet. I'll run a larger test soon, and as @David mentioned in the comments I'll make a benchmark. I suppose part of this question was just curiosity. I make the assumption that since it functions like a hash that it is a hash. Wasn't totally sure though. Also, I am not certain if there are upper bounds on how many member variables you could possibly have.
By the pigeonhole principle, there is a finite upper limit on the number of member variables you can have before degrading performance (for instance, due to hash collisions). However, unless you're deliberately picking pathologically bad object keys, and using a large number of them, you're just not going to see this degradation.
I can imagine implementations might not necessarily represent Javascript objects as hashtables - JScript.NET, for example, used the CLR's typesystem, which meant that each field was accessed by a memory offset rather than a hashtable lookup, presumably per-object modifications were made using reflection or at least a reallocation.
@MattBall—ECMAScript objects are specified to be simple name/value pairs, the term "hash" may well infer much more functionality to some. Perhaps javascript objects are implemented as hashes underneath, who knows? David's comment is fair — test it and see. It may be that different aspects have different performance in different browsers. Testing should include a hasOwnProperty filter too if that is relevant to the OP.
I posted my results from the analysis! Thanks again!
|
-3

Objects in JavaScript are an example of a Hash Table because object data is represented as keys & values.

Improve this answer

1 Comment

This isn't a good explanation... You could have any data structure under the hood, just because the interface is key/value based does not guarantee O(1) lookup

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.