Revision: 24857
Author: [email protected]
Date: Fri Oct 24 05:29:54 2014 UTC
Log: Limit the number of transitions allowed per hidden class.
Each time a transition is added to a hidden class, the whole
transitions array must be copied, which causes poor performance
in some circumstances. This change limits the maximum size of
the transition array, avoiding this behavior in the pathological
case. For example, this improves the performance of the EtchMark
benchmark by nearly 60%.
BUG=v8:3616
LOG=
[email protected], [email protected]
Review URL: https://codereview.chromium.org/635883003
Patch from Kevin M. McCormick <[email protected]>.
https://code.google.com/p/v8/source/detail?r=24857
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 21 09:42:16
2014 UTC
+++ /branches/bleeding_edge/src/heap/mark-compact.cc Fri Oct 24 05:29:54
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 Thu Oct 23 05:57:01 2014 UTC
+++ /branches/bleeding_edge/src/objects-inl.h Fri Oct 24 05:29:54 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;
}
@@ -6993,6 +6992,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;
+ DCHECK(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 Thu Oct 23 18:21:50 2014 UTC
+++ /branches/bleeding_edge/src/objects.cc Fri Oct 24 05:29:54 2014 UTC
@@ -6592,7 +6592,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());
}
}
@@ -6617,8 +6618,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);
}
}
=======================================
--- /branches/bleeding_edge/src/objects.h Thu Oct 23 18:21:50 2014 UTC
+++ /branches/bleeding_edge/src/objects.h Fri Oct 24 05:29:54 2014 UTC
@@ -6119,6 +6119,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 Thu Oct 23 11:31:33 2014
UTC
+++ /branches/bleeding_edge/src/transitions-inl.h Fri Oct 24 05:29:54 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 Aug 4 11:34:54 2014 UTC
+++ /branches/bleeding_edge/src/transitions.cc Fri Oct 24 05:29:54 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;
+ DCHECK(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 Thu Oct 23 11:31:33 2014 UTC
+++ /branches/bleeding_edge/src/transitions.h Fri Oct 24 05:29:54 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 Tue Oct 21 09:42:16
2014 UTC
+++ /branches/bleeding_edge/test/cctest/test-heap.cc Fri Oct 24 05:29:54
2014 UTC
@@ -2848,6 +2848,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.
@@ -2874,6 +2875,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.
