484512 - large sharp object costs in array_join_sub

Status: RESOLVED DUPLICATE of bug 200505

(Core :: JavaScript Engine, defect)

Description

[Robert Sayre]

In the attached peacekeeper-derived benchmark, sharp object costs 10% for an array of ints.

Comment 1

[Robert Sayre]

Attachment: peacekeeper arrayCombined.js

Comment 2

[Brendan Eich [:brendan]]

Sharp arrays are not involved here since toSource is not being called. What you see is the runaway-recursion avoidance use of the same underlying memoizer. This code could be optimized, but it can't be removed. As noted just today in es-discuss, ECMA-262 underspecifies and browser-based impls must avoid runaway recursion on programs such as:

a = [0, 1];
a[2] = a;
alert(a.join());

Same goes for toString, which is like join(',').

/be

Comment 3

[Brendan Eich [:brendan]]

(In reply to comment #2)
> Sharp arrays are not involved here since toSource is not being called. What you
> see is the runaway-recursion avoidance use of the same underlying memoizer.
> This code could be optimized, but it can't be removed. As noted just today in
> es-discuss, ECMA-262 underspecifies and browser-based impls must avoid runaway
> recursion on programs such as:
> 
> a = [0, 1];
> a[2] = a;
> alert(a.join());

Er, I mean alert(a); here, since join bottoms out in toString, so it's not an interesting test case. The problem inheres in toString but comes up with join.

> Same goes for toString, which is like join(',').

This part's right, but again it's the implicit toString on each element that runs away.

/be

Comment 4

[Robert Sayre]

http://mxr.mozilla.org/mozilla-central/source/js/src/jsarray.cpp#1308

We do both JS_CHECK_RECURSION and js_EnterSharpObject regardless of op. Are both required?

js_EnterSharpObject enumerates the entire array, rather than keeping visited array objects in a hash table, as our competitors do.

Comment 5

[Robert Sayre]

deleting the sharp object bookkeeping results in a 20-25% in this test case. We would still have to catch recursion with another method if we were to preserve today's behavior, of course.

Comment 6

[Brendan Eich [:brendan]]

(In reply to comment #4)
> http://mxr.mozilla.org/mozilla-central/source/js/src/jsarray.cpp#1308
> 
> We do both JS_CHECK_RECURSION and js_EnterSharpObject regardless of op. Are
> both required?

You can read the source for JS_CHECK_RECURSION, it simply prevents crashing (OS fatal signal) due to stack overflow. It does not avoid repeatedly visiting an array linked to itself, and it does not return the expected result that all the top browsers do; rather it completes abruptly with a thrown exception.

> js_EnterSharpObject enumerates the entire array, rather than keeping visited
> array objects in a hash table, as our competitors do.

The enumeration of the array happens once and keeps visited objects in a hash table. It's not sufficient to keep only visited array objects in the hash table since you can have recursion run away through a non-array too:

a = [0, 1, 2];
o = {p: a, toString: function(){return this.p.toString()}};
a[3] = o;
alert(a);

(For either the case in comment 2, or the above testcase, Opera runs away and hits its own form of JS_CHECK_RECURSION, ending with an exception:

JavaScript - file://localhost/tmp/a2.html
Inline script thread
Abort (control stack overflow).
Script terminated.

Safari does what we do in both cases.)

As noted already, "This code could be optimized, but it can't be removed." Removing the detection puts a loose bound on the speedup. The challenge here is to avoid divergence and deliver the expected result with fast-enough recursion detection, implemented without too much code.

Since we have had sharp variables since way back, I used the same memoizer for both recursion suppression and sharp variable attribution purposes. Certainly a join benchmark will go faster with code optimized for the former purpose only, but is it worth it? Where are we now w.r.t. the competition?

/be

Comment 7

[Brendan Eich [:brendan]]

I imply in the last comment that Opera is not a "top browser". Hurm. No offense, but it is not doing what V8, SFX (Nitro!), and IIRC IE all do, which is based on what SpiderMonkey does, and I suspect is required by some web sites.

/be

Comment 8

[Robert Sayre]

(In reply to comment #6)
> (In reply to comment #4)
> > http://mxr.mozilla.org/mozilla-central/source/js/src/jsarray.cpp#1308
> > 
> > We do both JS_CHECK_RECURSION and js_EnterSharpObject regardless of op. Are
> > both required?
>
>It does not avoid repeatedly visiting an
> array linked to itself, and it does not return the expected result that all the
> top browsers do; rather it completes abruptly with a thrown exception.

OK, so both types of check are required. 

> 
> > js_EnterSharpObject enumerates the entire array, rather than keeping visited
> > array objects in a hash table, as our competitors do.
> 
> The enumeration of the array happens once and keeps visited objects in a hash
> table. 

But if you are looping over a join of an array of integers, as in this test, you pay the cost for each iteration of the loop.

// results in 15k calls to js_EnterSharpObject
for (var i = 0; i < 5000; i++) {
   arrayCombined.run();
}

> It's not sufficient to keep only visited array objects in the hash table

Hmm, see below. They use a cx (they say "exec") global hashtable.

> since you can have recursion run away through a non-array too:
> 
> a = [0, 1, 2];
> o = {p: a, toString: function(){return this.p.toString()}};
> a[3] = o;
> alert(a);
 
> Safari does what we do in both cases.

Safari's check still catches this case, by keeping a context-global hashtable of visited arrays. It doesn't require checking each element at the time of the join(). See their arrayProtoFuncJoin.

> Where are we now w.r.t. the competition?

threadsafe TM:            500ms
threadsafe TM, no sharps: 380ms
v8 shell:                 410ms
webkit trunk jsc:         170ms

This test case has other issues, like creating a JSString for each element instead of building the joined string from jschar* buffers. I have a toy patch that uses std::vector<jschar> instead of the manual chars/nchars deal, and routes around js_ValueToString for certain cases.

Comment 9

[Brendan Eich [:brendan]]

(In reply to comment #8)
> But if you are looping over a join of an array of integers, as in this test,
> you pay the cost for each iteration of the loop.

Yeah, that is true.

> // results in 15k calls to js_EnterSharpObject
> for (var i = 0; i < 5000; i++) {
>    arrayCombined.run();
> }

The run function calls join three times, so this all makes sense.

> > It's not sufficient to keep only visited array objects in the hash table
> 
> Hmm, see below. They use a cx (they say "exec") global hashtable.

I'm wrong, it is sufficient for join and toString. I was thinking of toSource.

> > Where are we now w.r.t. the competition?
> 
> threadsafe TM:            500ms
> threadsafe TM, no sharps: 380ms
> v8 shell:                 410ms
> webkit trunk jsc:         170ms

This is all probably off target for what matters most in web app performance, but hey, it's another play-along-at-home benchmark site. Let's tune for it too.

> This test case has other issues, like creating a JSString for each element
> instead of building the joined string from jschar* buffers.

You found the existing bug on this, right? IIRC crowder hacked on it a bit.

/be

Comment 10

[Brendan Eich [:brendan]]

SFX makes 15k calls to put the array in the global hashtable, right? It has to be put at the start of the join, and removed at the end. There are 15k join calls, so we can go fast by avoiding js_EnterSharpObject in this case. IIRC crowder had another bug on this point (so this bug may be a dup).

/be

Comment 11

[Brendan Eich [:brendan]]

This looks like a dup of bug 200505.

/be

Comment 12

[Robert Sayre]

(In reply to comment #10)
> SFX makes 15k calls to put the array in the global hashtable, right? It has to
> be put at the start of the join, and removed at the end.

Yes, this is what happens. The put tells whether it was already in the hashtable, in which case there is a cycle.

(In reply to comment #11)
> This looks like a dup of bug 200505.

Yeah, though that bug is short on profiling results.

Comment 13

[Brendan Eich [:brendan]]

BTW, I was not being sarcastic here:

> This is all probably off target for what matters most in web app performance,
> but hey, it's another play-along-at-home benchmark site. Let's tune for it too.

Using js_EnterSharpObject for the JOIN and TO_STRING cases is silly code sharing. We should do better. Rob, hope to see your patch in bug 200505 soon.

/be