Overhead of AST visit

[Andy Wingo]

Hi,

I am working on destructuring binding. As we discussed, destructuring
may eventually cause expressions to be lifted from one function to
another, which requires adjustment of some state that is currently
computed when an expression is parsed. See:

https://docs.google.com/document/d/1iJWvuakeKsPJOeA-RJ-4bM3Jha5iewQjxKsylgzHEB0/edit#heading=h.42erxzmynv6r

The proposed first step in that series is to add a post-pass to the
parser, and to move some of the parser's work there. We were concerned,
though, about the overhead of a post-pass.

So as a first step I am trying to estimate the overhead of a full AST
traversal that doesn't do anything, as a way to estimate the maximum
potential overhead of this change.

The test case is a copy of https://code.jquery.com/jquery-2.1.1.min.js,
copied ten times in a row, and contained within a function f() { }. You
can find this file here:

http://wingolog.org/pub/jquery-parsing-test.js

Normally this would be only pre-parsed, but with --no-lazy we can force
the parser to run on it. (These tests include the patch from
https://codereview.chromium.org/649623002/.) The test file is 842595
bytes, and is minified.

The methodology here is to run d8 over that test file before and after
the change, and to compare instruction counts, assuming that instruction
counts are indicative of time, power, and latency. (This may not be
true because the post-pass is a bunch of indirect calls.)

The change: I added a new custom do-nothing AstVisitor to parser.cc.,
and wire it up to be called in the appropriate places
(Parser::DoParseProgram and Parser::ParseLazy). The visitor touches
all nodes in the result. Thus the overhead is a maximum overhead; it
will probably be somewhat less when the parser's work (e.g. bailout ID
generation) is moved there.

So here are the instruction count differences, counted by callgrind. I
ran it a few times; the numbers were mostly stable, but still I chose
the lowest one.

Before After
--lazy instructions 152,259,039 152,275,811
--no-lazy instructions 479,554,626 487,574,842

I measured the parse time for the script as well, using the following
command line and taking the lowest result:

for i in `seq 0 100`; do out/x64.release/d8 --trace_parse jquery-parser-test.js; done | grep parser-test | sort | head -10

Before After
--lazy script parse ms 16.934 16.924
--no-lazy script parse ms 47.028 53.442

Note that the --no-lazy time effectively compiles all nested functions,
I think, so it includes compilation time as well. This is fair enough
as whenever we parse an AST, we're going to compile too.

Conclusions, for this test case:

- The impact on lazy-parsed functions is unaffected, as you would
guess.

- With this added post-pass, the --no-lazy instruction count is 1.67%
higher, and the script parse time is 13.7% higher.

I believe these numbers to be upper bounds on the impact of adding a
post-pass to the parser. These tests were made on a i7-3770 system.

I'm somewhat surprised about the script parsing time impact. The times
do appear to be consistent, though.

I do not know what the impact would be of moving state computation out
of the parser and into a post-pass. I suspect it would lower the
overhead of the "after" configuration, as the parser wouldn't have to
keep so much state, and you'd get a better mix of computation and
pointer chasing, but it is hard to tell. 13.7% is a lot.

What do you think?

Andy

ps. Patch attached for the empty post-pass.