Revision: 25082
Author: [email protected]
Date: Mon Nov 3 16:44:58 2014 UTC
Log: Reland "Limit the number of transitions allowed per hidden class."
BUG=chromium:427813
LOG=N
[email protected]
Review URL: https://codereview.chromium.org/676393002
https://code.google.com/p/v8/source/detail?r=25082
Modified:
/branches/bleeding_edge/src/heap/mark-compact.cc
/branches/bleeding_edge/src/objects-inl.h
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
/branches/bleeding_edge/src/transitions-inl.h
/branches/bleeding_edge/src/transitions.cc
/branches/bleeding_edge/src/transitions.h
/branches/bleeding_edge/test/cctest/test-heap.cc
=======================================
--- /branches/bleeding_edge/src/heap/mark-compact.cc Tue Oct 28 16:43:34
2014 UTC
+++ /branches/bleeding_edge/src/heap/mark-compact.cc Mon Nov 3 16:44:58
2014 UTC
@@ -2521,13 +2521,14 @@
// Note that we never eliminate a transition array, though we might
right-trim
// such that number_of_transitions() == 0. If this assumption changes,
- // TransitionArray::CopyInsert() will need to deal with the case that a
- // transition array disappeared during GC.
- int trim = t->number_of_transitions() - transition_index;
+ // TransitionArray::Insert() will need to deal with the case that a
transition
+ // array disappeared during GC.
+ int trim = t->number_of_transitions_storage() - transition_index;
if (trim > 0) {
heap_->RightTrimFixedArray<Heap::FROM_GC>(
t, t->IsSimpleTransition() ? trim
: trim *
TransitionArray::kTransitionSize);
+ t->SetNumberOfTransitions(transition_index);
}
DCHECK(map->HasTransitionArray());
}
=======================================
--- /branches/bleeding_edge/src/objects-inl.h Wed Oct 29 10:36:36 2014 UTC
+++ /branches/bleeding_edge/src/objects-inl.h Mon Nov 3 16:44:58 2014 UTC
@@ -5203,9 +5203,8 @@
bool Map::CanHaveMoreTransitions() {
if (!HasTransitionArray()) return true;
- return FixedArray::SizeFor(transitions()->length() +
- TransitionArray::kTransitionSize)
- <= Page::kMaxRegularHeapObjectSize;
+ return transitions()->number_of_transitions() <
+ TransitionArray::kMaxNumberOfTransitions;
}
@@ -7003,6 +7002,14 @@
DCHECK(!heap->InNewSpace(heap->empty_fixed_array()));
WRITE_FIELD(this, kCodeCacheOffset, heap->empty_fixed_array());
}
+
+
+int Map::SlackForArraySize(int old_size, int size_limit) {
+ const int max_slack = size_limit - old_size;
+ CHECK(max_slack >= 0);
+ if (old_size < 4) return Min(max_slack, 1);
+ return Min(max_slack, old_size / 2);
+}
void JSArray::EnsureSize(Handle<JSArray> array, int required_size) {
=======================================
--- /branches/bleeding_edge/src/objects.cc Fri Oct 31 14:51:48 2014 UTC
+++ /branches/bleeding_edge/src/objects.cc Mon Nov 3 16:44:58 2014 UTC
@@ -2709,6 +2709,10 @@
// Add missing transitions.
Handle<Map> new_map = split_map;
for (int i = split_nof; i < old_nof; ++i) {
+ if (!new_map->CanHaveMoreTransitions()) {
+ return CopyGeneralizeAllRepresentations(old_map, modify_index,
store_mode,
+ "can't have more
transitions");
+ }
new_map = CopyInstallDescriptors(new_map, i, new_descriptors);
}
new_map->set_owns_descriptors(true);
@@ -6584,7 +6588,8 @@
if (old_size == 0) {
descriptors = DescriptorArray::Allocate(map->GetIsolate(), 0, 1);
} else {
- EnsureDescriptorSlack(map, old_size < 4 ? 1 : old_size / 2);
+ EnsureDescriptorSlack(
+ map, SlackForArraySize(old_size, kMaxNumberOfDescriptors));
descriptors = handle(map->instance_descriptors());
}
}
@@ -6609,8 +6614,11 @@
DCHECK(child->is_prototype_map());
} else {
Handle<TransitionArray> transitions =
- TransitionArray::CopyInsert(parent, name, child, flag);
- parent->set_transitions(*transitions);
+ TransitionArray::Insert(parent, name, child, flag);
+ if (!parent->HasTransitionArray() ||
+ *transitions != parent->transitions()) {
+ parent->set_transitions(*transitions);
+ }
child->SetBackPointer(*parent);
}
}
@@ -6690,8 +6698,9 @@
DCHECK(kind != map->elements_kind());
}
- bool insert_transition =
- flag == INSERT_TRANSITION && !map->HasElementsTransition();
+ bool insert_transition = flag == INSERT_TRANSITION &&
+ map->CanHaveMoreTransitions() &&
+ !map->HasElementsTransition();
if (insert_transition && map->owns_descriptors()) {
// In case the map owned its own descriptors, share the descriptors and
@@ -6740,9 +6749,10 @@
new_map->InitializeDescriptors(map->instance_descriptors());
}
- Handle<Name> name = isolate->factory()->observed_symbol();
- ConnectTransition(map, new_map, name, FULL_TRANSITION);
-
+ if (map->CanHaveMoreTransitions()) {
+ Handle<Name> name = isolate->factory()->observed_symbol();
+ ConnectTransition(map, new_map, name, FULL_TRANSITION);
+ }
return new_map;
}
=======================================
--- /branches/bleeding_edge/src/objects.h Fri Oct 31 14:51:48 2014 UTC
+++ /branches/bleeding_edge/src/objects.h Mon Nov 3 16:44:58 2014 UTC
@@ -6122,6 +6122,8 @@
static void AppendCallbackDescriptors(Handle<Map> map,
Handle<Object> descriptors);
+ static inline int SlackForArraySize(int old_size, int size_limit);
+
static void EnsureDescriptorSlack(Handle<Map> map, int slack);
// Returns the found code or undefined if absent.
=======================================
--- /branches/bleeding_edge/src/transitions-inl.h Mon Oct 27 11:57:58 2014
UTC
+++ /branches/bleeding_edge/src/transitions-inl.h Mon Nov 3 16:44:58 2014
UTC
@@ -158,6 +158,15 @@
FixedArray::NoIncrementalWriteBarrierSet(
this, ToTargetIndex(transition_number), target);
}
+
+
+void TransitionArray::SetNumberOfTransitions(int number_of_transitions) {
+ if (IsFullTransitionArray()) {
+ DCHECK(number_of_transitions <= number_of_transitions_storage());
+ WRITE_FIELD(this, kTransitionLengthOffset,
+ Smi::FromInt(number_of_transitions));
+ }
+}
#undef FIELD_ADDR
=======================================
--- /branches/bleeding_edge/src/transitions.cc Mon Oct 27 11:57:58 2014 UTC
+++ /branches/bleeding_edge/src/transitions.cc Mon Nov 3 16:44:58 2014 UTC
@@ -13,10 +13,12 @@
Handle<TransitionArray> TransitionArray::Allocate(Isolate* isolate,
- int
number_of_transitions) {
- Handle<FixedArray> array =
- isolate->factory()->NewFixedArray(ToKeyIndex(number_of_transitions));
+ int
number_of_transitions,
+ int slack) {
+ Handle<FixedArray> array = isolate->factory()->NewFixedArray(
+ LengthFor(number_of_transitions + slack));
array->set(kPrototypeTransitionsIndex, Smi::FromInt(0));
+ array->set(kTransitionLengthIndex, Smi::FromInt(number_of_transitions));
return Handle<TransitionArray>::cast(array);
}
@@ -74,6 +76,7 @@
if (new_nof != nof) {
DCHECK(new_nof == 0);
result->Shrink(ToKeyIndex(0));
+ result->SetNumberOfTransitions(0);
} else if (nof == 1) {
result->NoIncrementalWriteBarrierCopyFrom(
containing_map->transitions(), kSimpleTransitionIndex, 0);
@@ -85,21 +88,47 @@
}
-Handle<TransitionArray> TransitionArray::CopyInsert(Handle<Map> map,
- Handle<Name> name,
- Handle<Map> target,
- SimpleTransitionFlag
flag) {
+Handle<TransitionArray> TransitionArray::Insert(Handle<Map> map,
+ Handle<Name> name,
+ Handle<Map> target,
+ SimpleTransitionFlag flag)
{
if (!map->HasTransitionArray()) {
return TransitionArray::NewWith(map, name, target, flag);
}
int number_of_transitions = map->transitions()->number_of_transitions();
- int new_size = number_of_transitions;
+ int new_nof = number_of_transitions;
int insertion_index = map->transitions()->Search(*name);
- if (insertion_index == kNotFound) ++new_size;
+ if (insertion_index == kNotFound) ++new_nof;
+ CHECK(new_nof <= kMaxNumberOfTransitions);
+
+ if (new_nof <= map->transitions()->number_of_transitions_storage()) {
+ DisallowHeapAllocation no_gc;
+ TransitionArray* array = map->transitions();
+
+ if (insertion_index != kNotFound) {
+ array->SetTarget(insertion_index, *target);
+ return handle(array);
+ }
+
+ array->SetNumberOfTransitions(new_nof);
+ uint32_t hash = name->Hash();
+ for (insertion_index = number_of_transitions; insertion_index > 0;
+ --insertion_index) {
+ Name* key = array->GetKey(insertion_index - 1);
+ if (key->Hash() <= hash) break;
+ array->SetKey(insertion_index, key);
+ array->SetTarget(insertion_index, array->GetTarget(insertion_index -
1));
+ }
+ array->SetKey(insertion_index, *name);
+ array->SetTarget(insertion_index, *target);
+ return handle(array);
+ }
- Handle<TransitionArray> result = Allocate(map->GetIsolate(), new_size);
+ Handle<TransitionArray> result = Allocate(
+ map->GetIsolate(), new_nof,
+ Map::SlackForArraySize(number_of_transitions,
kMaxNumberOfTransitions));
// The map's transition array may grown smaller during the allocation
above as
// it was weakly traversed, though it is guaranteed not to disappear.
Trim the
@@ -111,28 +140,18 @@
DCHECK(array->number_of_transitions() < number_of_transitions);
number_of_transitions = array->number_of_transitions();
- new_size = number_of_transitions;
+ new_nof = number_of_transitions;
insertion_index = array->Search(*name);
- if (insertion_index == kNotFound) ++new_size;
+ if (insertion_index == kNotFound) ++new_nof;
- result->Shrink(ToKeyIndex(new_size));
+ result->Shrink(ToKeyIndex(new_nof));
+ result->SetNumberOfTransitions(new_nof);
}
if (array->HasPrototypeTransitions()) {
result->SetPrototypeTransitions(array->GetPrototypeTransitions());
}
-
- if (insertion_index != kNotFound) {
- for (int i = 0; i < number_of_transitions; ++i) {
- if (i != insertion_index) {
- result->NoIncrementalWriteBarrierCopyFrom(array, i, i);
- }
- }
- result->NoIncrementalWriteBarrierSet(insertion_index, *name, *target);
- result->set_back_pointer_storage(array->back_pointer_storage());
- return result;
- }
insertion_index = 0;
for (; insertion_index < number_of_transitions; ++insertion_index) {
=======================================
--- /branches/bleeding_edge/src/transitions.h Mon Oct 27 11:57:58 2014 UTC
+++ /branches/bleeding_edge/src/transitions.h Mon Nov 3 16:44:58 2014 UTC
@@ -30,8 +30,9 @@
// The full format is:
// [0] Undefined or back pointer map
// [1] Smi(0) or fixed array of prototype transitions
-// [2] First transition
-// [length() - kTransitionSize] Last transition
+// [2] Number of transitions
+// [3] First transition
+// [3 + number of transitions * kTransitionSize]: start of slack
class TransitionArray: public FixedArray {
public:
// Accessors for fetching instance transition at transition number.
@@ -67,10 +68,21 @@
// Returns the number of transitions in the array.
int number_of_transitions() {
if (IsSimpleTransition()) return 1;
- int len = length();
- return len <= kFirstIndex ? 0 : (len - kFirstIndex) / kTransitionSize;
+ if (length() <= kFirstIndex) return 0;
+ return Smi::cast(get(kTransitionLengthIndex))->value();
}
+ int number_of_transitions_storage() {
+ if (IsSimpleTransition()) return 1;
+ if (length() <= kFirstIndex) return 0;
+ return (length() - kFirstIndex) / kTransitionSize;
+ }
+
+ int NumberOfSlackTransitions() {
+ return number_of_transitions_storage() - number_of_transitions();
+ }
+
+ inline void SetNumberOfTransitions(int number_of_transitions);
inline int number_of_entries() { return number_of_transitions(); }
// Creates a FullTransitionArray from a SimpleTransitionArray in
@@ -78,21 +90,22 @@
static Handle<TransitionArray> ExtendToFullTransitionArray(
Handle<Map> containing_map);
- // Create a transition array, copying from the owning map if it already
has
- // one, otherwise creating a new one according to flag.
+ // Return a transition array, using the array from the owning map if it
+ // already has one (copying into a larger array if necessary), otherwise
+ // creating a new one according to flag.
// TODO(verwaest): This should not cause an existing transition to be
// overwritten.
- static Handle<TransitionArray> CopyInsert(Handle<Map> map,
- Handle<Name> name,
- Handle<Map> target,
- SimpleTransitionFlag flag);
+ static Handle<TransitionArray> Insert(Handle<Map> map, Handle<Name> name,
+ Handle<Map> target,
+ SimpleTransitionFlag flag);
// Search a transition for a given property name.
inline int Search(Name* name);
// Allocates a TransitionArray.
- static Handle<TransitionArray> Allocate(
- Isolate* isolate, int number_of_transitions);
+ static Handle<TransitionArray> Allocate(Isolate* isolate,
+ int number_of_transitions,
+ int slack = 0);
bool IsSimpleTransition() {
return length() == kSimpleTransitionSize &&
@@ -120,7 +133,8 @@
// Layout for full transition arrays.
static const int kPrototypeTransitionsIndex = 1;
- static const int kFirstIndex = 2;
+ static const int kTransitionLengthIndex = 2;
+ static const int kFirstIndex = 3;
// Layout for simple transition arrays.
static const int kSimpleTransitionTarget = 1;
@@ -133,6 +147,8 @@
// Layout for the full transition array header.
static const int kPrototypeTransitionsOffset = kBackPointerStorageOffset
+
kPointerSize;
+ static const int kTransitionLengthOffset =
+ kPrototypeTransitionsOffset + kPointerSize;
// Layout of map transition entries in full transition arrays.
static const int kTransitionKey = 0;
@@ -156,6 +172,12 @@
// The maximum number of transitions we want in a transition array
(should
// fit in a page).
static const int kMaxNumberOfTransitions = 1024 + 512;
+
+ // Returns the fixed array length required to hold number_of_transitions
+ // transitions.
+ static int LengthFor(int number_of_transitions) {
+ return ToKeyIndex(number_of_transitions);
+ }
private:
// Conversion from transition number to array indices.
=======================================
--- /branches/bleeding_edge/test/cctest/test-heap.cc Fri Oct 31 14:51:48
2014 UTC
+++ /branches/bleeding_edge/test/cctest/test-heap.cc Mon Nov 3 16:44:58
2014 UTC
@@ -2940,6 +2940,7 @@
"root = new F");
root = GetByName("root");
AddPropertyTo(2, root, "funny");
+ CcTest::heap()->CollectGarbage(NEW_SPACE);
// Count number of live transitions after marking. Note that one
transition
// is left, because 'o' still holds an instance of one transition target.
@@ -2966,6 +2967,7 @@
root = GetByName("root");
AddPropertyTo(2, root, "funny");
+ CcTest::heap()->CollectGarbage(NEW_SPACE);
// Count number of live transitions after marking. Note that one
transition
// is left, because 'o' still holds an instance of one transition target.
--
--
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.
