Monday, May 20, 2024
 Popular · Latest · Hot · Upcoming
8
rated 0 times [  14] [ 6]  / answers: 1 / hits: 24192  / 12 Years ago, mon, september 3, 2012, 12:00:00

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?


More From » performance

 Answers
7

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 the all the tooling built up around Objects, its still safe to use them clearly!


[#83277] Saturday, September 1, 2012, 12 Years  [reply] [flag answer]
Only authorized users can answer the question. Please sign in first, or register a free account.
jameson

Total Points: 534
Total Questions: 103
Total Answers: 102

Location: Lithuania
Member since Fri, Sep 4, 2020
4 Years ago
;