Object.keys() complexity?
JavascriptPerformanceTime ComplexityEcmascript 5Javascript Problem Overview
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.
Javascript Solutions
Solution 1 - Javascript
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
Solution 2 - Javascript
(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" :-)