Reviewers: danno,
Description:
Improve fast to slow elements conversion:
o Use a more strict limit for old arrays.
o Initial capacity of a slow elements dictionary should be the number
of used elements and not the old array capacity.
[email protected]
Please review this at http://codereview.chromium.org/7464032/
SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files:
M src/objects.h
M src/objects.cc
M src/runtime.cc
Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index
7495d6e7099fcb7e6c8c02a36fc7249fd7e707d8..8479402e4a850a9db55bdb07e054332ad31d0ff3
100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -2896,9 +2896,12 @@ MaybeObject* JSObject::NormalizeElements() {
int length = IsJSArray()
? Smi::cast(JSArray::cast(this)->length())->value()
: array->length();
+ int old_capacity = 0;
+ int used_elements = 0;
+ GetElementsCapacityAndUsage(&old_capacity, &used_elements);
NumberDictionary* dictionary = NULL;
{ Object* object;
- MaybeObject* maybe = NumberDictionary::Allocate(length);
+ MaybeObject* maybe = NumberDictionary::Allocate(used_elements);
if (!maybe->ToObject(&object)) return maybe;
dictionary = NumberDictionary::cast(object);
}
@@ -9083,62 +9086,69 @@ MaybeObject* JSObject::GetExternalElement(uint32_t
index) {
bool JSObject::HasDenseElements() {
int capacity = 0;
- int number_of_elements = 0;
+ int used = 0;
+ GetElementsCapacityAndUsage(&capacity, &used);
+ return (capacity == 0) || (used > (capacity / 2));
+}
+
+
+void JSObject::GetElementsCapacityAndUsage(int* capacity, int* used) {
+ *capacity = 0;
+ *used = 0;
FixedArrayBase* backing_store_base = FixedArrayBase::cast(elements());
FixedArray* backing_store = NULL;
- switch (GetElementsKind()) {
+ ElementsKind kind = GetElementsKind();
+ switch (kind) {
case NON_STRICT_ARGUMENTS_ELEMENTS:
backing_store_base =
FixedArray::cast(FixedArray::cast(backing_store_base)->get(1));
backing_store = FixedArray::cast(backing_store_base);
if (backing_store->IsDictionary()) {
NumberDictionary* dictionary =
NumberDictionary::cast(backing_store);
- capacity = dictionary->Capacity();
- number_of_elements = dictionary->NumberOfElements();
+ *capacity = dictionary->Capacity();
+ *used = dictionary->NumberOfElements();
break;
}
// Fall through.
case FAST_ELEMENTS:
backing_store = FixedArray::cast(backing_store_base);
- capacity = backing_store->length();
- for (int i = 0; i < capacity; ++i) {
- if (!backing_store->get(i)->IsTheHole()) ++number_of_elements;
+ *capacity = backing_store->length();
+ for (int i = 0; i < *capacity; ++i) {
+ if (!backing_store->get(i)->IsTheHole()) ++(*used);
}
break;
case DICTIONARY_ELEMENTS: {
NumberDictionary* dictionary =
NumberDictionary::cast(FixedArray::cast(elements()));
- capacity = dictionary->Capacity();
- number_of_elements = dictionary->NumberOfElements();
+ *capacity = dictionary->Capacity();
+ *used = dictionary->NumberOfElements();
break;
}
case FAST_DOUBLE_ELEMENTS: {
FixedDoubleArray* elms = FixedDoubleArray::cast(elements());
- capacity = elms->length();
- for (int i = 0; i < capacity; i++) {
- if (!elms->is_the_hole(i)) number_of_elements++;
+ *capacity = elms->length();
+ for (int i = 0; i < *capacity; i++) {
+ if (!elms->is_the_hole(i)) ++(*used);
}
break;
}
- case EXTERNAL_PIXEL_ELEMENTS:
- case EXTERNAL_BYTE_ELEMENTS:
- case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
- case EXTERNAL_SHORT_ELEMENTS:
- case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
- case EXTERNAL_INT_ELEMENTS:
- case EXTERNAL_UNSIGNED_INT_ELEMENTS:
- case EXTERNAL_FLOAT_ELEMENTS:
- case EXTERNAL_DOUBLE_ELEMENTS: {
- return true;
- }
+ default:
+ ASSERT(FIRST_EXTERNAL_ARRAY_ELEMENTS_KIND <= kind &&
+ kind <= LAST_EXTERNAL_ARRAY_ELEMENTS_KIND);
+ break;
}
- return (capacity == 0) || (number_of_elements > (capacity / 2));
}
bool JSObject::ShouldConvertToSlowElements(int new_capacity) {
- if (new_capacity <= kMaxFastElementsLength) return false;
+ STATIC_ASSERT(kMaxUncheckedOldFastElementsLength <=
+ kMaxUncheckedFastElementsLength);
+ if (new_capacity <= kMaxUncheckedOldFastElementsLength ||
+ (new_capacity <= kMaxUncheckedFastElementsLength &&
+ GetHeap()->InNewSpace(this))) {
+ return false;
+ }
// Keep the array in fast case if the current backing storage is
// almost filled and if the new capacity is no more than twice the
// old capacity.
Index: src/objects.h
diff --git a/src/objects.h b/src/objects.h
index
9b55ea747545799a7f35aa4948bdcfad46dccd0b..020019da978d9ddd65f61028834bb6611fb2a147
100644
--- a/src/objects.h
+++ b/src/objects.h
@@ -1946,8 +1946,21 @@ class JSObject: public JSReceiver {
// Also maximal value of JSArray's length property.
static const uint32_t kMaxElementCount = 0xffffffffu;
+ // Constants for heuristics controlling conversion of fast elements
+ // to slow elements.
+
+ // Maximal gap that can be introduced by adding an element beyond
+ // the current elements length.
static const uint32_t kMaxGap = 1024;
- static const int kMaxFastElementsLength = 5000;
+
+ // Maximal length of fast elements array that won't be checked for
+ // being dense enough on expansion.
+ static const int kMaxUncheckedFastElementsLength = 5000;
+
+ // Same as above but for old arrays. This limit is more strict. We
+ // don't want to be wasteful with long lived objects.
+ static const int kMaxUncheckedOldFastElementsLength = 500;
+
static const int kInitialMaxFastElementArray = 100000;
static const int kMaxFastProperties = 12;
static const int kMaxInstanceSize = 255 * kPointerSize;
@@ -2013,6 +2026,9 @@ class JSObject: public JSReceiver {
// Returns true if most of the elements backing storage is used.
bool HasDenseElements();
+ // Gets the current elements capacity and the number of used elements.
+ void GetElementsCapacityAndUsage(int* capacity, int* used);
+
bool CanSetCallback(String* name);
MUST_USE_RESULT MaybeObject* SetElementCallback(
uint32_t index,
Index: src/runtime.cc
diff --git a/src/runtime.cc b/src/runtime.cc
index
2cf8aba18e8413e814c1d4d42608cfc4250abf04..4d43c52c9ac05f3abda62b65dcc34f667f092b8a
100644
--- a/src/runtime.cc
+++ b/src/runtime.cc
@@ -1666,7 +1666,7 @@ RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpExec) {
RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpConstructResult) {
ASSERT(args.length() == 3);
CONVERT_SMI_ARG_CHECKED(elements_count, 0);
- if (elements_count > JSArray::kMaxFastElementsLength) {
+ if (elements_count > JSArray::kMaxUncheckedFastElementsLength) {
return isolate->ThrowIllegalOperation();
}
Object* new_object;
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
