793964 - 30% regression on dromaeo getElementById test due to string uninlining malloc-fest

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, defect)

Description

[Boris Zbarsky [:bzbarsky]]

STEPS TO REPRODUCE:

1)  Load http://dromaeo.com/?dom-query&numTests=1
2)  Run the test.
3)  Look at the first (getElementById) score.
4)  Compare to Firefox 15.

EXPECTED RESULTS: Not slower.

ACTUAL RESULTS: 30% slower.

Regression range on nightlies: http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=1e56d3016820&tochange=48c4938eaf57

A profile says a huge amount of time is spent uninlining strings under JS_GetStringCharsZAndLength (which xpconnect calls to get a jschar* and length out of the JS string to call into C++ code with).

The combination points at 785551.  The comments in that bug seem to say that this uninlining should be rare, but it's happening a _lot_ in this case...

Comment 1

[Terrence Cole [:terrence]]

Attachment: testcase

This is a standalone testcase demonstrating the bug.

The problem is that it is no longer safe to hand out a raw jschar* that points into the middle of a GC thing: when we move the GC thing, the jschar* will be left dangling.  Bug 793964 solves this problem by moving any inlined chars into out-of-line memory when we hand a raw jschar* back to the browser.  This regression is caused by the extra mallocs in this test.

To see if this is a problem for browsing in general, or just dromaeo, I instrumented the JS_GetStringChars family of functions and ran membuster.  Over the course of the test we called the JS_GetStringChars functions 4,904,151 times.  Of those calls, 117,752 needed to malloc new chars.  This gives us an uninlining rate of ~2.4% on real sites.

Given the above, I think it is reasonable to say that this is a bug in dromaeo, not in Firefox.

Comment 2

[Boris Zbarsky [:bzbarsky]]

Hm.  So why is dromaeo hitting it?  Just because it happens to use particularly short id strings there?

Comment 3

[Terrence Cole [:terrence]]

(In reply to Boris Zbarsky (:bz) from comment #2)
> Hm.  So why is dromaeo hitting it?  Just because it happens to use
> particularly short id strings there?

You are correct.  The strings it uses in this case are 7 characters long, which fits nicely in a JSShortString.  We are (correctly) creating a new JSShortString each time we do js_ConcatString for the |+| in the regressing test case.  I did not check, but I suspect that the cases that do not regress are getting atomized somehow.  This would allow us to uninline the canonical representation once and not have to do so on each iteration.

This is speculation on my part, but I think we are saved from hitting this on the web by a few things:
  >>> |id| needs to be manually namespaced.  Many id's are going to look like |leftpane-button-topleft-corner-dropshadow|.  Even css pidgin like |lpane-bot-tl-shadow| is going to overflow a JSShortString on 32bit.
  >>> There are no good tools [that I know of] to compress html that also work in the presence of javascript.
  >>> Most DOM manipulation is done by jquery these days.  Ropes will not flatten inline if they contain a non-extensible strings and nsString appears to require a \0, making them non-extensible.  Thus, as soon as you get any semi-complex string manipulation that involves DOM, ShortStrings are going to start dropping out of the picture.

Comment 4

[Boris Zbarsky [:bzbarsky]]

I assume it doesn't make sense to come up with some scheme for blacklisting concats from  a given opcode from creating an inline string if we detect that they keep getting uninlined soon after?

XPCOM strings do not in fact, in general, require a \0.  I'm not quite sure why the DOM binding code uses JS_GetStringCharsZAndLength instead of JS_GetStringCharsAndLength.  Looks like Luke changed it from JS_GetStringChars at some point...

On the other hand, we'd still need to uninline with JS_GetStringCharsAndLength, right?

I really wish we could solve our Spidermonkey-Gecko string impedance mismatches.  :(

Comment 5

[Terrence Cole [:terrence]]

(In reply to Boris Zbarsky (:bz) from comment #4)
> I assume it doesn't make sense to come up with some scheme for blacklisting
> concats from  a given opcode from creating an inline string if we detect
> that they keep getting uninlined soon after?

It could probably be done, but it would be a pretty severe complexity cost for the amount of win.  It doesn't really feel like the sort of thing that is likely to make the web better, but maybe I'm underestimating the impact of dromaeo.

> XPCOM strings do not in fact, in general, require a \0.  I'm not quite sure
> why the DOM binding code uses JS_GetStringCharsZAndLength instead of
> JS_GetStringCharsAndLength.  Looks like Luke changed it from
> JS_GetStringChars at some point...
> 
> On the other hand, we'd still need to uninline with
> JS_GetStringCharsAndLength, right?

Correct.

> I really wish we could solve our Spidermonkey-Gecko string impedance
> mismatches.  :(

Just so!

In SpiderMonkey I am working on a three pronged solution to the underlying problem:

  1) Chars access to anything not a JSStableString returns a JSString::CharPtr.  CharPtr subclasses RangedPtr<const jschar *> and adds an RAII assertion that no GC's can occur while the CharPtr is live.  Thus, the raw chars cannot be invalidated while available.

  2) Any section of code that needs to do real work (e.g. the frontend and regexp engines) uninlines by creating a JSStableString with ensureStable.  The section of code using the jschar* can GC without invalidating the pointer because it is in the C Heap now.  I lumped the entire browser into this category, which seems to have been premature. :-)

  3) [It turned out we didn't need this internally, but it is still an option if needed in the browser.]  Instead of returning a raw jschar*, return a class which contains a Handle<JSString*> and an offset.  All |operator*| or |operator[]| on the wrapper class do the double indirection to find the right value regardless of where we relocate the underlying JSString.  We did not go with this approach internally because we can't take the speed hit for sections using (2) and it isn't needed since we can use (1) everywhere else.

I have no idea if (1) would be appropriate for the DOM search under getElementById: can it re-enter JS or trigger GC more directly?  I also have no idea how much work it would be to wrap (3) in an nsString: is this even feasible?

Comment 6

[Luke Wagner [:luke]]

For really hot paths that really matter (and don't GC while holding a pointer to jschars), we could add jsfriendapi GetUnstableChars or something...

Comment 7

[Boris Zbarsky [:bzbarsky]]

> but it would be a pretty severe complexity cost for the amount of win.

OK, that's what I was expecting.  Makes sense.

(1) would sort of work for getElementById, kinda. It's a simple hashtable lookup, but after that's done we might GC.  We would not GC until we're done with the string.  Restructuring the binding code to deal with that would be a bit of a pain, and this isn't true for other DOM methods, obviously.

(3) is not really wrappable in an nsAString; an nsAString really needs a 16-bit code unit pointer.

I would be fine with just wontfixing this for now, I guess, given the very limited impact...

Comment 8

[Terrence Cole [:terrence]]

(In reply to Boris Zbarsky (:bz) from comment #7)
> (1) would sort of work for getElementById, kinda. It's a simple hashtable
> lookup, but after that's done we might GC.  We would not GC until we're done
> with the string.  Restructuring the binding code to deal with that would be
> a bit of a pain, and this isn't true for other DOM methods, obviously.

It would be truly preferable to be able to wrap the full live range of the unstable pointer in an AutoAssertNoGC, but if we need it, a hefty comment would probably be acceptable.  I've got a patch in the works to return an Unrooted value.  I will apply it here first and see if we can't solve this.

Comment 9

[Terrence Cole [:terrence]]

I took this as an opportunity to have a look at the new dom bindings generator.  I was hoping it would be easy to insert some new unwrapping in the generated bits, but it looks like the unwrapper that gets generated is fully specified by the IDL type.  Boris says this will be much easier to do when everything is moved over to webidl.

Thus, we decided to wontfix this for now, given the limited real-world impact.

Comment 10

[bhavana bajaj [:bajaj]]

Marking the status-firefox18 "wontfix" based on comment 9