Improved performance of Array.prototype.concat by moving the implementation to C++ (issue 123).
Fixed heap growth policy to avoid growing old space to its maximum capacity before doing a garbage collection and fixed issue that would lead to artificial out of memory situations (issue 129).
Fixed Date.prototype.toLocaleDateString to return the date in the same format as WebKit.
Added missing initialization checks to debugger API.
Added removing of unused maps during GC.
git-svn-id: http://v8.googlecode.com/svn/trunk@655 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
diff --git a/src/runtime.cc b/src/runtime.cc
index dcd2b01..8459af1 100644
--- a/src/runtime.cc
+++ b/src/runtime.cc
@@ -320,9 +320,19 @@
static Object* Runtime_GetTemplateField(Arguments args) {
ASSERT(args.length() == 2);
CONVERT_CHECKED(HeapObject, templ, args[0]);
- RUNTIME_ASSERT(templ->IsStruct());
CONVERT_CHECKED(Smi, field, args[1]);
- return HeapObject::GetHeapObjectField(templ, field->value());
+ int index = field->value();
+ int offset = index * kPointerSize + HeapObject::kHeaderSize;
+ InstanceType type = templ->map()->instance_type();
+ RUNTIME_ASSERT(type == FUNCTION_TEMPLATE_INFO_TYPE ||
+ type == OBJECT_TEMPLATE_INFO_TYPE);
+ RUNTIME_ASSERT(offset > 0);
+ if (type == FUNCTION_TEMPLATE_INFO_TYPE) {
+ RUNTIME_ASSERT(offset < FunctionTemplateInfo::kSize);
+ } else {
+ RUNTIME_ASSERT(offset < ObjectTemplateInfo::kSize);
+ }
+ return *HeapObject::RawField(templ, offset);
}
@@ -3429,8 +3439,8 @@
// If the holder is found, we read the property from it.
if (!holder.is_null() && holder->IsJSObject()) {
+ ASSERT(Handle<JSObject>::cast(holder)->HasProperty(*name));
JSObject* object = JSObject::cast(*holder);
- ASSERT(object->HasProperty(*name));
JSObject* receiver = (object->IsGlobalObject())
? GlobalObject::cast(object)->global_receiver()
: ComputeReceiverForNonGlobal(object);
@@ -3987,6 +3997,253 @@
}
+/**
+ * A simple visitor visits every element of Array's.
+ * The backend storage can be a fixed array for fast elements case,
+ * or a dictionary for sparse array. Since Dictionary is a subtype
+ * of FixedArray, the class can be used by both fast and slow cases.
+ * The second parameter of the constructor, fast_elements, specifies
+ * whether the storage is a FixedArray or Dictionary.
+ *
+ * An index limit is used to deal with the situation that a result array
+ * length overflows 32-bit non-negative integer.
+ */
+class ArrayConcatVisitor {
+ public:
+ ArrayConcatVisitor(Handle<FixedArray> storage,
+ uint32_t index_limit,
+ bool fast_elements) :
+ storage_(storage), index_limit_(index_limit),
+ fast_elements_(fast_elements), index_offset_(0) { }
+
+ void visit(uint32_t i, Handle<Object> elm) {
+ uint32_t index = i + index_offset_;
+ if (index >= index_limit_) return;
+
+ if (fast_elements_) {
+ ASSERT(index < static_cast<uint32_t>(storage_->length()));
+ storage_->set(index, *elm);
+
+ } else {
+ Handle<Dictionary> dict = Handle<Dictionary>::cast(storage_);
+ Handle<Dictionary> result =
+ Factory::DictionaryAtNumberPut(dict, index, elm);
+ if (!result.is_identical_to(dict))
+ storage_ = result;
+ }
+ }
+
+ void increase_index_offset(uint32_t delta) {
+ index_offset_ += delta;
+ }
+
+ private:
+ Handle<FixedArray> storage_;
+ uint32_t index_limit_;
+ bool fast_elements_;
+ uint32_t index_offset_;
+};
+
+
+/**
+ * A helper function that visits elements of a JSObject. Only elements
+ * whose index between 0 and range (exclusive) are visited.
+ *
+ * If the third parameter, visitor, is not NULL, the visitor is called
+ * with parameters, 'visitor_index_offset + element index' and the element.
+ *
+ * It returns the number of visisted elements.
+ */
+static uint32_t IterateElements(Handle<JSObject> receiver,
+ uint32_t range,
+ ArrayConcatVisitor* visitor) {
+ uint32_t num_of_elements = 0;
+
+ if (receiver->HasFastElements()) {
+ Handle<FixedArray> elements(FixedArray::cast(receiver->elements()));
+ uint32_t len = elements->length();
+ if (range < len) len = range;
+
+ for (uint32_t j = 0; j < len; j++) {
+ Handle<Object> e(elements->get(j));
+ if (!e->IsTheHole()) {
+ num_of_elements++;
+ if (visitor)
+ visitor->visit(j, e);
+ }
+ }
+
+ } else {
+ Handle<Dictionary> dict(receiver->element_dictionary());
+ uint32_t capacity = dict->Capacity();
+ for (uint32_t j = 0; j < capacity; j++) {
+ Handle<Object> k(dict->KeyAt(j));
+ if (dict->IsKey(*k)) {
+ ASSERT(k->IsNumber());
+ uint32_t index = static_cast<uint32_t>(k->Number());
+ if (index < range) {
+ num_of_elements++;
+ if (visitor) {
+ visitor->visit(index,
+ Handle<Object>(dict->ValueAt(j)));
+ }
+ }
+ }
+ }
+ }
+
+ return num_of_elements;
+}
+
+
+/**
+ * A helper function that visits elements of an Array object, and elements
+ * on its prototypes.
+ *
+ * Elements on prototypes are visited first, and only elements whose indices
+ * less than Array length are visited.
+ *
+ * If a ArrayConcatVisitor object is given, the visitor is called with
+ * parameters, element's index + visitor_index_offset and the element.
+ */
+static uint32_t IterateArrayAndPrototypeElements(Handle<JSArray> array,
+ ArrayConcatVisitor* visitor) {
+ uint32_t range = static_cast<uint32_t>(array->length()->Number());
+ Handle<Object> obj = array;
+
+ static const int kEstimatedPrototypes = 3;
+ List< Handle<JSObject> > objects(kEstimatedPrototypes);
+
+ // Visit prototype first. If an element on the prototype is shadowed by
+ // the inheritor using the same index, the ArrayConcatVisitor visits
+ // the prototype element before the shadowing element.
+ // The visitor can simply overwrite the old value by new value using
+ // the same index. This follows Array::concat semantics.
+ while (!obj->IsNull()) {
+ objects.Add(Handle<JSObject>::cast(obj));
+ obj = Handle<Object>(obj->GetPrototype());
+ }
+
+ uint32_t nof_elements = 0;
+ for (int i = objects.length() - 1; i >= 0; i--) {
+ Handle<JSObject> obj = objects[i];
+ nof_elements +=
+ IterateElements(Handle<JSObject>::cast(obj), range, visitor);
+ }
+
+ return nof_elements;
+}
+
+
+/**
+ * A helper function of Runtime_ArrayConcat.
+ *
+ * The first argument is an Array of arrays and objects. It is the
+ * same as the arguments array of Array::concat JS function.
+ *
+ * If an argument is an Array object, the function visits array
+ * elements. If an argument is not an Array object, the function
+ * visits the object as if it is an one-element array.
+ *
+ * If the result array index overflows 32-bit integer, the rounded
+ * non-negative number is used as new length. For example, if one
+ * array length is 2^32 - 1, second array length is 1, the
+ * concatenated array length is 0.
+ */
+static uint32_t IterateArguments(Handle<JSArray> arguments,
+ ArrayConcatVisitor* visitor) {
+ uint32_t visited_elements = 0;
+ uint32_t num_of_args = static_cast<uint32_t>(arguments->length()->Number());
+
+ for (uint32_t i = 0; i < num_of_args; i++) {
+ Handle<Object> obj(arguments->GetElement(i));
+ if (obj->IsJSArray()) {
+ Handle<JSArray> array = Handle<JSArray>::cast(obj);
+ uint32_t len = static_cast<uint32_t>(array->length()->Number());
+ uint32_t nof_elements =
+ IterateArrayAndPrototypeElements(array, visitor);
+ // Total elements of array and its prototype chain can be more than
+ // the array length, but ArrayConcat can only concatenate at most
+ // the array length number of elements.
+ visited_elements += (nof_elements > len) ? len : nof_elements;
+ if (visitor) visitor->increase_index_offset(len);
+
+ } else {
+ if (visitor) {
+ visitor->visit(0, obj);
+ visitor->increase_index_offset(1);
+ }
+ visited_elements++;
+ }
+ }
+ return visited_elements;
+}
+
+
+/**
+ * Array::concat implementation.
+ * See ECMAScript 262, 15.4.4.4.
+ */
+static Object* Runtime_ArrayConcat(Arguments args) {
+ ASSERT(args.length() == 1);
+ HandleScope handle_scope;
+
+ CONVERT_CHECKED(JSArray, arg_arrays, args[0]);
+ Handle<JSArray> arguments(arg_arrays);
+
+ // Pass 1: estimate the number of elements of the result
+ // (it could be more than real numbers if prototype has elements).
+ uint32_t result_length = 0;
+ uint32_t num_of_args = static_cast<uint32_t>(arguments->length()->Number());
+
+ { AssertNoAllocation nogc;
+ for (uint32_t i = 0; i < num_of_args; i++) {
+ Object* obj = arguments->GetElement(i);
+ if (obj->IsJSArray()) {
+ result_length +=
+ static_cast<uint32_t>(JSArray::cast(obj)->length()->Number());
+ } else {
+ result_length++;
+ }
+ }
+ }
+
+ // Allocate an empty array, will set length and content later.
+ Handle<JSArray> result = Factory::NewJSArray(0);
+
+ uint32_t estimate_nof_elements = IterateArguments(arguments, NULL);
+ // If estimated number of elements is more than half of length, a
+ // fixed array (fast case) is more time and space-efficient than a
+ // dictionary.
+ bool fast_case = (estimate_nof_elements * 2) >= result_length;
+
+ Handle<FixedArray> storage;
+ if (fast_case) {
+ // The backing storage array must have non-existing elements to
+ // preserve holes across concat operations.
+ storage = Factory::NewFixedArrayWithHoles(result_length);
+
+ } else {
+ // TODO(126): move 25% pre-allocation logic into Dictionary::Allocate
+ uint32_t at_least_space_for = estimate_nof_elements +
+ (estimate_nof_elements >> 2);
+ storage = Handle<FixedArray>::cast(
+ Factory::NewDictionary(at_least_space_for));
+ }
+
+ Handle<Object> len = Factory::NewNumber(static_cast<double>(result_length));
+
+ ArrayConcatVisitor visitor(storage, result_length, fast_case);
+
+ IterateArguments(arguments, &visitor);
+
+ result->set_length(*len);
+ result->set_elements(*storage);
+
+ return *result;
+}
+
+
// This will not allocate (flatten the string), but it may run
// very slowly for very deeply nested ConsStrings. For debugging use only.
static Object* Runtime_GlobalPrint(Arguments args) {
@@ -5523,9 +5780,16 @@
void Runtime::PerformGC(Object* result) {
Failure* failure = Failure::cast(result);
- // Try to do a garbage collection; ignore it if it fails. The C
- // entry stub will throw an out-of-memory exception in that case.
- Heap::CollectGarbage(failure->requested(), failure->allocation_space());
+ if (failure->IsRetryAfterGC()) {
+ // Try to do a garbage collection; ignore it if it fails. The C
+ // entry stub will throw an out-of-memory exception in that case.
+ Heap::CollectGarbage(failure->requested(), failure->allocation_space());
+ } else {
+ // Handle last resort GC and make sure to allow future allocations
+ // to grow the heap without causing GCs (if possible).
+ Counters::gc_last_resort_from_js.Increment();
+ Heap::CollectAllGarbage();
+ }
}