580355 - JM: make setelem on array holes faster

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Brian Hackett [Laid off!]]

On SS there are 267k setelem slow calls that are setting dense array holes; this out of 309k total setelem slow calls.  Estimated time for these calls on my machine is around 13ms.

Comment 1

[Brian Hackett [Laid off!]]

Attachment: OOL fast path for setting array holes

This patch adds an out of line path in SETELEM for handling holes.  For the following microbenchark:

function foo()
{
  var a = new Array();
  for (var i = 0; i < 1000000; i++)
    a[i] = 0;
}
foo();


I get these times:

V8: 55ms
JSC: 32ms
JM (old): 42ms
JM (new): 18ms

This works out to about 7ms saved in SS, which seems to be the case looking at the SS holes: 4ms saved in access-nsieve.js (12ms -> 8ms, about half the holes on SS), 1-2ms saved in crypto-aes.js and 3d-morph.js (bulk of the rest).

This checks the INDEXED_PROPERTIES flag in the scopes on Array.prototype and Object.prototype to watch for setters; this functionality does not actually work though as something is messed up in the VM.  This code (slow array) prints 'Foo!' and 'Zero!', in both interpreter and methodjit.

Array.prototype.__defineSetter__("foo", function() { print("Foo!"); });
Array.prototype.__defineSetter__(0, function() { print("Zero!"); });
var a = Array();
a.foo = 0;
a[0] = 0;

This code (dense array) prints nothing, in both interpreter and methodjit.

Array.prototype.__defineSetter__(0, function() { print("Zero!"); });
var a = Array();
a[0] = 0;

In the first example, both V8 and JSC print 'Foo!' but not 'Zero!', and in the second example neither prints anything.  If we followed this behavior the prototype checks could be ripped out of the OOL path, saving about 1ms on SS (wooooo!).

Comment 2

[David Anderson [:dvander] - inactive, e-mail if emergency]

Awesome results. 

Do we know what's going on in the VM?

Comment 3

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

(In reply to comment #1)
> I get these times:
> 
> V8: 55ms
> JSC: 32ms
> JM (old): 42ms
> JM (new): 18ms

That'll do, son.  That'll do just fine.

Comment 4

[Brendan Eich [:brendan]]

(In reply to comment #1)
> In the first example, both V8 and JSC print 'Foo!' but not 'Zero!', and in the
> second example neither prints anything.  If we followed this behavior the
> prototype checks could be ripped out of the OOL path, saving about 1ms on SS
> (wooooo!).

No (we wish!), you have to check that bit. Good news is that bug 558451 moves it into JSObject.

Stock tm tip (I believe) and with some of my patches for bug 558451 (I'm rebasing) works correctly:

js> Array.prototype.__defineSetter__("foo", function() { print("Foo!"); });
js> Array.prototype.__defineSetter__(0, function() { print("Zero!"); });
js> var a = Array();
js> a.foo = 0;
Foo!
js> a[0] = 0;
Zero!

/be

Comment 5

[Brendan Eich [:brendan]]

JSC should not cheat on an indexed proto-setter. I'll let Oliver know.

/be

Comment 6

[Brian Hackett [Laid off!]]

(In reply to comment #4)
> js> Array.prototype.__defineSetter__("foo", function() { print("Foo!"); });
> js> Array.prototype.__defineSetter__(0, function() { print("Zero!"); });
> js> var a = Array();
> js> a.foo = 0;
> Foo!
> js> a[0] = 0;
> Zero!

JM works correctly on this one too.  It's the second example (dense array case) where behavior is wrong.

Comment 7

[Brian Hackett [Laid off!]]

Attachment: fix for indexed setters

Fix for prototype-has-indexed-setter bug from comment 1.  All three monkeys handle the second example correctly now.

Comment 8

[Jeff Walden [:Waldo]]

(In reply to comment #5)
> JSC should not cheat on an indexed proto-setter.

Indeed, indexed properties do not function specially in the standard.  v8 does the same, as I recall -- I ran into this when writing tests for bug 578273 and was confused for a bit about what exactly was going on.

Comment 9

[Brendan Eich [:brendan]]

BTW, I filed https://bugs.webkit.org/show_bug.cgi?id=42801 at Olliej's behest.

/be

Comment 10

[David Anderson [:dvander] - inactive, e-mail if emergency]

Comment on attachment 459244 [details] [diff] [review]
OOL fast path for setting array holes


>+        /* Bump the array count. Don't worry about overflow. */
>+        Address arrayCount(baseReg, offsetof(JSObject,
>+                                             fslots[JSObject::JSSLOT_DENSE_ARRAY_COUNT]));
>+        stubcc.masm.loadData32(arrayCount, T1);
>+        stubcc.masm.add32(Imm32(1), T1);
>+        stubcc.masm.storeData32(T1, arrayCount);

This slot is gone now, thankfully.

>+
>+        /* Update the array length and minlencap if needed. Don't worry about overflow. */
>+        Address arrayLength(baseReg, offsetof(JSObject, fslots[JSObject::JSSLOT_ARRAY_LENGTH]));
>+        Address arrayMinlencap(baseReg, offsetof(JSObject,
>+                                                 fslots[JSObject::JSSLOT_DENSE_ARRAY_MINLENCAP]));

MINLENCAP is gone too.

r=me, though looks like you'll have to rebase before pushing.

Comment 11

[Brian Hackett [Laid off!]]

Attachment: rebased sethole patch

Rebase to current jaegermonkey, remove COUNT/MINLENCAP updates, incorporate fix for writing dense array elements with indexed setters in prototypes.

Comment 12

[David Anderson [:dvander] - inactive, e-mail if emergency]

http://hg.mozilla.org/users/danderson_mozilla.com/moo/rev/3d3f7234b94e

looks like a 5ms win on SS, all in nsieve. nice. other small wins in crypto-aes, 3d-morph but maybe noise.

Comment 13

[Brendan Eich [:brendan]]

Comment on attachment 460936 [details] [diff] [review]
rebased sethole patch

>+FrameState::tempRegForData(FrameEntry *fe, RegisterID reg, Assembler &masm) const
>+{
>+    JS_ASSERT(!fe->data.isConstant());
>+
>+    if (fe->isCopy())
>+        fe = fe->copyOf();
>+
>+    if (fe->data.inRegister()) {
>+        JS_ASSERT(fe->data.reg() != reg);
>+        return fe->data.reg();
>+    } else {

Style nit, fix anytime: else after return.

/be