Revision: 8744
Author: [email protected]
Date: Tue Jul 26 06:56:21 2011
Log: 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]
Review URL: http://codereview.chromium.org/7464032
http://code.google.com/p/v8/source/detail?r=8744
Modified:
/branches/bleeding_edge/src/objects-inl.h
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
/branches/bleeding_edge/src/runtime.cc
=======================================
--- /branches/bleeding_edge/src/objects-inl.h Mon Jul 25 08:01:45 2011
+++ /branches/bleeding_edge/src/objects-inl.h Tue Jul 26 06:56:21 2011
@@ -1964,6 +1964,17 @@
fast_swap(content_array, ToValueIndex(first), ToValueIndex(second));
fast_swap(content_array, ToDetailsIndex(first), ToDetailsIndex(second));
}
+
+
+template<typename Shape, typename Key>
+int HashTable<Shape, Key>::ComputeCapacity(int at_least_space_for) {
+ const int kMinCapacity = 32;
+ int capacity = RoundUpToPowerOf2(at_least_space_for * 2);
+ if (capacity < kMinCapacity) {
+ capacity = kMinCapacity; // Guarantee min capacity.
+ }
+ return capacity;
+}
template<typename Shape, typename Key>
=======================================
--- /branches/bleeding_edge/src/objects.cc Mon Jul 25 08:01:45 2011
+++ /branches/bleeding_edge/src/objects.cc Tue Jul 26 06:56:21 2011
@@ -2899,9 +2899,12 @@
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);
}
@@ -8618,7 +8621,7 @@
} else {
new_length = dictionary->max_number_key() + 1;
}
- MaybeObject* result = ShouldConvertToFastDoubleElements()
+ MaybeObject* result = CanConvertToFastDoubleElements()
? SetFastDoubleElementsCapacityAndLength(new_length, new_length)
: SetFastElementsCapacityAndLength(new_length, new_length);
if (result->IsFailure()) return result;
@@ -9160,7 +9163,15 @@
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;
@@ -9171,34 +9182,33 @@
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:
@@ -9206,31 +9216,34 @@
case EXTERNAL_INT_ELEMENTS:
case EXTERNAL_UNSIGNED_INT_ELEMENTS:
case EXTERNAL_FLOAT_ELEMENTS:
- case EXTERNAL_DOUBLE_ELEMENTS: {
- return true;
- }
- }
- return (capacity == 0) || (number_of_elements > (capacity / 2));
+ case EXTERNAL_DOUBLE_ELEMENTS:
+ case EXTERNAL_PIXEL_ELEMENTS:
+ // External arrays are considered 100% used.
+ ExternalArray* external_array = ExternalArray::cast(elements());
+ *capacity = external_array->length();
+ *used = external_array->length();
+ break;
+ }
}
bool JSObject::ShouldConvertToSlowElements(int new_capacity) {
- if (new_capacity <= kMaxFastElementsLength) 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.
- int old_capacity = 0;
- if (elements()->map() == GetHeap()->non_strict_arguments_elements_map())
{
- FixedArray* backing_store = FixedArray::cast(elements());
- old_capacity = FixedArray::cast(backing_store->get(1))->length();
- } else if (HasFastElements()) {
- old_capacity = FixedArray::cast(elements())->length();
- } else if (HasFastDoubleElements()) {
- old_capacity = FixedDoubleArray::cast(elements())->length();
- } else {
- UNREACHABLE();
- }
- return !HasDenseElements() || ((new_capacity / 2) > old_capacity);
+ STATIC_ASSERT(kMaxUncheckedOldFastElementsLength <=
+ kMaxUncheckedFastElementsLength);
+ if (new_capacity <= kMaxUncheckedOldFastElementsLength ||
+ (new_capacity <= kMaxUncheckedFastElementsLength &&
+ GetHeap()->InNewSpace(this))) {
+ return false;
+ }
+ // If the fast-case backing storage takes up roughly three times as
+ // much space (in machine words) as a dictionary backing storage
+ // would, the object should have slow elements.
+ int old_capacity = 0;
+ int used_elements = 0;
+ GetElementsCapacityAndUsage(&old_capacity, &used_elements);
+ int dictionary_size = NumberDictionary::ComputeCapacity(used_elements) *
+ NumberDictionary::kEntrySize;
+ return 3 * dictionary_size <= new_capacity;
}
@@ -9253,20 +9266,21 @@
// dictionary, we cannot go back to fast case.
if (dictionary->requires_slow_elements()) return false;
// If the dictionary backing storage takes up roughly half as much
- // space as a fast-case backing storage would the array should have
- // fast elements.
- uint32_t length = 0;
+ // space (in machine words) as a fast-case backing storage would,
+ // the object should have fast elements.
+ uint32_t array_size = 0;
if (IsJSArray()) {
- CHECK(JSArray::cast(this)->length()->ToArrayIndex(&length));
+ CHECK(JSArray::cast(this)->length()->ToArrayIndex(&array_size));
} else {
- length = dictionary->max_number_key();
- }
- return static_cast<uint32_t>(dictionary->Capacity()) >=
- (length / (2 * NumberDictionary::kEntrySize));
+ array_size = dictionary->max_number_key();
+ }
+ uint32_t dictionary_size = static_cast<uint32_t>(dictionary->Capacity())
*
+ NumberDictionary::kEntrySize;
+ return 2 * dictionary_size >= array_size;
}
-bool JSObject::ShouldConvertToFastDoubleElements() {
+bool JSObject::CanConvertToFastDoubleElements() {
if (FLAG_unbox_double_arrays) {
ASSERT(HasDictionaryElements());
NumberDictionary* dictionary = NumberDictionary::cast(elements());
@@ -10197,11 +10211,8 @@
template<typename Shape, typename Key>
MaybeObject* HashTable<Shape, Key>::Allocate(int at_least_space_for,
PretenureFlag pretenure) {
- const int kMinCapacity = 32;
- int capacity = RoundUpToPowerOf2(at_least_space_for * 2);
- if (capacity < kMinCapacity) {
- capacity = kMinCapacity; // Guarantee min capacity.
- } else if (capacity > HashTable::kMaxCapacity) {
+ int capacity = ComputeCapacity(at_least_space_for);
+ if (capacity > HashTable::kMaxCapacity) {
return Failure::OutOfMemoryException();
}
=======================================
--- /branches/bleeding_edge/src/objects.h Mon Jul 25 08:01:45 2011
+++ /branches/bleeding_edge/src/objects.h Tue Jul 26 06:56:21 2011
@@ -1654,7 +1654,7 @@
bool ShouldConvertToFastElements();
// Returns true if the elements of JSObject contains only values that
can be
// represented in a FixedDoubleArray.
- bool ShouldConvertToFastDoubleElements();
+ bool CanConvertToFastDoubleElements();
// Tells whether the index'th element is present.
inline bool HasElement(uint32_t index);
@@ -1948,8 +1948,21 @@
// 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;
@@ -2015,6 +2028,9 @@
// 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,
@@ -2491,6 +2507,10 @@
int at_least_space_for,
PretenureFlag pretenure = NOT_TENURED);
+ // Computes the required capacity for a table holding the given
+ // number of elements. May be more than HashTable::kMaxCapacity.
+ static int ComputeCapacity(int at_least_space_for);
+
// Returns the key at entry.
Object* KeyAt(int entry) { return get(EntryToIndex(entry)); }
=======================================
--- /branches/bleeding_edge/src/runtime.cc Mon Jul 25 08:01:45 2011
+++ /branches/bleeding_edge/src/runtime.cc Tue Jul 26 06:56:21 2011
@@ -1666,7 +1666,9 @@
RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpConstructResult) {
ASSERT(args.length() == 3);
CONVERT_SMI_ARG_CHECKED(elements_count, 0);
- if (elements_count > JSArray::kMaxFastElementsLength) {
+ if (elements_count < 0 ||
+ elements_count > FixedArray::kMaxLength ||
+ !Smi::IsValid(elements_count)) {
return isolate->ThrowIllegalOperation();
}
Object* new_object;
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
