1162665 - ES6 Map performance for large numbers of elements is deficient

Status: NEW

(Core :: JavaScript: GC, defect)

Description

[Katelyn Gadd (:kael)]

Attachment: Test case (containertest.js)

While investigating a performance issue with Map in v8, I discovered that its performance in SpiderMonkey is relatively deficient in my test case as well.

The test case compares using a JS Object as a dictionary vs a Map and measures the cost of adding a large number of key-value pairs (~12 million) to each container type.

The performance of Object is good in both engines and relatively stable. In SpiderMonkey, the performance of Map is relatively stable, but the overall run time is something like 10x worse than Object. It appears that a good portion of the time lost here is due to GC pauses - so it seems Map is creating an extreme amount of GC pressure when compared to Object or simply increasing the cost of doing the collections.

This test is not entirely like-for-like because the Object's keys are ints and the Map's keys are objects. (My real-world scenario is using arbitrary object instances as keys, so these are the two implementations I have to choose from.)

This kinda sucks since Map is the only way to key things on arbitrary values unless you're willing to cram numbered properties onto objects and change all your code to handle it.

Timing data follows. Test case attached (you can run the .js file in the spidermonkey shell, or the .html file in Firefox.)

I think it's probably important to mitigate the GC issues here for large-scale JS apps (if possible), and it would be great if the overall performance profile could be closer to Object.

---- firefox nightly 40.0a1 (2015-05-07) ----

No triggered garbage collection available; this may negatively impact results.

// Object.create(null)
0: 4ms
350000: 5ms
700000: 6ms
1050000: 3ms
1400000: 2ms
1750000: 10ms
2100000: 2ms
2450000: 2ms
2800000: 13ms
3150000: 3ms
3500000: 2ms
3850000: 17ms
4200000: 3ms
4550000: 2ms
4900000: 19ms
5250000: 2ms
5600000: 2ms
5950000: 23ms
6300000: 2ms
6650000: 2ms
7000000: 27ms
7350000: 2ms
7700000: 2ms
8050000: 30ms
8400000: 2ms
8750000: 2ms
9100000: 34ms
9450000: 2ms
9800000: 2ms
10150000: 2ms
10500000: 2ms
10850000: 2ms
11200000: 41ms
11550000: 2ms
11900000: 1ms
js object: 288ms

// new Map()
0: 50ms
350000: 58ms
700000: 48ms
1050000: 978ms
1400000: 57ms
1750000: 54ms
2100000: 58ms
2450000: 1158ms
2800000: 65ms
3150000: 63ms
3500000: 71ms
3850000: 71ms
4200000: 74ms
4550000: 78ms
4900000: 80ms
5250000: 1383ms
5600000: 64ms
5950000: 66ms
6300000: 79ms
6650000: 75ms
7000000: 72ms
7350000: 71ms
7700000: 70ms
8050000: 74ms
8400000: 76ms
8750000: 74ms
9100000: 82ms
9450000: 86ms
9800000: 90ms
10150000: 93ms
10500000: 91ms
10850000: 1921ms
11200000: 72ms
11550000: 63ms
11900000: 18ms
js Map: 7589ms

Comment 1

[Katelyn Gadd (:kael)]

Attachment: Browser test harness for containertest.js

Comment 2

[Boris Zbarsky [:bzbarsky]]

So I see two things going on here, in a profile.

First of all, lots of time spent in the put() on the hashtable.  It's all self time (except for the rehash) bits.  I'm _guessing_ it's something to do with barriers if we resize the hashtable, but not sure.

The second thing is marking.  This is almost entirely self time in js::GCMarker::processMarkStackTop, though there is some time under MapObject::mark as well.

> This test is not entirely like-for-like because the Object's keys are ints and the
> Map's keys are objects.

And the values are ints in both cases, yes?  So the Map case simply has a lot more marking to do...

That said, making this more of an apples to apples comparison by making the Map use the integers as keys doesn't seem to change things much.

Comment 3

[Terrence Cole [:terrence]]

Moving ni? to Jon.

Comment 4

[Jon Coppeard (:jonco)]

I experimented with a couple of GC-related approaches:

 - Making Map/Set use unique IDs for objects made the code much simpler but the benchmark results twice as slow.

 - Maintaining a list of nursery keys on the Map/Set object rather than adding a generic store buffer entry for each key made no different to the results.  This approach would probably help a different usage pattern where the objects were created on the fly though, so that may be worth pursuing elsewhere.

Marking is slow because it's map containing 12000000 entries.  I tried prodding the compiler to inline more of the marking path but it made no difference.

I think a big factor is that we have to call into C++ from the JIT for ever set operation on the map, whereas operations on objects are heavily optimised.

Comment 5

[Xidorn Quan [:xidorn] UTC+10]

A data point is that it seems on V8, Map accessing is much faster than object accessing based on https://jsperf.com/javascript-objects-vs-map-performance

From my local test, while we have a better performance on object accessing, our Map accessing is up to 13x slower than V8 on the benchmark above, which is a big gap.

Since Map has a much better performance on Chrome, it can be expected that people may start preferring Map over object in many cases, and that could affect our user experience.

Comment 6

[ragzovskii]

Hello.
I note that Map performance in latest stable FF is still less than on regular Object. Please refer to this test: https://jsperf.com/es6-map-vs-object-properties/2