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.
-- -- v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev --- You received this message because you are subscribed to the Google Groups "v8-dev" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
commit 14b8e45dae3528cfe9ce9c36d4a761aba62507fa Author: Andy Wingo <[email protected]> Date: Fri Oct 10 12:49:02 2014 +0200 tmp diff --git a/src/parser.cc b/src/parser.cc index a972a62..6001d62 100644 --- a/src/parser.cc +++ b/src/parser.cc @@ -23,6 +23,338 @@ namespace v8 { namespace internal { + +class AstNumberingVisitor FINAL : public AstVisitor { + public: + explicit AstNumberingVisitor(Zone* zone) : AstVisitor() { + InitializeAstVisitor(zone); + } + + private: + // AST node visit functions. +#define DECLARE_VISIT(type) virtual void Visit##type(type* node); + AST_NODE_LIST(DECLARE_VISIT) +#undef DECLARE_VISIT + + void VisitStatements(ZoneList<Statement*>* statements); + void VisitDeclarations(ZoneList<Declaration*>* declarations); + void VisitArguments(ZoneList<Expression*>* arguments); + void VisitObjectLiteralProperty(ObjectLiteralProperty* property); + + DEFINE_AST_VISITOR_SUBCLASS_MEMBERS(); + DISALLOW_COPY_AND_ASSIGN(AstNumberingVisitor); +}; + + +void AstNumberingVisitor::VisitBlock(Block* node) { + VisitStatements(node->statements()); +} + + +void AstNumberingVisitor::VisitVariableDeclaration(VariableDeclaration* node) { +} + + +void AstNumberingVisitor::VisitFunctionDeclaration(FunctionDeclaration* node) { + VisitFunctionLiteral(node->fun()); +} + + +void AstNumberingVisitor::VisitModuleDeclaration(ModuleDeclaration* node) { + Visit(node->module()); +} + + +void AstNumberingVisitor::VisitImportDeclaration(ImportDeclaration* node) { + Visit(node->module()); +} + + +void AstNumberingVisitor::VisitExportDeclaration(ExportDeclaration* node) { +} + + +void AstNumberingVisitor::VisitModuleLiteral(ModuleLiteral* node) { + VisitBlock(node->body()); +} + + +void AstNumberingVisitor::VisitModuleVariable(ModuleVariable* node) { + Visit(node->proxy()); +} + + +void AstNumberingVisitor::VisitModulePath(ModulePath* node) { + Visit(node->module()); +} + + +void AstNumberingVisitor::VisitModuleUrl(ModuleUrl* node) { +} + + +void AstNumberingVisitor::VisitModuleStatement(ModuleStatement* node) { + Visit(node->body()); +} + + +void AstNumberingVisitor::VisitExpressionStatement(ExpressionStatement* node) { + Visit(node->expression()); +} + + +void AstNumberingVisitor::VisitEmptyStatement(EmptyStatement* node) { +} + + +void AstNumberingVisitor::VisitIfStatement(IfStatement* node) { + Visit(node->condition()); + Visit(node->then_statement()); + if (node->HasElseStatement()) { + Visit(node->else_statement()); + } +} + + +void AstNumberingVisitor::VisitContinueStatement(ContinueStatement* node) { +} + + +void AstNumberingVisitor::VisitBreakStatement(BreakStatement* node) { +} + + +void AstNumberingVisitor::VisitReturnStatement(ReturnStatement* node) { + Visit(node->expression()); +} + + +void AstNumberingVisitor::VisitWithStatement(WithStatement* node) { + Visit(node->expression()); + Visit(node->statement()); +} + + +void AstNumberingVisitor::VisitSwitchStatement(SwitchStatement* node) { + Visit(node->tag()); + ZoneList<CaseClause*>* cases = node->cases(); + for (int i = 0; i < cases->length(); i++) { + VisitCaseClause(cases->at(i)); + } +} + + +void AstNumberingVisitor::VisitCaseClause(CaseClause* node) { + if (!node->is_default()) Visit(node->label()); + VisitStatements(node->statements()); +} + + +void AstNumberingVisitor::VisitDoWhileStatement(DoWhileStatement* node) { + Visit(node->body()); + Visit(node->cond()); +} + + +void AstNumberingVisitor::VisitWhileStatement(WhileStatement* node) { + Visit(node->cond()); + Visit(node->body()); +} + + +void AstNumberingVisitor::VisitForStatement(ForStatement* node) { + if (node->init() != NULL) Visit(node->init()); + if (node->cond() != NULL) Visit(node->cond()); + if (node->next() != NULL) Visit(node->next()); + Visit(node->body()); +} + + +void AstNumberingVisitor::VisitForInStatement(ForInStatement* node) { + Visit(node->each()); + Visit(node->enumerable()); + Visit(node->body()); +} + + +void AstNumberingVisitor::VisitForOfStatement(ForOfStatement* node) { + Visit(node->each()); + Visit(node->iterable()); + Visit(node->body()); +} + + +void AstNumberingVisitor::VisitTryCatchStatement(TryCatchStatement* node) { + Visit(node->try_block()); + Visit(node->catch_block()); +} + + +void AstNumberingVisitor::VisitTryFinallyStatement(TryFinallyStatement* node) { + Visit(node->try_block()); + Visit(node->finally_block()); +} + + +void AstNumberingVisitor::VisitDebuggerStatement(DebuggerStatement* node) { +} + + +void AstNumberingVisitor::VisitClassLiteral(ClassLiteral* node) { + if (node->extends()) Visit(node->extends()); + for (int i = 0; i < node->properties()->length(); i++) { + VisitObjectLiteralProperty(node->properties()->at(i)); + } +} + + +void AstNumberingVisitor::VisitNativeFunctionLiteral(NativeFunctionLiteral* node) { +} + + +void AstNumberingVisitor::VisitConditional(Conditional* node) { + Visit(node->condition()); + Visit(node->then_expression()); + Visit(node->else_expression()); +} + + +void AstNumberingVisitor::VisitLiteral(Literal* node) { +} + + +void AstNumberingVisitor::VisitRegExpLiteral(RegExpLiteral* node) { +} + + +void AstNumberingVisitor::VisitObjectLiteral(ObjectLiteral* node) { + for (int i = 0; i < node->properties()->length(); i++) { + VisitObjectLiteralProperty(node->properties()->at(i)); + } +} + + +void AstNumberingVisitor::VisitObjectLiteralProperty( + ObjectLiteralProperty* property) { + Visit(property->key()); + Visit(property->value()); +} + + +void AstNumberingVisitor::VisitArrayLiteral(ArrayLiteral* node) { + for (int i = 0; i < node->values()->length(); i++) { + Visit(node->values()->at(i)); + } +} + + +void AstNumberingVisitor::VisitVariableProxy(VariableProxy* node) { +} + + +void AstNumberingVisitor::VisitAssignment(Assignment* node) { + Visit(node->target()); + Visit(node->value()); +} + + +void AstNumberingVisitor::VisitYield(Yield* node) { + Visit(node->expression()); +} + + +void AstNumberingVisitor::VisitThrow(Throw* node) { + Visit(node->exception()); +} + + +void AstNumberingVisitor::VisitProperty(Property* node) { + Expression* key = node->key(); + Literal* literal = key->AsLiteral(); + if (literal != NULL && literal->IsPropertyName()) { + Visit(node->obj()); + } else { + Visit(node->obj()); + Visit(key); + } +} + + +void AstNumberingVisitor::VisitCall(Call* node) { + Visit(node->expression()); + VisitArguments(node->arguments()); +} + + +void AstNumberingVisitor::VisitCallNew(CallNew* node) { + Visit(node->expression()); + VisitArguments(node->arguments()); +} + + +void AstNumberingVisitor::VisitCallRuntime(CallRuntime* node) { + VisitArguments(node->arguments()); +} + + +void AstNumberingVisitor::VisitUnaryOperation(UnaryOperation* node) { + Visit(node->expression()); +} + + +void AstNumberingVisitor::VisitCountOperation(CountOperation* node) { + Visit(node->expression()); +} + + +void AstNumberingVisitor::VisitBinaryOperation(BinaryOperation* node) { + Visit(node->left()); + Visit(node->right()); +} + + +void AstNumberingVisitor::VisitCompareOperation(CompareOperation* node) { + Visit(node->left()); + Visit(node->right()); +} + + +void AstNumberingVisitor::VisitThisFunction(ThisFunction* node) { +} + + +void AstNumberingVisitor::VisitSuperReference(SuperReference* node) { +} + + +void AstNumberingVisitor::VisitStatements(ZoneList<Statement*>* statements) { + if (statements == NULL) return; + for (int i = 0; i < statements->length(); i++) { + Visit(statements->at(i)); + } +} + + +void AstNumberingVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) { + for (int i = 0; i < declarations->length(); i++) { + Visit(declarations->at(i)); + } +} + + +void AstNumberingVisitor::VisitArguments(ZoneList<Expression*>* arguments) { + for (int i = 0; i < arguments->length(); i++) { + Visit(arguments->at(i)); + } +} + + +void AstNumberingVisitor::VisitFunctionLiteral(FunctionLiteral* function) { + VisitDeclarations(function->scope()->declarations()); + VisitStatements(function->body()); +} + + RegExpBuilder::RegExpBuilder(Zone* zone) : zone_(zone), pending_empty_(false), @@ -926,6 +1258,15 @@ FunctionLiteral* Parser::DoParseProgram(CompilationInfo* info, Scope** scope, // Make sure the target stack is empty. DCHECK(target_stack_ == NULL); + if (result != NULL) { + AstNumberingVisitor visitor(zone()); + visitor.Visit(result); + if (visitor.HasStackOverflow()) { + set_stack_overflow(); + result = NULL; + } + } + return result; } @@ -1026,6 +1367,15 @@ FunctionLiteral* Parser::ParseLazy(Utf16CharacterStream* source) { DCHECK(target_stack_ == NULL); if (result != NULL) { + AstNumberingVisitor visitor(zone()); + visitor.Visit(result); + if (visitor.HasStackOverflow()) { + set_stack_overflow(); + result = NULL; + } + } + + if (result != NULL) { Handle<String> inferred_name(shared_info->inferred_name()); result->set_inferred_name(inferred_name); }
