936103 - IonMonkey: Optimize GETELEM on objects used as hashmaps

Status: NEW

(Core :: JavaScript Engine: JIT, defect, P5)

Description

[Jan de Mooij [:jandem]]

The TypeScript compiler (bug 935929) uses various objects as hashmaps.

Our ICs (and JITs) have never been good at optimizing this: we quickly reach the maximum number of stubs and then we give up and every access becomes a slow VM call. Either IonBuilder or the GetElement IC should be able to determine when a GETELEM is used to access a hashmap/dictionary object and do something more efficient.

We could do a callWithABI that does the whole lookup thing or maybe we can even add an IonCode stub to do a ShapeTable lookup from JIT code.

The testcase below is 3x slower than with v8.

function f(o) {
    var keys = Object.keys(o);
    var t = new Date;
    for (var i=0; i<225280; i++) {
	var k = keys[i % 128];
	var res = o[k];
    }
    print(new Date - t);
    return res;
}
var o = {};
for (var i=0; i<100; i++)
    o["a" + i] = i;
f(o);

Comment 1

[Tom S [:evilpie]]

Is that % 128 right? A lot of lookups are for "undefined".

Comment 2

[Tom S [:evilpie]]

Attachment: WIP for baseline

I implemented enough of the stub to get this working. (Missing a lot required checks, but seems to work correctly in this testcase). I changed it to keys[i % keys.length], to avoid hitting non existing properties all the time, optimizing that will be harder. Only running it in baseline the time moves from 52 to 17.

I also just look at the first match in the ShapeTable and not at any collusion. we could also do a linear search if there is no shape-table. This only really works on x64, because of registers size (for the hash) and x86 doesn't have enough registers to do it like this.

Comment 3

[Jan de Mooij [:jandem]]

(In reply to Tom Schuster [:evilpie] from comment #1)
> Is that % 128 right? A lot of lookups are for "undefined".

That was on purpose, TypeScript also hits this case a lot, to test if a value is in the hashmap :(

Comment 4

[Tom S [:evilpie]]

I just realized that we need to check that the atom returns false for ->isIndex(). (We might be able to cheat and just test if the first char is not 0-9).
The other plan is to add a new flag to the BaseShape like NON_NATIVE, which guards that it's a native object without a getprop hook, in which case this optimization is valid. Adding the linear search path was trivial.

Jan thinks that only 55% percent of all property lookups in typescript even succeed, so adding getprop that guards that the property is not found might be necessary, however that probably involves some more work (e.g. resolve hook and walking of the prototype chain).

Comment 5

[Tom S [:evilpie]]

Attachment: wip v2, passes jit tests

Comment 6

[Guilherme Lima]

Something made the testcase faster. Firefox 34 (beta) takes 45ms and Chrome 38 takes close to that (it varies a lot, from 35ms to 60ms).

I modified the 2nd loop from 100 to 10 "for (var i=0; i<10; i++)". Firefox took 130ms and Chrome 105ms.
Changing it to 1000, Chrome took 8ms, and Firefox 28ms.

Comment 7

[Jon Coppeard (:jonco)]

Is this patch still needed?

Comment 8

[Tom S [:evilpie]]

I think this is sort of similar to what Jan experimented with megamorphic getprops in Ion Bug 1107515. I don't think we should use this, because the JIT code is really huge.

Comment 9

[Jan de Mooij [:jandem]]

Megamorphic ICs made this a lot faster.

Comment 10

[Guilherme Lima]

Chrome improved a lot as well and is 3x faster than Firefox, at least for me on Win10.