Object.keys() complexity?

Question

Anyone know the time-complexity of ECMAScript5's Object.keys() in common implementations? Is it O(n) for n keys? Is time proportional to the size of the hash table, assuming a hash implementation?

I'm looking for either guarantees by language implementors or some real world benchmarking.

How many keys do you expect to be having, such that the time complexity of enumerating them matters? — Gabe, Oct 10 '11 at 18:06
@IAbstractDownvoteFactory: While the function `Object.keys()` may be able to return in `O(1)`, *enumerating the results* can't be done in less than `O(n)`. — Gabe, Oct 10 '11 at 18:16
@Gabe Can you explain more about how Object.keys() may be able to return in O(1)? — user137717, Apr 18 '16 at 20:02
@user137717, The Object implementation could _theoretically_ store an array of keys, changing the array whenever a new property is added or one is deleted. The keys function would then simply return the stored array. This has consequences on storage and offloads time spent in the keys function to time spent when creating and deleting keys. — Brian S, Apr 24 '16 at 14:24
Yea, that's what I thought. Doesn't really make sense for the general implementation, but a programmer could do it themselves pretty easily for their own use case. — user137717, Apr 24 '16 at 14:38

score 56 · Accepted Answer · answered Oct 10 '11 at 18:09

56

It appears to be O(n) in V8 (chrome, node.js) at least:

> var hash = {}
>   ,    c = 0;
> 
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
0
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
26
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
49
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
75
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
102

answered Oct 10 '11 at 18:09

Those results make sense for a dense hash map. Does performance degrade as keys get more sparse? – hurrymaplelad Oct 10 '11 at 18:23
1

@hurrymaplelad - What? All JS hash keys are strings. This code effectively generates `{'1':1, '2':1, '3':1, ...}` _sparse_ vs _dense_ keys don't make sense for hash implementations, only arrays. And it really doesn't make any sense for an engine to ever implement a hash as an array since numerical indexes are generally rather rare. Though if you want to test that for some reason, just change `c++` to `c+=Math.random()` which will give you totally un-associatable keys. – Oct 10 '11 at 18:25
1

@cwolves: An `Array` object is just an object whose properties are expected to be whole numbers. Those aren't terribly rare, and there are certainly JS implementations that use arrays to back `Array` instances. – Gabe Oct 10 '11 at 18:53
@cwolves: [expanded your test](http://jsfiddle.net/EGmPb/) to cover variations in magnitude of key size, and results look consistent. You're correct, _sparse vs dense_ does not apply to your test. I was looking for an example with low [load factor](http://en.wikipedia.org/wiki/Hash_table#Load_factor), but that's independent of key choice. Are JS Objects generally implemented as hashmaps? If so, is performance `O(n+s)`, where `s` is the size of the hash table? – hurrymaplelad Oct 10 '11 at 19:29
5

JS Objects are not implemented as hashmaps, rather as pairs of arrays (that is C arrays, not JS Array objects) http://code.google.com/intl/de-DE/chrome/devtools/docs/memory-analysis-101.html#v8_specifics – user123444555621 Oct 10 '11 at 19:48
@Gabe - Not exactly. `Array`s inherit from `Object` and there's often both `dense` and `sparse` implementations under the hood for how those arrays are handled. I'm saying it would be rare to have numerical indexes on a generic object (`{}`). – Oct 10 '11 at 20:05
@Pumbaa80 - Um, Yeah that page says that but it can't be 100% accurate. If it were, you wouldn't have a constant-time lookup on object keys which would be absurd. – Oct 10 '11 at 20:08
@cwolves: You don't need constant-time lookup on object keys in cases where you can do the lookup once when you JIT compile the code. The compiler can then emit code for an array index rather than a hash lookup. – Gabe Oct 10 '11 at 20:32
I just had a look at the V8 source code, and turns out they use something called [FixedArray](http://codesearch.google.com/#OAMlx_jo-ck/src/v8/src/heap.cc&type=cs&l=3981) to store the [object keys](http://codesearch.google.com/#OAMlx_jo-ck/src/v8/src/objects.cc&type=cs&l=4713). My C++ sucks badly, so I won't dig any deeper. – user123444555621 Oct 10 '11 at 21:03
I love the results and discussion, but I don't know what this means. Is this fast or slow? @MarkKahn – Frozenfrank May 21 '20 at 15:27
1

@Frozenfrank -- it's as fast as possible – May 22 '20 at 22:35
This seems to be the case for `Object.values` as well, in case anyone else is wondering. – Automatico Oct 19 '20 at 13:33
It's not the case for string-named properties though, contrary to what has been discussed above. See my answer for more details. – jmrk Nov 19 '20 at 13:32
Chart shows O(N) for a simple case in Chrome 87, Firefox 81, Safari 14 https://jsfiddle.net/9u5ohnmb/ – Victor Dec 15 '20 at 10:26
seems O(1) until twenty entries in the hash map – Dave Ankin Dec 26 '20 at 14:19

score 51 · Answer 2 · answered Nov 19 '20 at 13:31

51

(V8 developer here.)

The answer by Mark Kahn is correct for sufficiently dense integer-keyed/"indexed" properties, where complexity of Object.keys() is indeed O(n).

While the JavaScript spec pretends that all object properties are string-keyed/"named", that's not how modern high-performance engines implement it. Internally there's a huge difference! Indexed properties are stored in an array (as long as they are dense enough), which gives generally much better performance than a {'1': 1, ...} dictionary would.

For objects with thousands of named properties, our implementation indeed uses a hash table (as the question guessed), and that means complexity of Object.keys() is O(n log n). That's because a hash table (of course) stores entries in its own order. Object.keys() must return named properties in the order in which they were created though, which we store as additional metadata, so that means we must sort the keys after retrieving them from the hash table, which is an O(n log n) operation.

Named properties on most objects that occur in practice (up to about a thousand properties) are (usually) stored in creation order in a special kind of internal array, so they can be retrieved in O(n) and don't need to be sorted.

So the summary is really "it depends" :-)

answered Nov 19 '20 at 13:31

jmrk

34,271
7
59
74

Hmm, but the question here is that if I use an `Object.keys()` will it be an `O(n)` or something else? I didn't fully understand your answer... In naive terms, if I have a hash map as follows: `{a:1,b:2,...}` and I use `Object.keys()` for the same, will the time complexity be `O(n)` or something else? Also, what if we just want to get the keys and not sort them? – Shivam Sahil Dec 26 '20 at 08:03
There is no way to get an object's keys without sorting them. And as I wrote, whether the complexity of `Object.keys()` is O(n) or something else depends on the specifics of your object (and, naturally, on the implementation details of the specific version of the specific JavaScript engine you happen to be running on). There are no guarantees. – jmrk Dec 26 '20 at 12:26
the cutoff for this is 20, which you can verify using code from the other answer and using really small objects, but calling Object.keys many times – Dave Ankin Dec 26 '20 at 14:18
@DaveAnkin: if it were that simple, I would have said so. It's not that simple. And it changes over time/versions/implementations. It also usually doesn't matter: for most common cases, assuming that `Object.keys()` has linear complexity is reasonable (even though it won't be true in _all_ cases). Please be aware that "code from the other answer" only illustrates one particular case, not all possible scenarios. – jmrk Dec 27 '20 at 14:01
@jmrk sure, and no benchmark is perfect (i added Math.random().toString(16).substring(2) in order to get longer keys), but for object 20 seems like the cutoff that the original poster was asking for) – Dave Ankin Dec 27 '20 at 15:04
@jmrk thanks for working on v8 and your answer by the way, I'd be curious if you know more about that other cutoff i accidentally discovered. – Dave Ankin Dec 27 '20 at 15:07
1

I'm curious if Object.keys(bigObject).length would still be O(n) or is the js optimizer something that can be relied on to ensure this is O(1) – josh Apr 09 '21 at 21:57
It's never O(1). – jmrk Apr 10 '21 at 20:36
1

I'm pretty sure [Python has insertion-order dictionaries with O(n) iteration](https://stackoverflow.com/questions/39980323/are-dictionaries-ordered-in-python-3-6), so it's definitely possibloe. – nog642 Apr 17 '22 at 16:37
@jmrk So I guess this means that for-in iteration is also O(n log n)? – Hans Brende Aug 11 '22 at 04:29
2

@HansBrende Yes. `for-in` additionally has to walk the prototype chain, which (depending on how you define `n`) might not change asymptotic complexity but is generally more work. – jmrk Aug 11 '22 at 09:45
@jmrk what if we know that the prototype is Object.prototype? Is that fast-tracked for for-in since the prototype chain is only length 1 and all properties are "own" properties? Would for-in be faster than Object.keys in that case since it avoids allocating the array? – Hans Brende Aug 11 '22 at 19:57
1

@HansBrende `for-in` must always visit prototypes, and its fast path allocates an array under the hood. I doubt that it is ever faster than any alternative, but when in doubt, measure it yourself (using your full app or a _very_ realistic simulation of it, not just a simple microbenchmark). – jmrk Aug 11 '22 at 20:35
@jmrk oh WOW, that is really counter-intuitive! Because that means that even if I wanted to extract only ONE property key from an object, the performance would still be O(n log n) due to that hidden array allocation. E.g., `for (let key in obj) return key` would still be O(n log n) rather than O(1) is what you're saying? – Hans Brende Aug 11 '22 at 20:54
Just a side question, are calls to `Object.keys()` and `Object.values()` memoized? Would calling it multiple times result in constant times for subsequent calls if the values of the object haven't changed? – Abir Taheer Dec 29 '22 at 02:06
@AbirTaheer No, AFAIK they are not memoized. Presumably because it's too hard to estimate whether the memory consumption of memoization is worth it. – jmrk Dec 29 '22 at 22:55
@jmrk I'm curious how this compares to the Standard built-in object "Map" and what performance would look like when using map to iterate, and add keys to a new array? Would this be strictly O(n)? (asking for node.js v16+) – JattCode113 Feb 06 '23 at 16:25
1

@JattCode113 it's off-topic for this question, but if I'm reading the code right, iterating over a `Map` should be O(n) in our current implementation. – jmrk Feb 08 '23 at 09:47

Object.keys() complexity?

2 Answers2

Linked