1

Additional Note:

I did check this previous answer and desire an answer that is more current and that is less Chrome specific: Performance of key lookup in JavaScript object

Assuming a standard javascript “dictionary” object with properties like this:

var myObject = {
   Key1: ”Value1”,
   Key2: ”Value2”,
   Key3: ”Value3”,
   …
   Key500: ”Value500”
}

Does anyone know if browsers(etc) internally optimize their retrieval of these properties?

A good case might be auto-sort + binary search.

A not-so-good case might be simple linear search.

EcmaScript standards say the browsers can do the internals as they wish:

[browsers,etc] may support [object’s] internal properties with any implementation-dependent behaviour as long as it is consistent with the specific host object restrictions stated in this document.

and

The mechanics and order of enumerating the properties … is not specified.

I'm not really needing to know a specific optimization, I just want to know if they are trying to optimize beyond a simple linear search.

So, does anyone have "inside" knowledge?

Community
  • 1
  • 1
markE
  • 102,905
  • 11
  • 164
  • 176
  • Of course they do optimize search by key. It's an essential point. Some engine even compile objects as kind of classes in certain cases. – Denys Séguret Apr 19 '13 at 18:16
  • I suspect you're right...but do you have knowledge that they optimize, or are you assuming they do? – markE Apr 19 '13 at 18:18
  • related : http://stackoverflow.com/questions/7700987/performance-of-key-lookup-in-javascript-object – Denys Séguret Apr 19 '13 at 18:19
  • More generally, google for the names of JS engines and "key lookup", "maps" and so on. – Denys Séguret Apr 19 '13 at 18:20
  • Anecdotal evidence suggests that browsers keep the properties in the order in which they are defined, evidenced by looking at the result of `JSON.stringify(yourObject)`. The properties in the JSON string are in the same order in which you defined them on the object. So it doesn't look like they sort the properties. – Brandon Apr 19 '13 at 18:21
  • @Brandon Not really : they build a structure for fast look-up *and* keep the insertion order (and all say it's not guaranteed) – Denys Séguret Apr 19 '13 at 18:22
  • @dystroy: yes, I checked that previous answer. It is 1+ year and a few browser versions ago. – markE Apr 19 '13 at 18:26
  • @markE And did you expect engines to have dropped optimizations since ? – Denys Séguret Apr 19 '13 at 18:30
  • @dystroy: be nice! No, I would expect browser improvements. The previous answer denoted that browser javascript was **not** well optimized in this regard and said that Chrome was trying to do better. – markE Apr 19 '13 at 18:33

2 Answers2

5

It depends on the browser and the JavaScript engine. Google's V8 dynamically creates hidden classes instead of dynamic lookup, to reduce the time used to access properties. Using hidden classes also has the added benefit of using class-based optimizations such as inline caching.

There is more information here under the "Fast Property Access" section. The idea basically comes from this paper: An Efficient Implementation of Self, a Dynamically-Typed Object-Oriented Language Based on Prototypes.

Internet Explorer has a "fast type system" to optimize property access. More details in this presentation.

Mozilla's SpiderMonkey engine uses a property cache (warning: the details are somewhat obsolete, but it basically still uses a property cache).

The new IonMonkey engine uses inline property-caches, but details seem to be scant so far.

Raymond Chen
  • 44,448
  • 11
  • 96
  • 135
Vivin Paliath
  • 94,126
  • 40
  • 223
  • 295
2

Yes. The specification does not require such optimications, as you have already noted, but it can be observed empirically. I tested how quickly keys are grabbed from objects that contain up to 500,000 elements. (test here, be warned that it will freeze your browser for a little while).

The key retrieval time does not increase with the size of the object, which means that it has O(1) time complexity for search.

Peter Olson
  • 139,199
  • 49
  • 202
  • 242
  • Many thanks for taking the time to create this test. I'll try your test in multiple browsers. Hopefully I'll find O(1) for all browsers! – markE Apr 19 '13 at 18:59
  • Found O(1) across all browsers I could get my hands on. Thanks, I consider that definitive. Or should I say inductive since it's comes from empirical analysis ;) – markE Apr 19 '13 at 19:11