When overwriting native `Map`, use one internally for O(1) lookups

[ljharb]

Even when overwriting native Map that doesn't comply with the spec, we should use the native Map internally rather than our O(n) slow path for object keys.

[cscott]

Quite possibly. Right now we test a variety of things, and if any of them are not spec-compliant, we fall back to our own from-scratch implementation.

Maps (and Sets) are common enough that we perhaps should add a middle-ground type of fallback, where we substantially use the native implementation but only override a few things.

But profiling seems to indicate that's not actually the problem/common case with our current Map implementation. Instead, the slow thing seems to be the defineProperties calls on each instance. If we restructure to inherit property definitions from a prototype object (since assignment preserved enumerability we can still assign to our child object) we could potentially see a substantial speedup.

Not sure that optimizing the "object key" case is really the thing that needs doing. Few people are using non-string/non-numeric keys as far as I can tell.

But in any case, we should take care so as not to explode the set of possible configurations we need to test.

[ljharb]

The shim's primary goal is correctness, but performance is next, so I'd love to get both whenever possible.

I'd love to see PRs that made any "clobber the broken native implementation" code more performant.

[zloirock]

If you interesting, how works collection polyfilling in core-js:

• If collection not convert -0 key to +0 - wrap collections methods
• If collection not support chaining - wrap set or add
• If collection can't be init from iterable or not support iterator closing - wrap constructor
• If collection hasn't [Symbol.iterator] - set method
• Only with other problems - replace collection fully

In most case we have fully spec-complying native collection.

If you wanna fake subclassing - you can also add subclassing-friendly wrapper to this logic ;) I don't think adding not spec-complying feature is a good idea, considering your position about size in environment w/o descriptors.

[ljharb]

@zloirock what do you do for browsers like Safari 8 which has entries/keys/values methods that work in for..of but not as independent iterators?

What do you do in engines that don't have a native Map at all? (Note that mutating objects to add an ID is a far worse violation of the spec than O(n))

[zloirock]

@ljharb

what do you do for browsers like Safari 8 which has entries/keys/values methods that work in for..of but not as independent iterators?

Additional buggy iterators check - fully replace collection. Possible emulate iterators by using forEach (used it before), but it creates some problems and slow.

mutating objects to add an ID is a far worse violation of the spec than O(n))

Strongly disagree.

What do you do in engines that don't have a native Map at all

Entries chain and O(1) index for all keys except frozen objects.

[ljharb]

Mutation is clearly a violation of the spec. You can certainly make your own decision about which violation is worse or better, but I'd be surprised if many developers expected mutation more than they expected slowness.

[zloirock]

That's your opinion, I will not persuade you. I just suggest ways to fix native collections without complete replacement.

[ljharb]

With #328, there's still some browsers on the Map/Set` spectrum between IE 9 and latest Chrome that do have native collections, but have been totally clobbered - but that PR should preserve much or all of the native implementation.

I've also corrected the subclassing tests that were incorrectly using Map.call(this) - basically, to subclass Map and Set, Object.setPrototypeOf must be supported or shimmable.

[ljharb]

There's still a few browers (Safari 8 in particular) where we're clobbering the entire implementation, so we still need to look into that here.

@zloirock Thanks for your persistence! Despite that we disagree on priorities of performance versus non-performance-correctness, your suggestions have helped me to improve the former without sacrificing the latter, so it's much appreciated.

[medikoo]

If I read the spec correctly, it describes key search with O(n) algorithm. Of course I don't mean that it should be followed, but my question is: On which basis it is assumed that native implementations internally do O(1)? Is it observed from benchmarks, read from their source code, or is it just no-brainer assumption, taking that they may have some kind of id references to objects in C layer?

[zloirock]

@medikoo

Map object must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection.

[medikoo]

@zloirock great thanks, that answers perfectly. I misread the spec then.

[ljharb]

The reality is that prior to native ES6, there is no "other mechanism" available. The spec doesn't mention mutating in http://www.ecma-international.org/ecma-262/6.0/#sec-map.prototype.set, which means that that must never be any mutation of key or value.

Any way to implement O(1) without mutation or native Maps is welcome, but I've not seen it yet.