Support lazy parsing of inner functions

Support lazy parsing of inner functions

The approach here is for the PreParser to report usage of identifiers in
expression and calls to eval() with the ParserRecorder interface, which
handily also creates the CachedData used to skip this work the next time
we encounter the same script.

BUG=v8:3195
LOG=Y

[Ian Cullinan, 2014-10-22 23:07:18]

cullinan@amazon.com changed reviewers:
+ marja@chromium.org

[Ian Cullinan, 2014-10-22 23:07:19]

Hi Marja,

Here's a proposed fix for https://code.google.com/p/v8/issues/detail?id=3195

In my testing this signifigantly reduces initial compile times for common
JavaScript libraries which are entirely composed of nested functions (like
jQuery), most signifigantly on mobile (android_arm).

I can share some performance data (timings of ScriptCompiler::CompileUnbound()
in d8 for common JavaScript libraries) if you'd like.

Thanks,
Ian C

[marja, 2014-10-24 16:59:35]

I had only a very quick look... (will have a better look next week)

How do you distinguish between the following cases:

function outer() {
  var a; // needs to be context-allocated
  function inner() {
     a = 5; // refers outer
  }
}

and

function outer() {
  var a; // doesn't need to be context allocated
  function inner() {
    var a;
    a = 5;
  }
}

?

[Ian Cullinan, 2014-10-24 17:30:57]

On 2014/10/24 16:59:35, marja wrote:
> How do you distinguish between the following cases:

I don't - the outer `a` gets context-allocated in both cases. If you think this
would cause a problem in real code, we can keep track of scopes and variable
declarations in the preparser, but of course that comes at a cost.

[Ian Cullinan, 2014-10-24 22:00:34]

FYI, I have a related CL https://codereview.chromium.org/677153004/ which
provides good test coverage for this change. It should probably land before this
one. 

Thanks again for the review.

Cheers,
Ian C

[marja, 2014-10-27 08:16:45]

marja@chromium.org changed reviewers:
+ rossberg@chromium.org

[marja, 2014-10-27 08:16:45]

rossberg@, this CL enables making inner functions lazy, but it always
context-allocates outer function variables if any inner function refers to a
variable with the same name, e.g.,

function outer() {
  var a; // will be unnecessarily context-allocated
  function inner() {
    var a;
    a = 5;
  }
}

... can you provide more insight into whether this is okay? My gut feeling says
it's not okay to add a bunch of stuff into the context unnecessarily, but my V8
fu is not good enough to say that for sure.

[rossberg, 2014-10-27 10:20:52]

On 2014/10/27 08:16:45, marja wrote:
> rossberg@, this CL enables making inner functions lazy, but it always
> context-allocates outer function variables if any inner function refers to a
> variable with the same name, e.g.,
> 
> function outer() {
>   var a; // will be unnecessarily context-allocated
>   function inner() {
>     var a;
>     a = 5;
>   }
> }
> 
> ... can you provide more insight into whether this is okay? My gut feeling
says
> it's not okay to add a bunch of stuff into the context unnecessarily, but my
V8
> fu is not good enough to say that for sure.

Definitely not okay. This could tank some functions severely, just imagine:

  function outer() {
    function inner() {
      for (var i = 0; ...) { ... }
    }
    for (var i = 0; ...) { ... }
  }

The outer loop would become much slower if i was forced into the context.
Especially in optimised code.

We would need to implement a form of preparsing with proper scope and binding
analysis to enable lazy parsing of inner functions.

[Ian Cullinan, 2014-11-06 02:27:34]

Hi marja, rossberg,

I've had a go at tracking variable declarations and bindings in the preparser
(only when preparsing inner functions). This makes lazy parsing of inner
functions slightly slower than Patch Set 1 (still much faster than eager
parsing), but avoids unnecessarily context-allocating outer function variables
and (in my testing) does not regress lazy parsing of outer functions.

PTAL, I'm looking forward to your comments.

Thanks,
Ian C

[rossberg, 2014-11-06 11:55:46]

Hm, I'm not sure I understand the change. The only place where a variable is
actually recognised as declared seems to be in ParseVariableDeclaration. But
there are various other constructs in JS that bind variables, e.g., function
declarations, parameter lists, catch, for, etc.

https://codereview.chromium.org/641283003/diff/20001/src/preparser.cc
File src/preparser.cc (right):

https://codereview.chromium.org/641283003/diff/20001/src/preparser.cc#newcode57
src/preparser.cc:57: DeclarationScope()->Declare(identifier);
Why Declare here?

[Ian Cullinan, 2014-11-12 19:26:17]

On 2014/11/06 11:55:46, rossberg wrote:
> Hm, I'm not sure I understand the change. The only place where a variable is
> actually recognised as declared seems to be in ParseVariableDeclaration. But
> there are various other constructs in JS that bind variables, e.g., function
> declarations, parameter lists, catch, for, etc.

Your understanding is better than mine :) 
I've added tracking for function declarations, parameter lists, catch, and class
plus a bunch of extra logic to support let / harmony scoping.

> https://codereview.chromium.org/641283003/diff/20001/src/preparser.cc
> File src/preparser.cc (right):
> 
>
https://codereview.chromium.org/641283003/diff/20001/src/preparser.cc#newcode57
> src/preparser.cc:57: DeclarationScope()->Declare(identifier);
> Why Declare here?

Embarrassing typo.

I'm surprised the test suite didn't catch any of these problems, so I added a
unit test that covers all the issues you've raised.

[Ian Cullinan, 2014-11-19 23:35:08]

rossberg,

PTAL at the latest patch set - I believe I've addressed all the concerns you
raised.

Thanks,
Ian

[marja, 2014-12-09 15:20:46]

Q: I wonder whether we need to / should modify the "preparse data". Would it be
better to keep it as is, so that it just contains the positions of the lazy
top-level functions and no identifiers? (I don't know the answer.)

So, the "preparse data" is put into a memory cache on Blink side, and used if we
need to parse the script again. We use it to just jump over lazy functions. I
wonder actually whether bloating it with the identifiers destroys the efficiency
benefit of it. Does it make sense to jump over a lazy inner function and read
the identifiers from the preparse data - instead of just parsing it with the
PreParser?

Any measurements which could shed light on this? The only benchmark which I know
is affected by the preparse data use is morejs on chromium side. If the preparse
data is not used, warm loads regress around 5%. I wonder what this CL does to
morejs.

[Ian Cullinan, 2014-12-09 21:57:33]

> Q: I wonder whether we need to / should modify the "preparse data". Would
> it be
> better to keep it as is, so that it just contains the positions of the lazy
> top-level functions and no identifiers? (I don't know the answer.)

Adding the identifiers to the preparse data gets us a pretty big win on warm
parsing times. I don't have access to morejs so I can't try that, but what I
have been doing is running `d8 --cache=code --trace_parse` with some popular
JavaScript files from the web and looking at how long parsing takes with and
without the preparse data, with and without my change (on my desktop, times in
milliseconds, median of five runs):

                                                before          after
                                            cold    warm    cold    warm
http://connect.facebook.net/en_US/all.js    8.2     7.9     5.1     0.7
http://[1]/analytics.js                     1.9     1.7     1.7     0.5
http://b.scorecardresearch.com/beacon.js    0.1     0.02    0.1     0.02
http://a.disquscdn.com/embed.js             1       0.04    1       0.04
http://www.google-analytics.com/ga.js       3       2.8     2.6     0.6
http://[2]/jquery/1.7.2/jquery.min.js       5.8     5.6     4.1     0.9
http://[3]/pagead/js/lidar.js               3.6     3.3     2.8     0.7
http://[3]/pagead/osd.js                    3.1     2.9     2.5     0.6
http://platform.twitter.com/widgets.js      2.5     0.25    2.5     0.25

[1] www.google-analytics.com
[2] ajax.googleapis.com/ajax/libs
[3] pagead2.googlesyndication.com

As you can see, it's the same or better in every case (0-38% speedup cold, 0-91%
speedup with the preparse data). It's a particularly large win on modern
JavaScript libraries like jQuery which make extensive use of closures to avoid
polluting the global scope.

Here's the numbers for the size of the preparse data (in bytes):

                                            before  after
http://connect.facebook.net/en_US/all.js    20      15260
http://[1]/analytics.js                     20      14500
http://b.scorecardresearch.com/beacon.js    60      76
http://a.disquscdn.com/embed.js             340     468
http://www.google-analytics.com/ga.js       20      23300
http://[2]/jquery/1.7.2/jquery.min.js       20      17820
http://[3]/pagead/js/lidar.js               20      21384
http://[3]/pagead/osd.js                    20      18744
http://platform.twitter.com/widgets.js      1120    1560

The extra preparse data is only significant in the cases where it's buying us a
large speedup.

[rossberg, 2014-12-12 14:39:28]

I really appreciate the effort you put into this, and from a first look, the
latest patch makes sense.

However, I'm fundamentally concerned about the fact that this change introduces
a second, completely different mechanism for doing variable resolution. The one
we have now is already more subtle than we'd like. Having to maintain two
different ones, and making sure that they stay in perfect sync, is probably
going to be very painful. Especially when there are no significant tests even
checking that they are in sync.

So, while I wholeheartedly agree that this would be great to have (and your
numbers are very convincing!), I'm sorry to say that I don't think we want to
land this patch in its current form. We would need to find a way to have a
sufficiently unified implementation (e.g., by factoring out the commonalities of
Scope objects as well as the VariableResolution/Allocation algorithms somehow).

[Ian Cullinan, 2015-01-09 19:39:23]

On 2014/12/12 14:39:28, rossberg wrote:
> I really appreciate the effort you put into this, and from a first look, the
> latest patch makes sense.
> 
> However, I'm fundamentally concerned about the fact that this change
introduces
> a second, completely different mechanism for doing variable resolution. The
one
> we have now is already more subtle than we'd like. Having to maintain two
> different ones, and making sure that they stay in perfect sync, is probably
> going to be very painful. Especially when there are no significant tests even
> checking that they are in sync.
> 
> So, while I wholeheartedly agree that this would be great to have (and your
> numbers are very convincing!), I'm sorry to say that I don't think we want to
> land this patch in its current form. We would need to find a way to have a
> sufficiently unified implementation (e.g., by factoring out the commonalities
of
> Scope objects as well as the VariableResolution/Allocation algorithms
somehow).

Thanks for the time you've spent looking at this. Unfortunately I haven't had
any time to work on it over xmas/new year, and it's looking like I probably
won't any time soon.

If I do make some progress with Scope/VariableResolution/Allocation should I
post an update to this CL or open a new one?

Cheers,
Ian