From e3c0ae62af481b632b6333f126767c44df436799 Mon Sep 17 00:00:00 2001 From: olehougaard Date: Thu, 26 Feb 2009 07:54:22 +0000 Subject: [PATCH] Go into slow case when encountering object initialization on the top level to optimize performance of code like C.prototype.x = ...; C.prototype.y = ...; ... C.prototype.z = ...; Review URL: http://codereview.chromium.org/27128 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@1372 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/ast.h | 14 ++- src/codegen-ia32.cc | 17 ++++ src/parser.cc | 117 +++++++++++++++++++++++++- src/runtime.cc | 16 ++++ src/runtime.h | 2 + test/mjsunit/top-level-assignments.js | 96 +++++++++++++++++++++ 6 files changed, 260 insertions(+), 2 deletions(-) create mode 100644 test/mjsunit/top-level-assignments.js diff --git a/src/ast.h b/src/ast.h index f8272f8e6..c0fa4146a 100644 --- a/src/ast.h +++ b/src/ast.h @@ -1106,7 +1106,8 @@ class Conditional: public Expression { class Assignment: public Expression { public: Assignment(Token::Value op, Expression* target, Expression* value, int pos) - : op_(op), target_(target), value_(value), pos_(pos) { + : op_(op), target_(target), value_(value), pos_(pos), + block_start_(false), block_end_(false) { ASSERT(Token::IsAssignmentOp(op)); } @@ -1120,11 +1121,22 @@ class Assignment: public Expression { Expression* value() const { return value_; } int position() { return pos_; } + // An initialization block is a series of statments of the form + // x.y.z.a = ...; x.y.z.b = ...; etc. The parser marks the beginning and + // ending of these blocks to allow for optimizations of initialization + // blocks. + bool starts_initialization_block() { return block_start_; } + bool ends_initialization_block() { return block_end_; } + void mark_block_start() { block_start_ = true; } + void mark_block_end() { block_end_ = true; } + private: Token::Value op_; Expression* target_; Expression* value_; int pos_; + bool block_start_; + bool block_end_; }; diff --git a/src/codegen-ia32.cc b/src/codegen-ia32.cc index f5086b298..5bdeb0077 100644 --- a/src/codegen-ia32.cc +++ b/src/codegen-ia32.cc @@ -2758,6 +2758,15 @@ void CodeGenerator::VisitAssignment(Assignment* node) { Reference target(this, node->target()); if (target.is_illegal()) return; + if (node->starts_initialization_block()) { + ASSERT(target.type() == Reference::NAMED || + target.type() == Reference::KEYED); + // Change to slow case in the beginning of an initialization block + // to avoid the quadratic behavior of repeatedly adding fast properties. + int stack_position = (target.type() == Reference::NAMED) ? 0 : 1; + frame_->Push(Operand(esp, stack_position * kPointerSize)); + __ CallRuntime(Runtime::kToSlowProperties, 1); + } if (node->op() == Token::ASSIGN || node->op() == Token::INIT_VAR || node->op() == Token::INIT_CONST) { @@ -2789,6 +2798,14 @@ void CodeGenerator::VisitAssignment(Assignment* node) { target.SetValue(CONST_INIT); } else { target.SetValue(NOT_CONST_INIT); + if (node->ends_initialization_block()) { + ASSERT(target.type() == Reference::NAMED || + target.type() == Reference::KEYED); + // End of initialization block. Revert to fast case. + int stack_position = (target.type() == Reference::NAMED) ? 1 : 2; + frame_->Push(Operand(esp, stack_position * kPointerSize)); + __ CallRuntime(Runtime::kToFastProperties, 1); + } } } } diff --git a/src/parser.cc b/src/parser.cc index 0a5fa312d..611f93a5b 100644 --- a/src/parser.cc +++ b/src/parser.cc @@ -69,6 +69,11 @@ class Parser { Handle name, int start_position, bool is_expression); + // The minimum number of contiguous assignment that will + // be treated as an initialization block. Benchmarks show that + // the overhead exceeds the savings below this limit. + static const int kMinInitializationBlock = 3; + protected: enum Mode { @@ -1215,6 +1220,110 @@ void PreParser::ReportMessageAt(Scanner::Location source_location, } +// An InitializationBlockFinder finds and marks sequences of statements of the +// form x.y.z.a = ...; x.y.z.b = ...; etc. +class InitializationBlockFinder { + public: + InitializationBlockFinder() + : first_in_block_(NULL), last_in_block_(NULL), block_size_(0) {} + + ~InitializationBlockFinder() { + if (InBlock()) EndBlock(); + } + + void Update(Statement* stat) { + Assignment* assignment = AsAssignment(stat); + if (InBlock()) { + if (BlockContinues(assignment)) { + UpdateBlock(assignment); + } else { + EndBlock(); + } + } + if (!InBlock() && (assignment != NULL) && + (assignment->op() == Token::ASSIGN)) { + StartBlock(assignment); + } + } + + private: + static Assignment* AsAssignment(Statement* stat) { + if (stat == NULL) return NULL; + ExpressionStatement* exp_stat = stat->AsExpressionStatement(); + if (exp_stat == NULL) return NULL; + return exp_stat->expression()->AsAssignment(); + } + + // Returns true if the expressions appear to denote the same object. + // In the context of initialization blocks, we only consider expressions + // of the form 'x.y.z'. + static bool SameObject(Expression* e1, Expression* e2) { + VariableProxy* v1 = e1->AsVariableProxy(); + VariableProxy* v2 = e2->AsVariableProxy(); + if (v1 != NULL && v2 != NULL) { + return v1->name()->Equals(*v2->name()); + } + Property* p1 = e1->AsProperty(); + Property* p2 = e2->AsProperty(); + if ((p1 == NULL) || (p2 == NULL)) return false; + Literal* key1 = p1->key()->AsLiteral(); + Literal* key2 = p2->key()->AsLiteral(); + if ((key1 == NULL) || (key2 == NULL)) return false; + if (!key1->handle()->IsString() || !key2->handle()->IsString()) { + return false; + } + String* name1 = String::cast(*key1->handle()); + String* name2 = String::cast(*key2->handle()); + if (!name1->Equals(name2)) return false; + return SameObject(p1->obj(), p2->obj()); + } + + // Returns true if the expressions appear to denote different properties + // of the same object. + static bool PropertyOfSameObject(Expression* e1, Expression* e2) { + Property* p1 = e1->AsProperty(); + Property* p2 = e2->AsProperty(); + if ((p1 == NULL) || (p2 == NULL)) return false; + return SameObject(p1->obj(), p2->obj()); + } + + bool BlockContinues(Assignment* assignment) { + if ((assignment == NULL) || (first_in_block_ == NULL)) return false; + if (assignment->op() != Token::ASSIGN) return false; + return PropertyOfSameObject(first_in_block_->target(), + assignment->target()); + } + + void StartBlock(Assignment* assignment) { + first_in_block_ = assignment; + last_in_block_ = assignment; + block_size_ = 1; + } + + void UpdateBlock(Assignment* assignment) { + last_in_block_ = assignment; + ++block_size_; + } + + void EndBlock() { + if (block_size_ >= Parser::kMinInitializationBlock) { + first_in_block_->mark_block_start(); + last_in_block_->mark_block_end(); + } + last_in_block_ = first_in_block_ = NULL; + block_size_ = 0; + } + + bool InBlock() { return first_in_block_ != NULL; } + + Assignment* first_in_block_; + Assignment* last_in_block_; + int block_size_; + + DISALLOW_COPY_AND_ASSIGN(InitializationBlockFinder); +}; + + void* Parser::ParseSourceElements(ZoneListWrapper* processor, int end_token, bool* ok) { @@ -1228,9 +1337,15 @@ void* Parser::ParseSourceElements(ZoneListWrapper* processor, TargetScope scope(this); ASSERT(processor != NULL); + InitializationBlockFinder block_finder; while (peek() != end_token) { Statement* stat = ParseStatement(NULL, CHECK_OK); - if (stat && !stat->IsEmpty()) processor->Add(stat); + if (stat == NULL || stat->IsEmpty()) continue; + // We find and mark the initialization blocks on top level code only. + // This is because the optimization prevents reuse of the map transitions, + // so it should be used only for code that will only be run once. + if (top_scope_->is_global_scope()) block_finder.Update(stat); + processor->Add(stat); } return 0; } diff --git a/src/runtime.cc b/src/runtime.cc index ea27da9fe..489e82db0 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -2151,6 +2151,22 @@ static Object* Runtime_GetArgumentsProperty(Arguments args) { } +static Object* Runtime_ToFastProperties(Arguments args) { + ASSERT(args.length() == 1); + CONVERT_ARG_CHECKED(JSObject, object, 0); + object->TransformToFastProperties(0); + return *object; +} + + +static Object* Runtime_ToSlowProperties(Arguments args) { + ASSERT(args.length() == 1); + CONVERT_ARG_CHECKED(JSObject, object, 0); + object->NormalizeProperties(CLEAR_INOBJECT_PROPERTIES); + return *object; +} + + static Object* Runtime_ToBool(Arguments args) { NoHandleAllocation ha; ASSERT(args.length() == 1); diff --git a/src/runtime.h b/src/runtime.h index ecb9a10c3..34aa4b915 100644 --- a/src/runtime.h +++ b/src/runtime.h @@ -49,6 +49,8 @@ namespace v8 { namespace internal { F(GetPropertyNames, 1) \ F(GetPropertyNamesFast, 1) \ F(GetArgumentsProperty, 1) \ + F(ToFastProperties, 1) \ + F(ToSlowProperties, 1) \ \ F(IsInPrototypeChain, 2) \ \ diff --git a/test/mjsunit/top-level-assignments.js b/test/mjsunit/top-level-assignments.js new file mode 100644 index 000000000..7ab6e2569 --- /dev/null +++ b/test/mjsunit/top-level-assignments.js @@ -0,0 +1,96 @@ +// Copyright 2009 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +// Testing that optimization of top-level object initialization doesn't +// break V8. + +var x = new Object(); +x.a = 7; +x.b = function() { return 42; }; +x.c = 88; +x.d = "A Man Called Horse"; + +assertEquals(7, x.a); +assertEquals(42, x.b()); +assertEquals(88, x.c); +assertEquals("A Man Called Horse", x.d); + +var y = new Object(); +y.a = 7; +y.b = function() { return 42; }; +y.c = 12 * y.a; +y.d = "A Man Called Horse"; + +assertEquals(84, y.c); + +var z = new Object(); +z.a = 3; +function forty_two() { return 42; }; +z.a += 4; +z.b = forty_two; +z.c = 12; +z.c *= z.a; +z.d = "A Man Called Horse"; + +assertEquals(84, z.c); + +var x1 = new Object(); +var x2 = new Object(); +x1.a = 7; +x1.b = function() { return 42; }; +x2.a = 7; +x2.b = function() { return 42; }; +x1.c = 88; +x1.d = "A Man Called Horse"; +x2.c = 88; +x2.d = "A Man Called Horse"; + +assertEquals(7, x1.a); +assertEquals(42, x1.b()); +assertEquals(88, x1.c); +assertEquals("A Man Called Horse", x1.d); + +assertEquals(7, x2.a); +assertEquals(42, x2.b()); +assertEquals(88, x2.c); +assertEquals("A Man Called Horse", x2.d); + +function Calculator(x, y) { + this.x = x; + this.y = y; +} + +Calculator.prototype.sum = function() { return this.x + this.y; }; +Calculator.prototype.difference = function() { return this.x - this.y; }; +Calculator.prototype.product = function() { return this.x * this.y; }; +Calculator.prototype.quotient = function() { return this.x / this.y; }; + +var calc = new Calculator(20, 10); +assertEquals(30, calc.sum()); +assertEquals(10, calc.difference()); +assertEquals(200, calc.product()); +assertEquals(2, calc.quotient()); -- 2.34.1