From 911d447b96878681c0015606ca90be040aae3400 Mon Sep 17 00:00:00 2001 From: "erik.corry@gmail.com" Date: Wed, 6 Jun 2012 10:17:26 +0000 Subject: [PATCH] Keep track of which maps are associated with prototype objects so we can tune the fast-case vs. hash map heuristics accordingly. This is a reland of r11681 https://chromiumcodereview.appspot.com/10448011 , which was reverted because of layout test failures that were actually caused by the long-standing issue fixed in https://chromiumcodereview.appspot.com/10515006 (r11706). Review URL: https://chromiumcodereview.appspot.com/10532021 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@11727 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/objects-inl.h | 29 +++++++++-- src/objects.cc | 75 +++++++++++++++++++++++---- src/objects.h | 28 ++++++++-- src/runtime.cc | 2 + src/runtime.h | 1 + test/cctest/test-heap.cc | 15 ++++-- test/mjsunit/fast-prototype.js | 113 +++++++++++++++++++++++++++++++++++++++++ 7 files changed, 240 insertions(+), 23 deletions(-) create mode 100644 test/mjsunit/fast-prototype.js diff --git a/src/objects-inl.h b/src/objects-inl.h index 0620e0e..c1a75fe 100644 --- a/src/objects-inl.h +++ b/src/objects-inl.h @@ -1611,13 +1611,21 @@ bool JSObject::HasFastProperties() { } -int JSObject::MaxFastProperties() { +bool JSObject::TooManyFastProperties(int properties) { // Allow extra fast properties if the object has more than - // kMaxFastProperties in-object properties. When this is the case, + // kFastPropertiesSoftLimit in-object properties. When this is the case, // it is very unlikely that the object is being used as a dictionary // and there is a good chance that allowing more map transitions // will be worth it. - return Max(map()->inobject_properties(), kMaxFastProperties); + int inobject = map()->inobject_properties(); + + int limit; + if (map()->used_for_prototype()) { + limit = Max(inobject, kMaxFastProperties); + } else { + limit = Max(inobject, kFastPropertiesSoftLimit); + } + return properties > limit; } @@ -2949,6 +2957,20 @@ bool Map::is_shared() { } +void Map::set_used_for_prototype(bool value) { + if (value) { + set_bit_field3(bit_field3() | (1 << kUsedForPrototype)); + } else { + set_bit_field3(bit_field3() & ~(1 << kUsedForPrototype)); + } +} + + +bool Map::used_for_prototype() { + return ((1 << kUsedForPrototype) & bit_field3()) != 0; +} + + JSFunction* Map::unchecked_constructor() { return reinterpret_cast(READ_FIELD(this, kConstructorOffset)); } @@ -4099,6 +4121,7 @@ Object* JSFunction::prototype() { return instance_prototype(); } + bool JSFunction::should_have_prototype() { return map()->function_with_prototype(); } diff --git a/src/objects.cc b/src/objects.cc index e5f0e49..5bbba49 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -1580,7 +1580,7 @@ MaybeObject* JSObject::AddFastProperty(String* name, } if (map()->unused_property_fields() == 0) { - if (properties()->length() > MaxFastProperties()) { + if (TooManyFastProperties(properties()->length())) { Object* obj; { MaybeObject* maybe_obj = NormalizeProperties(CLEAR_INOBJECT_PROPERTIES, 0); @@ -1830,7 +1830,7 @@ MaybeObject* JSObject::ConvertDescriptorToField(String* name, Object* new_value, PropertyAttributes attributes) { if (map()->unused_property_fields() == 0 && - properties()->length() > MaxFastProperties()) { + TooManyFastProperties(properties()->length())) { Object* obj; { MaybeObject* maybe_obj = NormalizeProperties(CLEAR_INOBJECT_PROPERTIES, 0); @@ -5042,6 +5042,7 @@ MaybeObject* Map::CopyDropTransitions() { return new_map; } + void Map::UpdateCodeCache(Handle map, Handle name, Handle code) { @@ -7612,9 +7613,57 @@ bool JSFunction::IsInlineable() { } +MaybeObject* JSObject::OptimizeAsPrototype() { + if (IsGlobalObject()) return this; + + // Make sure prototypes are fast objects and their maps have the bit set + // so they remain fast. + Map* proto_map = map(); + if (!proto_map->used_for_prototype()) { + if (!HasFastProperties()) { + MaybeObject* new_proto = TransformToFastProperties(0); + if (new_proto->IsFailure()) return new_proto; + ASSERT(new_proto == this); + proto_map = map(); + if (!proto_map->is_shared()) { + proto_map->set_used_for_prototype(true); + } + } else { + Heap* heap = GetHeap(); + // We use the hole value as a singleton key in the prototype transition + // map so that we don't multiply the number of maps unnecessarily. + Map* new_map = + proto_map->GetPrototypeTransition(heap->the_hole_value()); + if (new_map == NULL) { + MaybeObject* maybe_new_map = proto_map->CopyDropTransitions(); + if (!maybe_new_map->To(&new_map)) return maybe_new_map; + new_map->set_used_for_prototype(true); + MaybeObject* ok = + proto_map->PutPrototypeTransition(heap->the_hole_value(), + new_map); + if (ok->IsFailure()) return ok; + } + ASSERT(!proto_map->is_shared() && !new_map->is_shared()); + set_map(new_map); + } + } + return this; +} + + MaybeObject* JSFunction::SetInstancePrototype(Object* value) { ASSERT(value->IsJSReceiver()); Heap* heap = GetHeap(); + + // First some logic for the map of the prototype to make sure the + // used_for_prototype flag is set. + if (value->IsJSObject()) { + MaybeObject* ok = JSObject::cast(value)->OptimizeAsPrototype(); + if (ok->IsFailure()) return ok; + } + + // Now some logic for the maps of the objects that are created by using this + // function as a constructor. if (has_initial_map()) { // If the function has allocated the initial map // replace it with a copy containing the new prototype. @@ -8786,7 +8835,7 @@ MaybeObject* JSArray::SetElementsLength(Object* len) { } -Object* Map::GetPrototypeTransition(Object* prototype) { +Map* Map::GetPrototypeTransition(Object* prototype) { FixedArray* cache = prototype_transitions(); int number_of_transitions = NumberOfProtoTransitions(); const int proto_offset = @@ -8796,8 +8845,7 @@ Object* Map::GetPrototypeTransition(Object* prototype) { for (int i = 0; i < number_of_transitions; i++) { if (cache->get(proto_offset + i * step) == prototype) { Object* map = cache->get(map_offset + i * step); - ASSERT(map->IsMap()); - return map; + return Map::cast(map); } } return NULL; @@ -8905,21 +8953,26 @@ MaybeObject* JSReceiver::SetPrototype(Object* value, // Nothing to do if prototype is already set. if (map->prototype() == value) return value; - Object* new_map = map->GetPrototypeTransition(value); + if (value->IsJSObject()) { + MaybeObject* ok = JSObject::cast(value)->OptimizeAsPrototype(); + if (ok->IsFailure()) return ok; + } + + Map* new_map = map->GetPrototypeTransition(value); if (new_map == NULL) { { MaybeObject* maybe_new_map = map->CopyDropTransitions(); - if (!maybe_new_map->ToObject(&new_map)) return maybe_new_map; + if (!maybe_new_map->To(&new_map)) return maybe_new_map; } { MaybeObject* maybe_new_cache = - map->PutPrototypeTransition(value, Map::cast(new_map)); + map->PutPrototypeTransition(value, new_map); if (maybe_new_cache->IsFailure()) return maybe_new_cache; } - Map::cast(new_map)->set_prototype(value); + new_map->set_prototype(value); } - ASSERT(Map::cast(new_map)->prototype() == value); - real_receiver->set_map(Map::cast(new_map)); + ASSERT(new_map->prototype() == value); + real_receiver->set_map(new_map); heap->ClearInstanceofCache(); ASSERT(size == Size()); diff --git a/src/objects.h b/src/objects.h index ea0ca9c..e5dc780 100644 --- a/src/objects.h +++ b/src/objects.h @@ -1583,6 +1583,8 @@ class JSObject: public JSReceiver { MUST_USE_RESULT MaybeObject* DeleteNormalizedProperty(String* name, DeleteMode mode); + MUST_USE_RESULT MaybeObject* OptimizeAsPrototype(); + // Retrieve interceptors. InterceptorInfo* GetNamedInterceptor(); InterceptorInfo* GetIndexedInterceptor(); @@ -2052,7 +2054,7 @@ class JSObject: public JSReceiver { // Maximal number of fast properties for the JSObject. Used to // restrict the number of map transitions to avoid an explosion in // the number of maps for objects used as dictionaries. - inline int MaxFastProperties(); + inline bool TooManyFastProperties(int properties); // Maximal number of elements (numbered 0 .. kMaxElementCount - 1). // Also maximal value of JSArray's length property. @@ -2074,7 +2076,8 @@ class JSObject: public JSReceiver { static const int kMaxUncheckedOldFastElementsLength = 500; static const int kInitialMaxFastElementArray = 100000; - static const int kMaxFastProperties = 12; + static const int kFastPropertiesSoftLimit = 12; + static const int kMaxFastProperties = 32; static const int kMaxInstanceSize = 255 * kPointerSize; // When extending the backing storage for property values, we increase // its size by more than the 1 entry necessary, so sequentially adding fields @@ -4687,9 +4690,16 @@ class Map: public HeapObject { // behavior. If true, the map should never be modified, instead a clone // should be created and modified. inline void set_is_shared(bool value); - inline bool is_shared(); + // Tells whether the map is used for an object that is a prototype for another + // object or is the prototype on a function. Such maps are made faster by + // tweaking the heuristics that distinguish between regular object-oriented + // objects and the objects that are being used as hash maps. This flag is + // for optimization, not correctness. + inline void set_used_for_prototype(bool value); + inline bool used_for_prototype(); + // Tells whether the instance needs security checks when accessing its // properties. inline void set_is_access_check_needed(bool access_check_needed); @@ -4878,9 +4888,18 @@ class Map: public HeapObject { void TraverseTransitionTree(TraverseCallback callback, void* data); + // When you set the prototype of an object using the __proto__ accessor you + // need a new map for the object (the prototype is stored in the map). In + // order not to multiply maps unnecessarily we store these as transitions in + // the original map. That way we can transition to the same map if the same + // prototype is set, rather than creating a new map every time. The + // transitions are in the form of a map where the keys are prototype objects + // and the values are the maps the are transitioned to. The special key + // the_hole denotes the map we should transition to when the + // used_for_prototype flag is set. static const int kMaxCachedPrototypeTransitions = 256; - Object* GetPrototypeTransition(Object* prototype); + Map* GetPrototypeTransition(Object* prototype); MUST_USE_RESULT MaybeObject* PutPrototypeTransition(Object* prototype, Map* map); @@ -4973,6 +4992,7 @@ class Map: public HeapObject { // Bit positions for bit field 3 static const int kIsShared = 0; static const int kFunctionWithPrototype = 1; + static const int kUsedForPrototype = 2; // Layout of the default cache. It holds alternating name and code objects. static const int kCodeCacheEntrySize = 2; diff --git a/src/runtime.cc b/src/runtime.cc index 5b85246..a418797 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -13471,6 +13471,8 @@ ELEMENTS_KIND_CHECK_RUNTIME_FUNCTION(ExternalIntElements) ELEMENTS_KIND_CHECK_RUNTIME_FUNCTION(ExternalUnsignedIntElements) ELEMENTS_KIND_CHECK_RUNTIME_FUNCTION(ExternalFloatElements) ELEMENTS_KIND_CHECK_RUNTIME_FUNCTION(ExternalDoubleElements) +// Properties test sitting with elements tests - not fooling anyone. +ELEMENTS_KIND_CHECK_RUNTIME_FUNCTION(FastProperties) #undef ELEMENTS_KIND_CHECK_RUNTIME_FUNCTION diff --git a/src/runtime.h b/src/runtime.h index fc0a472..f5a4f50 100644 --- a/src/runtime.h +++ b/src/runtime.h @@ -380,6 +380,7 @@ namespace internal { F(HasExternalUnsignedIntElements, 1, 1) \ F(HasExternalFloatElements, 1, 1) \ F(HasExternalDoubleElements, 1, 1) \ + F(HasFastProperties, 1, 1) \ F(TransitionElementsSmiToDouble, 1, 1) \ F(TransitionElementsDoubleToObject, 1, 1) \ F(HaveSameMap, 2, 1) \ diff --git a/test/cctest/test-heap.cc b/test/cctest/test-heap.cc index 3ddab85..498b67d 100644 --- a/test/cctest/test-heap.cc +++ b/test/cctest/test-heap.cc @@ -1579,18 +1579,23 @@ TEST(PrototypeTransitionClearing) { *v8::Handle::Cast( v8::Context::GetCurrent()->Global()->Get(v8_str("base")))); - // Verify that only dead prototype transitions are cleared. - CHECK_EQ(10, baseObject->map()->NumberOfProtoTransitions()); + // Verify that only dead prototype transitions are cleared. There is an + // extra, 11th, prototype transition on the Object map, which is the + // transition to a map with the used_for_prototype flag set (the key is + // the_hole). + CHECK_EQ(11, baseObject->map()->NumberOfProtoTransitions()); HEAP->CollectAllGarbage(Heap::kNoGCFlags); - CHECK_EQ(10 - 3, baseObject->map()->NumberOfProtoTransitions()); + const int transitions = 11 - 3; + CHECK_EQ(transitions, baseObject->map()->NumberOfProtoTransitions()); // Verify that prototype transitions array was compacted. FixedArray* trans = baseObject->map()->prototype_transitions(); - for (int i = 0; i < 10 - 3; i++) { + for (int i = 0; i < transitions; i++) { int j = Map::kProtoTransitionHeaderSize + i * Map::kProtoTransitionElementsPerEntry; CHECK(trans->get(j + Map::kProtoTransitionMapOffset)->IsMap()); - CHECK(trans->get(j + Map::kProtoTransitionPrototypeOffset)->IsJSObject()); + Object* proto = trans->get(j + Map::kProtoTransitionPrototypeOffset); + CHECK(proto->IsTheHole() || proto->IsJSObject()); } // Make sure next prototype is placed on an old-space evacuation candidate. diff --git a/test/mjsunit/fast-prototype.js b/test/mjsunit/fast-prototype.js new file mode 100644 index 0000000..f2fc202 --- /dev/null +++ b/test/mjsunit/fast-prototype.js @@ -0,0 +1,113 @@ +// Copyright 2012 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. + +// Flags: --allow-natives-syntax + +// Check that objects that are used for prototypes are in the fast mode. + +function Super() { +} + + +function Sub() { +} + + +function AddProps(obj) { + for (var i = 0; i < 26; i++) { + obj["x" + i] = 0; + } +} + + +function DoProtoMagic(proto, set__proto__) { + if (set__proto__) { + (new Sub()).__proto__ = proto; + } else { + Sub.prototype = proto; + } +} + + +function test(use_new, add_first, set__proto__, same_map_as) { + var proto = use_new ? new Super() : {}; + + // New object is fast. + assertTrue(%HasFastProperties(proto)); + + if (add_first) { + AddProps(proto); + // Adding this many properties makes it slow. + assertFalse(%HasFastProperties(proto)); + DoProtoMagic(proto, set__proto__); + // Making it a prototype makes it fast again. + assertTrue(%HasFastProperties(proto)); + } else { + DoProtoMagic(proto, set__proto__); + // Still fast + assertTrue(%HasFastProperties(proto)); + AddProps(proto); + // Setting the bit means it is still fast with all these properties. + assertTrue(%HasFastProperties(proto)); + } + if (same_map_as && !add_first) { + assertTrue(%HaveSameMap(same_map_as, proto)); + } + return proto; +} + + +for (var i = 0; i < 4; i++) { + var set__proto__ = ((i & 1) != 0); + var use_new = ((i & 2) != 0); + + test(use_new, true, set__proto__); + + var last = test(use_new, false, set__proto__); + test(use_new, false, set__proto__, last); +} + + +var x = {a: 1, b: 2, c: 3}; +var o = { __proto__: x }; +assertTrue(%HasFastProperties(x)); +for (key in x) { + assertTrue(key == 'a'); + break; +} +delete x.b; +for (key in x) { + assertTrue(key == 'a'); + break; +} +assertFalse(%HasFastProperties(x)); +x.d = 4; +assertFalse(%HasFastProperties(x)); +for (key in x) { + assertTrue(key == 'a'); + break; +} -- 2.7.4