bugzilla.mozilla.org has resumed normal operation. Attachments prior to 2014 will be unavailable for a few days. This is tracked in Bug 1475801.
Please report any other irregularities here.

Consider speeding up Angular's array of functions stringifying code

RESOLVED DUPLICATE of bug 1383343

Status

()

Core
JavaScript Engine
RESOLVED DUPLICATE of bug 1383343
a year ago
a year ago

People

(Reporter: Ehsan, Unassigned)

Tracking

(Blocks: 1 bug)

Firefox Tracking Flags

(Not tracked)

Details

(Reporter)

Description

a year ago
See this profile: http://bit.ly/2tq5yKU

Code: https://searchfox.org/mozilla-central/rev/17ebac68112bd635b458e831670c1e506ebc17ad/js/src/jsfun.cpp#1013

Perhaps there are optimization opportunities here.

Spoke about this with Jan on IRC.
Maybe a JSFunction* to JSString* cache could work. We should add some logging to see how many (different) functions we're talking about exactly...
Flags: needinfo?(jdemooij)
I looked into this a bit and there's a lot of plain silliness in this code. Like we create a JSString* containing the substring of the source code we're interested in (we copy/malloc the chars), then we append this string to a StringBuffer. We should just append the source chars directly and eliminate a string allocation + copy.

AngularJS doesn't call FunctionToString many times but the functions are pretty large (> 500 lines of code IIRC). A cache based on the JSScript* would probably work.
Depends on: 1377489
I looked at this a few weeks ago and a JSScript*/JSFunction* -> JSString* cache should handle most cases. Also nice for memory usage because Angular is stringifying some huge functions. I'll try something later today - I also want to see how this behaves on actual websites.
What is anuglar using Function.toString() so much for?
(Reporter)

Comment 5

a year ago
I *think* it comes from this code:

https://github.com/WebKit/webkit/blob/a94041673884d836778f3fb028d3cc87328ddbe3/PerformanceTests/Speedometer/resources/todomvc/architecture-examples/angularjs/node_modules/angular/angular.js#L8033

where directive.controllers is an array of functions, and the comparison results in a call to Array.toString(), which maps to Array.join() which calls toString() on each element in the array which is a function.  (Note how in the profile this is all coming from a call to LooselyEqual).

Now, in my naive thinking, inside LooselyEqual around steps 10 and 11 <https://searchfox.org/mozilla-central/rev/3a3af33f513071ea829debdfbc628caebcdf6996/js/src/vm/Interpreter.cpp#879>, if one of the comparison sides weren't primitives, perhaps we could remember that the other side was, and in case we encounter something like an array on the other side, maybe we can see if the first element would be sufficient to tell whether the comparison result would be inequal?
(In reply to :Ehsan Akhgari (needinfo please, extremely long backlog) from comment #5)
> Now, in my naive thinking, inside LooselyEqual around steps 10 and 11
> <https://searchfox.org/mozilla-central/rev/
> 3a3af33f513071ea829debdfbc628caebcdf6996/js/src/vm/Interpreter.cpp#879>, if
> one of the comparison sides weren't primitives, perhaps we could remember
> that the other side was, and in case we encounter something like an array on
> the other side, maybe we can see if the first element would be sufficient to
> tell whether the comparison result would be inequal?

It's very difficult due to potential side-effects. For |"foo" == array| there are at least the following cases to consider:

* A getter on the object itself or on the prototype might have side-effects.
* A proxy on the prototype might intercept things.
* Array.prototype.toString might have been deleted/overridden.
* Same for Array.prototype.join (called by Array.prototype.toString).
* One of the elements might have a custom toString/valueOf method.
* The array may contain a symbol and stringifying will throw.

In theory we could guard against each of these, but it's very hard to get right and to justify the complexity.
Depends on: 1383775
Depends on: 1383343
I think there might be a simpler/cleaner approach.

I don't see the value in optimizing Function.toString().  It's just not something that programs do explicitly.  In this case, it's occurring as a side-effect of JS behaviour for comparing an array object with a string.

Comparing values to strings, however.. happens a lot in code.  And in polymorphic JS, those values can easily be arrays.  I would venture additionally that there exist very few instances where a JS dev does |a == "str"| with the explicit expectation that |a| is an array and relying on the join-with-comma behaviour of Array.toString().

I'd expect that most of the time we see an array show up in a comparison with a string, it's because the code is polymorphic, and the comparison is there for one of the other variants where the value being compared is NOT an array.

We should be able to handle the compare-array-with-string case directly, on the expectation that the vast majority of the time, the expected result of that compare is false.

Here's a proposal.

The comparison in this case is of the form |array_object == string_literal|.  We know the LHS is going to get stringified.  We also know that arrays stringify with |join()| and that |join()| with no args assumes "," as a separator.

This means that as long as |toString()| on the array doesn't throw, then:

1. Arrays of length 0 yield ''
2. Arrays of length 1 stringify their element 0.
3. Arrays of length >1 are guaranteed to yield a string containing a ','

toString on an Array will only throw if join() throws.  join() will only throw if one of the array element's toString() throws.  Function.toString() should never throw.

If the RHS string literal doesn't contain a ',', and the LHS array is of length >1, then all we need to do is confirm that all of the array elements have side-effect-free, non-throwing stringifying behaviour.  If we can do that, we can shortcut to 'false'.

Jan, what do you think?
(In reply to Kannan Vijayan [:djvj] from comment #7)
> If the RHS string literal doesn't contain a ',', and the LHS array is of
> length >1, then all we need to do is confirm that all of the array elements
> have side-effect-free, non-throwing stringifying behaviour.  If we can do
> that, we can shortcut to 'false'.

So we'd need to test at least the following conditions:
- array[Symbol.toPrimitive] isn't present
- array.toString === Array.prototype.toString
- array.join === Array.prototype.join
- (And probably a dense array resp. no getters or inherited indexed properties check.)

And for each array element:
- element[Symbol.toPrimitive] isn't present
- element.toString is present
- element.toString has the expected side-effect-free stringifying behaviour
That sounds roughly correct.  Can you spot any flaws in my reasoning, Andre?
(In reply to Kannan Vijayan [:djvj] from comment #7)
> I don't see the value in optimizing Function.toString().  It's just not
> something that programs do explicitly.

I'm not convinced this is true: frameworks stringify functions to do runtime reflection of arguments, for example. In fact, Angular does exactly that: https://github.com/angular/angular.js/blob/master/src/auto/injector.js#L73-L81

I'm also not fully convinced that there is all that much value in just checking for "," in the string as you describe: it seems quite likely that that'd just be in the string for whatever reason fairly often.

Could we perhaps stringify elements in the array lazily, assuming that the preconditions from comment 8 hold? The hope would be that we'd get a mismatch either in length (if the result of stringifying just some of the elements exceeds the string's length) or in contents before stringifying all elements.

That does seem more involved, but once we have checked for all the preconditions, maybe it's not too much additional complexity?
(In reply to Kannan Vijayan [:djvj] from comment #7)
> The comparison in this case is of the form |array_object == string_literal|.
> We know the LHS is going to get stringified.  We also know that arrays
> stringify with |join()| and that |join()| with no args assumes "," as a
> separator.

Do we know that the LHS in the AngularJS case is always an array object? If it's any object/value, having a dynamic ArrayObject::class check could regress other cases where user code checks for |someObject == stringLiteral|, like for example this old YUI3 code https://github.com/yui/yui3/blob/25264e3629b1c07fb779d203c4a25c0879ec862c/src/date/js/date-math.js#L20.


FWIW AngularJS 1.5.3 no longer has that issue (https://github.com/angular/angular.js/issues/14268, https://github.com/angular/angular.js/pull/14271).
I think optimizing this will be complicated - a lot of conditions we would need to check for, and to me checking for this case specifically borders on benchmark gaming (unless we can show it helps real websites out there).

I think we should first dig into the profile and optimize any bits we can optimize, since that will help other code that takes the same code paths (without going through, say, LooselyEqual).

Regarding Function.prototype.toString, see bug 1383343 comment 7. Websites stringify huge functions all the time.
OK so this line:

  if (controller == '@') {

Is executed 303 times when I run all AngularJS tests once. In 202 cases, controller is an array (of length 11), which is much less than I expected. Changing this line to use === or to check !Array.isArray(controller) does not make us a lot faster, so I wonder if this bug is still an issue after bug 1383343.

Ehsan maybe you want to profile this again?
My proposal was based on the kind of code that I've noticed in the early jquery days.  Heavily overloaded function arguments where the type of one argument is highly polymorphic (string or array or object or function), and acts as a selector.

Still, it seems like it may not be as worthwhile as I originally thought.  Thanks for the feedback.
(Reporter)

Comment 15

a year ago
Thanks Jan, this is completely fixed now by bug 1383343.  After that bug, fun_toString() hardly shows up in the profile any more: https://perfht.ml/2eSoDzC
Status: NEW → RESOLVED
Last Resolved: a year ago
Flags: needinfo?(jdemooij)
Resolution: --- → DUPLICATE
Duplicate of bug: 1383343
You need to log in before you can comment on or make changes to this bug.