From 4c1a5810b9b2aae078ab2457732f544dceb97df8 Mon Sep 17 00:00:00 2001 From: "feng@chromium.org" Date: Tue, 28 Oct 2008 14:47:50 +0000 Subject: [PATCH] Implement Array::concat function in C++. The performance of Array::concat is critical of jQuery benchmark from http://www.dromaeo.com. Our current implementation in JavaScript is very generic and is several times slower than JSC and SpiderMonkey. Re-implement Array::concat in C++ to take advantage of underlying implementation details. This cuts dom-travesal-jquery execution time by half. We may want to move Array specific implementation into a separate source file, say jsarray.cc. Review URL: http://codereview.chromium.org/7990 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@625 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/array.js | 47 ++------- src/factory.cc | 6 ++ src/factory.h | 1 + src/objects.cc | 2 +- src/runtime.cc | 231 +++++++++++++++++++++++++++++++++++++++++++ src/runtime.h | 1 + test/mjsunit/array-concat.js | 8 ++ 7 files changed, 255 insertions(+), 41 deletions(-) diff --git a/src/array.js b/src/array.js index c183159..3355c94 100644 --- a/src/array.js +++ b/src/array.js @@ -373,48 +373,15 @@ function ArrayPush() { function ArrayConcat(arg1) { // length == 1 - var arg_number = 0, arg_count = %_ArgumentsLength(); - var n = 0; - - var A = $Array(1 + arg_count); - var E = this; - - while (true) { - if (IS_ARRAY(E)) { - // This is an array of intervals or an array of keys. Keys are - // represented by non-negative integers. Intervals are represented by - // negative integers, followed by positive counts. The interval start - // is determined by subtracting the entry from -1. There may also be - // undefined entries in the array which should be skipped. - var intervals = %GetArrayKeys(E, E.length); - var length = intervals.length; - for (var k = 0; k < length; k++) { - var key = intervals[k]; - if (key < 0) { - var j = -1 - key; - var limit = j + intervals[++k]; - for (; j < limit; j++) { - if (j in E) { - A[n + j] = E[j]; - } - } - } else { - // The case where key is undefined also ends here. - if (!IS_UNDEFINED(key)) { - A[n + key] = E[key]; - } - } - } - n += E.length; - } else { - A[n++] = E; - } - if (arg_number == arg_count) break; - E = %_Arguments(arg_number++); + // TODO: can we just use arguments? + var arg_count = %_ArgumentsLength(); + var arrays = new $Array(1 + arg_count); + arrays[0] = this; + for (var i = 0; i < arg_count; i++) { + arrays[i + 1] = %_Arguments(i); } - A.length = n; // may contain empty arrays - return A; + return %ArrayConcat(arrays); } diff --git a/src/factory.cc b/src/factory.cc index 435f4c1..9db9fbb 100644 --- a/src/factory.cc +++ b/src/factory.cc @@ -42,6 +42,12 @@ Handle Factory::NewFixedArray(int size, PretenureFlag pretenure) { } +Handle Factory::NewDictionary(int at_least_space_for) { + ASSERT(0 <= at_least_space_for); + CALL_HEAP_FUNCTION(Dictionary::Allocate(at_least_space_for), Dictionary); +} + + Handle Factory::NewDescriptorArray(int number_of_descriptors) { ASSERT(0 <= number_of_descriptors); CALL_HEAP_FUNCTION(DescriptorArray::Allocate(number_of_descriptors), diff --git a/src/factory.h b/src/factory.h index bb04b6b..abd84d3 100644 --- a/src/factory.h +++ b/src/factory.h @@ -41,6 +41,7 @@ class Factory : public AllStatic { static Handle NewFixedArray( int size, PretenureFlag pretenure = NOT_TENURED); + static Handle NewDictionary(int at_least_space_for); static Handle NewDescriptorArray(int number_of_descriptors); diff --git a/src/objects.cc b/src/objects.cc index e33d12e..7c2c55d 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -5751,7 +5751,7 @@ Object* HashTable::EnsureCapacity( int n, HashTableKey* key) { int capacity = Capacity(); int nof = NumberOfElements() + n; - // Make sure 20% is free + // Make sure 25% is free if (nof + (nof >> 2) <= capacity) return this; Object* obj = Allocate(nof * 2); diff --git a/src/runtime.cc b/src/runtime.cc index dcd2b01..1739b3e 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -3987,6 +3987,237 @@ static Object* Runtime_PushIfAbsent(Arguments args) { } +/** + * 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. + */ +class ArrayConcatVisitor { + public: + ArrayConcatVisitor(Handle storage, bool fast_elements) + : storage_(storage), fast_elements_(fast_elements), index_offset_(0) { } + + void visit(uint32_t i, Handle elm) { + uint32_t index = i + index_offset_; + + if (fast_elements_) { + ASSERT(index < static_cast(storage_->length())); + storage_->set(index, *elm); + + } else { + Handle dict = Handle::cast(storage_); + Handle 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 storage_; + 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 receiver, + uint32_t range, + ArrayConcatVisitor* visitor) { + uint32_t num_of_elements = 0; + + if (receiver->HasFastElements()) { + Handle elements(FixedArray::cast(receiver->elements())); + uint32_t len = elements->length(); + if (range < len) len = range; + + for (uint32_t j = 0; j < len; j++) { + Handle e(elements->get(j)); + if (!e->IsTheHole()) { + num_of_elements++; + if (visitor) + visitor->visit(j, e); + } + } + + } else { + Handle dict(receiver->element_dictionary()); + uint32_t capacity = dict->Capacity(); + for (uint32_t j = 0; j < capacity; j++) { + Handle k(dict->KeyAt(j)); + if (dict->IsKey(*k)) { + ASSERT(k->IsNumber()); + uint32_t index = static_cast(k->Number()); + if (index < range) { + num_of_elements++; + if (visitor) { + visitor->visit(index, + Handle(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 array, + ArrayConcatVisitor* visitor) { + uint32_t range = static_cast(array->length()->Number()); + Handle obj = array; + + static const int kEstimatedPrototypes = 3; + List< Handle > 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(obj); + obj = Handle(obj->GetPrototype()); + } + + uint32_t nof_elements = 0; + for (int i = objects.length() - 1; i >= 0; i--) { + Handle obj = objects[i]; + nof_elements += + IterateElements(Handle::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. + */ +static uint32_t IterateArguments(Handle arguments, + ArrayConcatVisitor* visitor) { + uint32_t visited_elements = 0; + uint32_t num_of_args = static_cast(arguments->length()->Number()); + + for (uint32_t i = 0; i < num_of_args; i++) { + Handle obj(arguments->GetElement(i)); + if (obj->IsJSArray()) { + Handle array = Handle::cast(obj); + uint32_t len = static_cast(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 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(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(JSArray::cast(obj)->length()->Number()); + } else { + result_length++; + } + } + } + + // Allocate an empty array, will set length and content later. + Handle 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 & space-efficient than a dictionary. + bool fast_case = (estimate_nof_elements * 2) >= result_length; + + Handle storage; + if (fast_case) { + storage = Factory::NewFixedArray(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::cast( + Factory::NewDictionary(at_least_space_for)); + } + + Handle len = Factory::NewNumber(static_cast(result_length)); + + ArrayConcatVisitor visitor(storage, 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) { diff --git a/src/runtime.h b/src/runtime.h index 463698c..25931d9 100644 --- a/src/runtime.h +++ b/src/runtime.h @@ -64,6 +64,7 @@ namespace v8 { namespace internal { \ /* Array join support */ \ F(PushIfAbsent, 2) \ + F(ArrayConcat, 1) \ \ /* ConsStrings */ \ F(ConsStringFst, 1) \ diff --git a/test/mjsunit/array-concat.js b/test/mjsunit/array-concat.js index bb8c570..22e02a1 100644 --- a/test/mjsunit/array-concat.js +++ b/test/mjsunit/array-concat.js @@ -67,6 +67,14 @@ while (pos = poses.shift()) { assertEquals("undefined", typeof(a[123])); assertEquals("baz", c[123]); + // If the element of prototype is shadowed, the element on the instance + // should be copied, but not the one on the prototype. + Array.prototype[123] = 'baz'; + a[123] = 'xyz'; + assertEquals('xyz', a[123]); + c = a.concat(b); + assertEquals('xyz', c[123]); + // Non-numeric properties on the prototype or the array shouldn't get // copied. Array.prototype.moe = 'joe'; -- 2.7.4