[array] Move Array#sort pre-processing to Torque
This CL removes the "PrepareElementsForSort" runtime function, and
replaces it with a simpler version in Torque. The biggest difference
is that certain sparse configurations no longer have a fast-path.
The Torque pre-processing step replaces the existing Torque mechanism that
copied already pre-processed elements into the "work" FixedArray. The Torque
compacting works as follows:
- Iterate all elements from 0 to {length}
- If the element is the hole: Do nothing.
- If the element is "undefined": Increment undefined counter.
- In all other cases, push the element into the "work" FixedArray.
Then the "work" FixedArray is sorted as before. Writing the elements from
the "work" array back into the receiver, after sorting, has three steps:
1. Copy the sorted elements from the "work" FixedArray to the receiver.
2. Add previously counted number of "undefined" to the receiver.
3. Depending on the backing store either delete properties or
set them to the Hole up to {length}.
Bug: v8:8714
Change-Id: I14eccb7cfd2e4618bce2a85cba0689d7e0380ad2
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1619756
Commit-Queue: Simon Zünd <szuend@chromium.org>
Reviewed-by: Tobias Tebbi <tebbi@chromium.org>
Reviewed-by: Jakob Gruber <jgruber@chromium.org>
Cr-Commit-Position: refs/heads/master@{#61812}
diff --git a/src/builtins/base.tq b/src/builtins/base.tq
index cdfb23f..898bffb 100644
--- a/src/builtins/base.tq
+++ b/src/builtins/base.tq
@@ -1024,6 +1024,7 @@
constexpr int31 generates 'V8_TYPED_ARRAY_MAX_SIZE_IN_HEAP';
const kMaxSafeInteger: constexpr float64 generates 'kMaxSafeInteger';
const kSmiMaxValue: constexpr uintptr generates 'kSmiMaxValue';
+const kSmiMax: uintptr = kSmiMaxValue;
const kStringMaxLength: constexpr int31 generates 'String::kMaxLength';
const kFixedArrayMaxLength:
constexpr int31 generates 'FixedArray::kMaxLength';
diff --git a/src/debug/debug-evaluate.cc b/src/debug/debug-evaluate.cc
index 3f7e4f68..a4960cd1 100644
--- a/src/debug/debug-evaluate.cc
+++ b/src/debug/debug-evaluate.cc
@@ -263,7 +263,6 @@
V(HasFastPackedElements) \
V(NewArray) \
V(NormalizeElements) \
- V(PrepareElementsForSort) \
V(TypedArrayGetBuffer) \
/* Errors */ \
V(NewTypeError) \
@@ -513,7 +512,6 @@
case Builtins::kArrayPrototypeKeys:
case Builtins::kArrayPrototypeLastIndexOf:
case Builtins::kArrayPrototypeSlice:
- case Builtins::kArrayPrototypeSort:
case Builtins::kArrayPrototypeToLocaleString:
case Builtins::kArrayPrototypeToString:
case Builtins::kArrayForEach:
@@ -787,6 +785,7 @@
case Builtins::kArrayPrototypeReverse:
case Builtins::kArrayPrototypeShift:
case Builtins::kArrayPrototypeUnshift:
+ case Builtins::kArrayPrototypeSort:
case Builtins::kArrayPrototypeSplice:
case Builtins::kArrayUnshift:
// Map builtins.
diff --git a/src/objects/fixed-array.h b/src/objects/fixed-array.h
index 0216767..5896f41 100644
--- a/src/objects/fixed-array.h
+++ b/src/objects/fixed-array.h
@@ -140,8 +140,6 @@
inline ObjectSlot GetFirstElementAddress();
inline bool ContainsOnlySmisOrHoles();
- // Returns true iff the elements are Numbers and sorted ascending.
- bool ContainsSortedNumbers();
// Gives access to raw memory which stores the array's data.
inline ObjectSlot data_start();
diff --git a/src/objects/js-objects.cc b/src/objects/js-objects.cc
index 2f7e179..3fe98c9 100644
--- a/src/objects/js-objects.cc
+++ b/src/objects/js-objects.cc
@@ -1963,17 +1963,6 @@
try_fast_path, true);
}
-Handle<FixedArray> JSReceiver::GetOwnElementIndices(Isolate* isolate,
- Handle<JSReceiver> receiver,
- Handle<JSObject> object) {
- KeyAccumulator accumulator(isolate, KeyCollectionMode::kOwnOnly,
- ALL_PROPERTIES);
- accumulator.CollectOwnElementIndices(receiver, object);
- Handle<FixedArray> keys =
- accumulator.GetKeys(GetKeysConversion::kKeepNumbers);
- DCHECK(keys->ContainsSortedNumbers());
- return keys;
-}
Maybe<bool> JSReceiver::SetPrototype(Handle<JSReceiver> object,
Handle<Object> value, bool from_javascript,
ShouldThrow should_throw) {
diff --git a/src/objects/js-objects.h b/src/objects/js-objects.h
index 361c74b..b9a7014 100644
--- a/src/objects/js-objects.h
+++ b/src/objects/js-objects.h
@@ -259,9 +259,6 @@
Handle<JSReceiver> object, PropertyFilter filter,
bool try_fast_path = true);
- V8_WARN_UNUSED_RESULT static Handle<FixedArray> GetOwnElementIndices(
- Isolate* isolate, Handle<JSReceiver> receiver, Handle<JSObject> object);
-
static const int kHashMask = PropertyArray::HashField::kMask;
DEFINE_FIELD_OFFSET_CONSTANTS(HeapObject::kHeaderSize,
diff --git a/src/objects/objects.cc b/src/objects/objects.cc
index 5969435..fece0b5 100644
--- a/src/objects/objects.cc
+++ b/src/objects/objects.cc
@@ -3811,20 +3811,6 @@
return new_array;
}
-bool FixedArray::ContainsSortedNumbers() {
- for (int i = 1; i < length(); ++i) {
- Object a_obj = get(i - 1);
- Object b_obj = get(i);
- if (!a_obj.IsNumber() || !b_obj.IsNumber()) return false;
-
- uint32_t a = NumberToUint32(a_obj);
- uint32_t b = NumberToUint32(b_obj);
-
- if (a > b) return false;
- }
- return true;
-}
-
Handle<FixedArray> FixedArray::ShrinkOrEmpty(Isolate* isolate,
Handle<FixedArray> array,
int new_length) {
diff --git a/src/runtime/runtime-array.cc b/src/runtime/runtime-array.cc
index a7d10c7..ef5275d 100644
--- a/src/runtime/runtime-array.cc
+++ b/src/runtime/runtime-array.cc
@@ -15,7 +15,6 @@
#include "src/objects/elements.h"
#include "src/objects/hash-table-inl.h"
#include "src/objects/js-array-inl.h"
-#include "src/objects/keys.h"
#include "src/objects/prototype.h"
#include "src/runtime/runtime-utils.h"
@@ -42,386 +41,6 @@
return *object;
}
-namespace {
-// Find the next free position. undefined and holes are both considered
-// free spots. Returns "Nothing" if an exception occurred.
-V8_WARN_UNUSED_RESULT
-Maybe<uint32_t> FindNextFreePosition(Isolate* isolate,
- Handle<JSReceiver> receiver,
- uint32_t current_pos) {
- for (uint32_t position = current_pos;; ++position) {
- Maybe<bool> has_element = JSReceiver::HasOwnProperty(receiver, position);
- MAYBE_RETURN(has_element, Nothing<uint32_t>());
- if (!has_element.FromJust()) return Just(position);
-
- Handle<Object> element;
- ASSIGN_RETURN_ON_EXCEPTION_VALUE(
- isolate, element, JSReceiver::GetElement(isolate, receiver, position),
- Nothing<uint32_t>());
- if (element->IsUndefined(isolate)) return Just(position);
- }
-}
-
-// As RemoveArrayHoles, but also handles Dictionary elements that stay
-// Dictionary (requires_slow_elements() is true), proxies and objects that
-// might have accessors.
-V8_WARN_UNUSED_RESULT
-Object RemoveArrayHolesGeneric(Isolate* isolate, Handle<JSReceiver> receiver,
- uint32_t limit) {
- HandleScope scope(isolate);
-
- // For proxies, we do not collect the keys, instead we use all indices in
- // the full range of [0, limit).
- Handle<FixedArray> keys;
- if (!receiver->IsJSProxy()) {
- keys = JSReceiver::GetOwnElementIndices(isolate, receiver,
- Handle<JSObject>::cast(receiver));
- }
-
- uint32_t num_undefined = 0;
- uint32_t current_pos = 0;
- uint32_t num_indices = keys.is_null() ? limit : keys->length();
-
- // Compact keys with undefined values and moves non-undefined
- // values to the front.
- // The loop does two things simultaneously:
- // (1) Count the number of 'undefined', i.e.
- // i.e.: HasProperty(receiver, key) && Get(receiver, key) == undefined
- // (2) Move all non-undefined values to the front. The variable current_pos
- // is used to track free spots in the array starting at the beginning.
- // Holes and 'undefined' are considered free spots.
- // A hole is when HasElement(receiver, key) is false.
- for (uint32_t i = 0; i < num_indices; ++i) {
- uint32_t key = keys.is_null() ? i : NumberToUint32(keys->get(i));
-
- // We only care about array indices that are smaller than the limit.
- // The keys are sorted, so we can break as soon as we encounter the first.
- if (key >= limit) break;
-
- Maybe<bool> has_element = JSReceiver::HasElement(receiver, key);
- MAYBE_RETURN(has_element, ReadOnlyRoots(isolate).exception());
- if (!has_element.FromJust()) {
- continue;
- }
-
- Handle<Object> element;
- ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
- isolate, element, JSReceiver::GetElement(isolate, receiver, key));
-
- if (element->IsUndefined(isolate)) {
- ++num_undefined;
- } else {
- // Find next free position to move elements to.
- Maybe<uint32_t> free_position =
- FindNextFreePosition(isolate, receiver, current_pos);
- MAYBE_RETURN(free_position, ReadOnlyRoots(isolate).exception());
- current_pos = free_position.FromJust();
-
- // Do not move elements that are already in the "packed" area.
- if (key <= current_pos) continue;
-
- // array[current_pos] = array[key].
- // Deleting array[key] is done later. This is to preserve the same
- // semantics as the old JS implementation when working with non-extensible
- // objects:
- // If the array contains undefineds, the position at 'key' might later
- // bet set to 'undefined'. If we delete the element now and later set it
- // to undefined, the set operation would throw an exception.
- // Instead, to mark it up as a free space, we set array[key] to undefined.
- // As 'key' will be incremented afterward, this undefined value will not
- // affect 'num_undefined', and the logic afterwards will correctly set
- // the remaining undefineds or delete the remaining properties.
- RETURN_FAILURE_ON_EXCEPTION(
- isolate, Object::SetElement(isolate, receiver, current_pos, element,
- ShouldThrow::kThrowOnError));
- RETURN_FAILURE_ON_EXCEPTION(
- isolate, Object::SetElement(isolate, receiver, key,
- isolate->factory()->undefined_value(),
- ShouldThrow::kThrowOnError));
- ++current_pos;
- }
- }
-
- // current_pos points to the next free space in the array/object. In most
- // cases this corresponds to the 'length' or to the number of non-undefined
- // elements.
- // In cases where an object is 'packed' and 'length' is smaller, e.g.:
- // { 0: 5, 1: 4, 2: 3, length: 2 }
- // current_pos will be greater than limit, thus, we need to take the minimum.
- uint32_t result = std::min(current_pos, limit);
-
- // Set [current_pos, current_pos + num_undefined) to undefined.
- for (uint32_t i = 0; i < num_undefined; ++i) {
- RETURN_FAILURE_ON_EXCEPTION(
- isolate, Object::SetElement(isolate, receiver, current_pos++,
- isolate->factory()->undefined_value(),
- ShouldThrow::kThrowOnError));
- }
- // TODO(szuend): Re-enable when we also copy from the prototype chain for
- // JSArrays. Then we can use HasOwnProperty instead of
- // HasElement and this condition will hold.
- // DCHECK_LE(current_pos, num_indices);
-
- // Deleting everything after the undefineds up unto the limit.
- for (uint32_t i = num_indices; i > 0;) {
- --i;
- uint32_t key = keys.is_null() ? i : NumberToUint32(keys->get(i));
- if (key < current_pos) break;
- if (key >= limit) continue;
-
- Maybe<bool> delete_result = JSReceiver::DeleteElement(receiver, key);
- MAYBE_RETURN(delete_result, ReadOnlyRoots(isolate).exception());
- }
-
- return *isolate->factory()->NewNumberFromUint(result);
-}
-
-// Collects all defined (non-hole) and non-undefined (array) elements at the
-// start of the elements array. If the object is in dictionary mode, it is
-// converted to fast elements mode. Undefined values are placed after
-// non-undefined values. Returns the number of non-undefined values.
-V8_WARN_UNUSED_RESULT
-Object RemoveArrayHoles(Isolate* isolate, Handle<JSReceiver> receiver,
- uint32_t limit) {
- if (receiver->IsJSProxy()) {
- return RemoveArrayHolesGeneric(isolate, receiver, limit);
- }
-
- Handle<JSObject> object = Handle<JSObject>::cast(receiver);
- if (object->HasStringWrapperElements()) {
- int len = String::cast(Handle<JSValue>::cast(object)->value()).length();
- DCHECK_LE(len, limit);
- return Smi::FromInt(len);
- }
-
- if (object->HasSloppyArgumentsElements() || !object->map().is_extensible()) {
- return RemoveArrayHolesGeneric(isolate, receiver, limit);
- }
-
- JSObject::ValidateElements(*object);
- if (object->HasDictionaryElements()) {
- // Convert to fast elements containing only the existing properties.
- // Ordering is irrelevant, since we are going to sort anyway.
- Handle<NumberDictionary> dict(object->element_dictionary(), isolate);
- if (object->IsJSArray() || dict->requires_slow_elements() ||
- dict->max_number_key() >= limit) {
- return RemoveArrayHolesGeneric(isolate, receiver, limit);
- }
- // Convert to fast elements.
- Handle<Map> new_map =
- JSObject::GetElementsTransitionMap(object, HOLEY_ELEMENTS);
-
- AllocationType allocation = ObjectInYoungGeneration(*object)
- ? AllocationType::kYoung
- : AllocationType::kOld;
- Handle<FixedArray> fast_elements =
- isolate->factory()->NewFixedArray(dict->NumberOfElements(), allocation);
- dict->CopyValuesTo(*fast_elements);
-
- JSObject::SetMapAndElements(object, new_map, fast_elements);
- JSObject::ValidateElements(*object);
- } else if (object->HasFixedTypedArrayElements()) {
- // Typed arrays cannot have holes or undefined elements.
- // TODO(bmeurer, v8:4153): Change this to size_t later.
- uint32_t array_length =
- static_cast<uint32_t>(Handle<JSTypedArray>::cast(receiver)->length());
- return Smi::FromInt(Min(limit, array_length));
- } else if (!object->HasDoubleElements()) {
- JSObject::EnsureWritableFastElements(object);
- }
- DCHECK(object->HasSmiOrObjectElements() || object->HasDoubleElements());
-
- // Collect holes at the end, undefined before that and the rest at the
- // start, and return the number of non-hole, non-undefined values.
-
- Handle<FixedArrayBase> elements_base(object->elements(), isolate);
- uint32_t elements_length = static_cast<uint32_t>(elements_base->length());
- if (limit > elements_length) {
- limit = elements_length;
- }
- if (limit == 0) {
- return Smi::kZero;
- }
-
- uint32_t result = 0;
- if (elements_base->map() == ReadOnlyRoots(isolate).fixed_double_array_map()) {
- FixedDoubleArray elements = FixedDoubleArray::cast(*elements_base);
- // Split elements into defined and the_hole, in that order.
- unsigned int holes = limit;
- // Assume most arrays contain no holes and undefined values, so minimize the
- // number of stores of non-undefined, non-the-hole values.
- for (unsigned int i = 0; i < holes; i++) {
- if (elements.is_the_hole(i)) {
- holes--;
- } else {
- continue;
- }
- // Position i needs to be filled.
- while (holes > i) {
- if (elements.is_the_hole(holes)) {
- holes--;
- } else {
- elements.set(i, elements.get_scalar(holes));
- break;
- }
- }
- }
- result = holes;
- while (holes < limit) {
- elements.set_the_hole(holes);
- holes++;
- }
- } else {
- FixedArray elements = FixedArray::cast(*elements_base);
- DisallowHeapAllocation no_gc;
-
- // Split elements into defined, undefined and the_hole, in that order. Only
- // count locations for undefined and the hole, and fill them afterwards.
- WriteBarrierMode write_barrier = elements.GetWriteBarrierMode(no_gc);
- unsigned int undefs = limit;
- unsigned int holes = limit;
- // Assume most arrays contain no holes and undefined values, so minimize the
- // number of stores of non-undefined, non-the-hole values.
- for (unsigned int i = 0; i < undefs; i++) {
- Object current = elements.get(i);
- if (current.IsTheHole(isolate)) {
- holes--;
- undefs--;
- } else if (current.IsUndefined(isolate)) {
- undefs--;
- } else {
- continue;
- }
- // Position i needs to be filled.
- while (undefs > i) {
- current = elements.get(undefs);
- if (current.IsTheHole(isolate)) {
- holes--;
- undefs--;
- } else if (current.IsUndefined(isolate)) {
- undefs--;
- } else {
- elements.set(i, current, write_barrier);
- break;
- }
- }
- }
- result = undefs;
- while (undefs < holes) {
- elements.set_undefined(isolate, undefs);
- undefs++;
- }
- while (holes < limit) {
- elements.set_the_hole(isolate, holes);
- holes++;
- }
- }
-
- DCHECK_LE(result, limit);
- return *isolate->factory()->NewNumberFromUint(result);
-}
-
-// Copy element at index from source to target only if target does not have the
-// element on its own. Returns true if a copy occurred, false if not
-// and Nothing if an exception occurred.
-V8_WARN_UNUSED_RESULT
-Maybe<bool> ConditionalCopy(Isolate* isolate, Handle<JSReceiver> source,
- Handle<JSReceiver> target, uint32_t index) {
- Maybe<bool> source_has_prop = JSReceiver::HasOwnProperty(source, index);
- MAYBE_RETURN(source_has_prop, Nothing<bool>());
- if (!source_has_prop.FromJust()) return Just(false);
-
- Maybe<bool> target_has_prop = JSReceiver::HasOwnProperty(target, index);
- MAYBE_RETURN(target_has_prop, Nothing<bool>());
- if (target_has_prop.FromJust()) return Just(false);
-
- Handle<Object> source_element;
- ASSIGN_RETURN_ON_EXCEPTION_VALUE(
- isolate, source_element, JSReceiver::GetElement(isolate, target, index),
- Nothing<bool>());
-
- Handle<Object> set_result;
- ASSIGN_RETURN_ON_EXCEPTION_VALUE(
- isolate, set_result,
- Object::SetElement(isolate, target, index, source_element,
- ShouldThrow::kThrowOnError),
- Nothing<bool>());
-
- return Just(true);
-}
-
-// Copy elements in the range 0..length from objects prototype chain
-// to object itself, if object has holes. Returns null on error and undefined on
-// success.
-V8_WARN_UNUSED_RESULT
-MaybeHandle<Object> CopyFromPrototype(Isolate* isolate,
- Handle<JSReceiver> object,
- uint32_t length) {
- for (PrototypeIterator iter(isolate, object, kStartAtPrototype);
- !iter.IsAtEnd(); iter.Advance()) {
- Handle<JSReceiver> current(PrototypeIterator::GetCurrent<JSReceiver>(iter));
-
- if (current->IsJSProxy()) {
- for (uint32_t i = 0; i < length; ++i) {
- MAYBE_RETURN_NULL(ConditionalCopy(isolate, current, object, i));
- }
- } else {
- Handle<FixedArray> keys = JSReceiver::GetOwnElementIndices(
- isolate, object, Handle<JSObject>::cast(current));
-
- uint32_t num_indices = keys->length();
- for (uint32_t i = 0; i < num_indices; ++i) {
- uint32_t idx = NumberToUint32(keys->get(i));
-
- // Prototype might have indices that go past length, but we are only
- // interested in the range [0, length).
- if (idx >= length) break;
-
- MAYBE_RETURN_NULL(ConditionalCopy(isolate, current, object, idx));
- }
- }
- }
- return isolate->factory()->undefined_value();
-}
-
-} // namespace
-
-RUNTIME_FUNCTION(Runtime_PrepareElementsForSort) {
- HandleScope scope(isolate);
- DCHECK_EQ(2, args.length());
- CONVERT_ARG_HANDLE_CHECKED(JSReceiver, object, 0);
- CONVERT_NUMBER_CHECKED(uint32_t, length, Uint32, args[1]);
-
- if (isolate->debug_execution_mode() == DebugInfo::kSideEffects) {
- if (!isolate->debug()->PerformSideEffectCheckForObject(object)) {
- return ReadOnlyRoots(isolate).exception();
- }
- }
-
- // Counter for sorting arrays that have non-packed elements and where either
- // the ElementsProtector is invalid or the prototype does not match
- // Array.prototype.
- JSObject initial_array_proto = JSObject::cast(
- isolate->native_context()->get(Context::INITIAL_ARRAY_PROTOTYPE_INDEX));
- if (object->IsJSArray() &&
- !Handle<JSArray>::cast(object)->HasFastPackedElements()) {
- if (!isolate->IsNoElementsProtectorIntact() ||
- object->map().prototype() != initial_array_proto) {
- isolate->CountUsage(
- v8::Isolate::kArrayPrototypeSortJSArrayModifiedPrototype);
- }
- }
-
- // Skip copying from prototype for JSArrays with ElementsProtector intact and
- // the original array prototype.
- if (!object->IsJSArray() || !isolate->IsNoElementsProtectorIntact() ||
- object->map().prototype() != initial_array_proto) {
- RETURN_FAILURE_ON_EXCEPTION(isolate,
- CopyFromPrototype(isolate, object, length));
- }
- return RemoveArrayHoles(isolate, object, length);
-}
-
RUNTIME_FUNCTION(Runtime_NewArray) {
HandleScope scope(isolate);
DCHECK_LE(3, args.length());
diff --git a/src/runtime/runtime.h b/src/runtime/runtime.h
index 983b64b..2f343bf 100644
--- a/src/runtime/runtime.h
+++ b/src/runtime/runtime.h
@@ -46,7 +46,6 @@
I(IsArray, 1, 1) \
F(NewArray, -1 /* >= 3 */, 1) \
F(NormalizeElements, 1, 1) \
- F(PrepareElementsForSort, 2, 1) \
F(TransitionElementsKind, 2, 1) \
F(TransitionElementsKindWithKind, 2, 1) \
diff --git a/test/js-perf-test/ArraySort/sort-base.js b/test/js-perf-test/ArraySort/sort-base.js
index c888972..776d45e 100644
--- a/test/js-perf-test/ArraySort/sort-base.js
+++ b/test/js-perf-test/ArraySort/sort-base.js
@@ -93,7 +93,9 @@
function CreateDictionaryArray() {
array_to_sort = Array.from(template_array);
- array_to_sort[%MaxSmi()] = 42;
+ Object.defineProperty(array_to_sort, kArraySize - 2,
+ { get: () => this.foo,
+ set: (v) => this.foo = v });
AssertDictionaryElements();
}
diff --git a/test/mjsunit/array-sort.js b/test/mjsunit/array-sort.js
index ca0daad..6db8759 100644
--- a/test/mjsunit/array-sort.js
+++ b/test/mjsunit/array-sort.js
@@ -127,9 +127,8 @@
assertFalse(4 in obj, "objsort non-existing retained");
}
+TestSparseNonArraySorting(1000);
TestSparseNonArraySorting(5000);
-TestSparseNonArraySorting(500000);
-TestSparseNonArraySorting(Math.pow(2, 31) + 1);
function TestArrayLongerLength(length) {
@@ -147,8 +146,7 @@
TestArrayLongerLength(4);
TestArrayLongerLength(10);
TestArrayLongerLength(1000);
-TestArrayLongerLength(500000);
-TestArrayLongerLength(Math.pow(2,32) - 1);
+TestArrayLongerLength(5000);
function TestNonArrayLongerLength(length) {
@@ -166,8 +164,7 @@
TestNonArrayLongerLength(4);
TestNonArrayLongerLength(10);
TestNonArrayLongerLength(1000);
-TestNonArrayLongerLength(500000);
-TestNonArrayLongerLength(Math.pow(2,32) - 1);
+TestNonArrayLongerLength(5000);
function TestNonArrayWithAccessors() {
diff --git a/test/mjsunit/regress/regress-v8-7682.js b/test/mjsunit/regress/regress-v8-7682.js
index 86f12f5..68f9e0b 100644
--- a/test/mjsunit/regress/regress-v8-7682.js
+++ b/test/mjsunit/regress/regress-v8-7682.js
@@ -22,5 +22,5 @@
// the spec:
// - "xs" is sparse and IsExtensible(xs) is false (its frozen).
// - "xs" is sparse and the prototype has properties in the sort range.
-assertEquals(2, xs[0]);
-assertEquals(1, xs[1]);
+assertEquals(1, xs[0]);
+assertEquals(2, xs[1]);
diff --git a/test/mjsunit/ubsan-fuzzerbugs.js b/test/mjsunit/ubsan-fuzzerbugs.js
index 5a7594d..ae590b6 100644
--- a/test/mjsunit/ubsan-fuzzerbugs.js
+++ b/test/mjsunit/ubsan-fuzzerbugs.js
@@ -72,21 +72,3 @@
%OptimizeFunctionOnNextCall(f);
f();
})();
-
-// crbug.com/935133
-(function() {
- var called_has = false;
- var proxy = new Proxy({}, {
- has: function(x, p) {
- called_has = true;
- throw "The test may finish now";
- },
- });
- proxy.length = 2147483648;
- try {
- Array.prototype.sort.call(proxy);
- } catch(e) {
- assertTrue(e === "The test may finish now");
- }
- assertTrue(called_has);
-})();
diff --git a/test/mozilla/mozilla.status b/test/mozilla/mozilla.status
index be0180f..216d962 100644
--- a/test/mozilla/mozilla.status
+++ b/test/mozilla/mozilla.status
@@ -163,6 +163,13 @@
# https://crbug.com/v8/8120
'ecma_3/Array/regress-322135-04': [SKIP],
+ # These tests try to sort very large arrays. Array#sort pre-processing does
+ # not support huge sparse Arrays, so these tests run a very long time.
+ # https://crbug.com/v8/8714
+ 'js1_5/Array/regress-330812': [SKIP],
+ 'js1_5/Regress/regress-422348': [SKIP],
+ 'js1_5/Array/regress-157652': [SKIP],
+
##################### SLOW TESTS #####################
# Compiles a long chain of && or || operations, can time out under slower
@@ -509,7 +516,6 @@
'ecma_3/extensions/regress-274152': [FAIL_OK],
'js1_5/Regress/regress-372364': [FAIL_OK],
'js1_5/Regress/regress-420919': [FAIL_OK],
- 'js1_5/Regress/regress-422348': [FAIL_OK],
'js1_5/Regress/regress-410852': [FAIL_OK],
'ecma_3/RegExp/regress-375715-04': [FAIL_OK],
'js1_5/decompilation/regress-456964-01': [FAIL_OK],
diff --git a/test/webkit/webkit.status b/test/webkit/webkit.status
index c15c3b6..014155e 100644
--- a/test/webkit/webkit.status
+++ b/test/webkit/webkit.status
@@ -36,6 +36,11 @@
# Irregexp interpreter overflows stack. We should just not crash.
'fast/js/regexp-stack-overflow': [PASS, FAIL],
+ # This test tries to sort very large array. Array#sort pre-processing does
+ # not support huge sparse Arrays, so this test runs a very long time.
+ # https://crbug.com/v8/8714
+ 'array-sort-small-sparse-array-with-large-length': [SKIP],
+
# Slow tests.
'dfg-double-vote-fuzz': [PASS, SLOW],
}], # ALWAYS
diff --git a/third_party/v8/builtins/array-sort.tq b/third_party/v8/builtins/array-sort.tq
index ddd796b..8643348 100644
--- a/third_party/v8/builtins/array-sort.tq
+++ b/third_party/v8/builtins/array-sort.tq
@@ -34,7 +34,7 @@
ResetToGenericAccessor() {
this.loadFn = Load<GenericElementsAccessor>;
this.storeFn = Store<GenericElementsAccessor>;
- this.bailoutStatus = kSuccess;
+ this.deleteFn = Delete<GenericElementsAccessor>;
}
// The receiver of the Array.p.sort call.
@@ -54,17 +54,14 @@
// uses ToString and a lexicographical compare.
sortComparePtr: CompareBuiltinFn;
- // The following three function pointer represent a Accessor/Path.
- // These are used to Load/Store elements and to check whether to bail to the
- // baseline GenericElementsAccessor.
+ // The following four function pointer represent a Accessor/Path.
+ // These are used to Load/Store/Delete elements and to check whether
+ // to bail to the baseline GenericElementsAccessor.
loadFn: LoadFn;
storeFn: StoreFn;
+ deleteFn: DeleteFn;
canUseSameAccessorFn: CanUseSameAccessorFn;
- // If this field has the value kFailure, we need to bail to the baseline
- // GenericElementsAccessor.
- bailoutStatus: Smi;
-
// This controls when we get *into* galloping mode. It's initialized to
// kMinGallop. mergeLow and mergeHigh tend to nudge it higher for random
// data, and lower for highly structured data.
@@ -90,48 +87,76 @@
// Pointer to the temporary array.
tempArray: FixedArray;
+
+ // The initialReceiverLength converted and clamped to Smi.
+ sortLength: Smi;
+
+ // The number of undefined that need to be inserted after sorting
+ // when the elements are copied back from the workArray to the receiver.
+ numberOfUndefined: Smi;
}
+ type FastSmiElements;
+ type FastObjectElements;
+
transitioning macro NewSortState(implicit context: Context)(
receiver: JSReceiver, comparefn: Undefined | Callable,
- initialReceiverLength: Number, sortLength: Smi,
- forceGeneric: constexpr bool): SortState {
+ initialReceiverLength: Number): SortState {
const sortComparePtr =
comparefn != Undefined ? SortCompareUserFn : SortCompareDefault;
const map = receiver.map;
- let loadFn = Load<GenericElementsAccessor>;
- let storeFn = Store<GenericElementsAccessor>;
- let canUseSameAccessorFn = CanUseSameAccessor<GenericElementsAccessor>;
+ let loadFn: LoadFn;
+ let storeFn: StoreFn;
+ let deleteFn: DeleteFn;
+ let canUseSameAccessorFn: CanUseSameAccessorFn;
try {
- if constexpr (!forceGeneric) {
- GotoIfForceSlowPath() otherwise Slow;
- let a: FastJSArray = Cast<FastJSArray>(receiver) otherwise Slow;
+ GotoIfForceSlowPath() otherwise Slow;
+ let a: FastJSArray = Cast<FastJSArray>(receiver) otherwise Slow;
- const elementsKind: ElementsKind = map.elements_kind;
- if (IsDoubleElementsKind(elementsKind)) {
- loadFn = Load<FastDoubleElements>;
- storeFn = Store<FastDoubleElements>;
- canUseSameAccessorFn = CanUseSameAccessor<FastDoubleElements>;
- } else if (elementsKind == PACKED_SMI_ELEMENTS) {
- loadFn = Load<FastPackedSmiElements>;
- storeFn = Store<FastPackedSmiElements>;
- canUseSameAccessorFn = CanUseSameAccessor<FastPackedSmiElements>;
- } else {
- loadFn = Load<FastSmiOrObjectElements>;
- storeFn = Store<FastSmiOrObjectElements>;
- canUseSameAccessorFn = CanUseSameAccessor<FastSmiOrObjectElements>;
- }
+ const elementsKind: ElementsKind = map.elements_kind;
+ if (IsDoubleElementsKind(elementsKind)) {
+ loadFn = Load<FastDoubleElements>;
+ storeFn = Store<FastDoubleElements>;
+ deleteFn = Delete<FastDoubleElements>;
+ canUseSameAccessorFn = CanUseSameAccessor<FastDoubleElements>;
+ } else if (IsFastSmiElementsKind(elementsKind)) {
+ loadFn = Load<FastSmiElements>;
+ storeFn = Store<FastSmiElements>;
+ deleteFn = Delete<FastSmiElements>;
+ canUseSameAccessorFn = CanUseSameAccessor<FastSmiElements>;
+ } else {
+ loadFn = Load<FastObjectElements>;
+ storeFn = Store<FastObjectElements>;
+ deleteFn = Delete<FastObjectElements>;
+ canUseSameAccessorFn = CanUseSameAccessor<FastObjectElements>;
}
}
label Slow {
- if (map.elements_kind == DICTIONARY_ELEMENTS && IsExtensibleMap(map) &&
- !IsCustomElementsReceiverInstanceType(map.instance_type)) {
- loadFn = Load<DictionaryElements>;
- storeFn = Store<DictionaryElements>;
- canUseSameAccessorFn = CanUseSameAccessor<DictionaryElements>;
+ loadFn = Load<GenericElementsAccessor>;
+ storeFn = Store<GenericElementsAccessor>;
+ deleteFn = Delete<GenericElementsAccessor>;
+ canUseSameAccessorFn = CanUseSameAccessor<GenericElementsAccessor>;
+ }
+
+ // With the pre-processing step in Torque, the exact number of elements
+ // to sort is unknown at this time. The 'length' property is an upper bound
+ // (as per spec) while the actual size of the backing store is a good guess.
+ // After the pre-processing step, the workarray won't change in length.
+ let workArrayLength: intptr =
+ Signed(Convert<uintptr>(initialReceiverLength));
+ try {
+ const object = Cast<JSObject>(receiver) otherwise NoJsObject;
+ const elementsLength = Convert<intptr>(object.elements.length);
+
+ // In some cases, elements are only on prototypes, but not on the receiver
+ // itself. Do nothing then, as {workArrayLength} got initialized with the
+ // {length} property.
+ if (elementsLength != 0) {
+ workArrayLength = IntPtrMin(workArrayLength, elementsLength);
}
}
+ label NoJsObject {}
return new SortState{
receiver,
@@ -141,17 +166,18 @@
sortComparePtr,
loadFn,
storeFn,
+ deleteFn,
canUseSameAccessorFn,
- bailoutStatus: kSuccess,
minGallop: kMinGallopWins,
pendingRunsSize: 0,
pendingRuns: AllocateZeroedFixedArray(Convert<intptr>(kMaxMergePending)),
- workArray: AllocateZeroedFixedArray(Convert<intptr>(sortLength)),
- tempArray: kEmptyFixedArray
+ workArray: AllocateZeroedFixedArray(workArrayLength),
+ tempArray: kEmptyFixedArray,
+ sortLength: 0,
+ numberOfUndefined: 0
};
}
- const kFailure: Smi = -1;
const kSuccess: Smi = 0;
// The maximum number of entries in a SortState's pending-runs stack.
@@ -171,6 +197,7 @@
type LoadFn = builtin(Context, SortState, Smi) => Object;
type StoreFn = builtin(Context, SortState, Smi, Object) => Smi;
+ type DeleteFn = builtin(Context, SortState, Smi) => Smi;
type CanUseSameAccessorFn = builtin(Context, JSReceiver, Object, Number) =>
Boolean;
type CompareBuiltinFn = builtin(Context, Object, Object, Object) => Number;
@@ -183,28 +210,23 @@
transitioning builtin Load<ElementsAccessor: type>(
context: Context, sortState: SortState, index: Smi): Object {
- return GetProperty(sortState.receiver, index);
+ const receiver = sortState.receiver;
+ if (!HasProperty_Inline(receiver, index)) return Hole;
+ return GetProperty(receiver, index);
}
- Load<FastPackedSmiElements>(
- context: Context, sortState: SortState, index: Smi): Object {
+ Load<FastSmiElements>(context: Context, sortState: SortState, index: Smi):
+ Object {
const object = UnsafeCast<JSObject>(sortState.receiver);
const elements = UnsafeCast<FixedArray>(object.elements);
return elements.objects[index];
}
- Load<FastSmiOrObjectElements>(
- context: Context, sortState: SortState, index: Smi): Object {
+ Load<FastObjectElements>(context: Context, sortState: SortState, index: Smi):
+ Object {
const object = UnsafeCast<JSObject>(sortState.receiver);
const elements = UnsafeCast<FixedArray>(object.elements);
- const result: Object = elements.objects[index];
- if (IsTheHole(result)) {
- // The pre-processing step removed all holes by compacting all elements
- // at the start of the array. Finding a hole means the cmp function or
- // ToString changes the array.
- return Failure(sortState);
- }
- return result;
+ return elements.objects[index];
}
Load<FastDoubleElements>(context: Context, sortState: SortState, index: Smi):
@@ -212,28 +234,11 @@
try {
const object = UnsafeCast<JSObject>(sortState.receiver);
const elements = UnsafeCast<FixedDoubleArray>(object.elements);
- const value = LoadDoubleWithHoleCheck(elements, index) otherwise Bailout;
+ const value = LoadDoubleWithHoleCheck(elements, index) otherwise IfHole;
return AllocateHeapNumberWithValue(value);
}
- label Bailout {
- // The pre-processing step removed all holes by compacting all elements
- // at the start of the array. Finding a hole means the cmp function or
- // ToString changes the array.
- return Failure(sortState);
- }
- }
-
- Load<DictionaryElements>(context: Context, sortState: SortState, index: Smi):
- Object {
- try {
- const object = UnsafeCast<JSObject>(sortState.receiver);
- const dictionary = UnsafeCast<NumberDictionary>(object.elements);
- const intptrIndex = Convert<intptr>(index);
- return BasicLoadNumberDictionaryElement(dictionary, intptrIndex)
- otherwise Bailout, Bailout;
- }
- label Bailout {
- return Failure(sortState);
+ label IfHole {
+ return Hole;
}
}
@@ -243,7 +248,7 @@
return kSuccess;
}
- Store<FastPackedSmiElements>(
+ Store<FastSmiElements>(
context: Context, sortState: SortState, index: Smi, value: Object): Smi {
const object = UnsafeCast<JSObject>(sortState.receiver);
const elements = UnsafeCast<FixedArray>(object.elements);
@@ -252,7 +257,7 @@
return kSuccess;
}
- Store<FastSmiOrObjectElements>(
+ Store<FastObjectElements>(
context: Context, sortState: SortState, index: Smi, value: Object): Smi {
const object = UnsafeCast<JSObject>(sortState.receiver);
const elements = UnsafeCast<FixedArray>(object.elements);
@@ -270,26 +275,42 @@
return kSuccess;
}
- Store<DictionaryElements>(
- context: Context, sortState: SortState, index: Smi, value: Object): Smi {
+ transitioning builtin Delete<ElementsAccessor: type>(
+ context: Context, sortState: SortState, index: Smi): Smi {
+ const receiver = sortState.receiver;
+ if (!HasProperty_Inline(receiver, index)) return kSuccess;
+ DeleteProperty(receiver, index, kSloppy);
+ return kSuccess;
+ }
+
+ Delete<FastSmiElements>(context: Context, sortState: SortState, index: Smi):
+ Smi {
+ assert(IsHoleyFastElementsKind(sortState.receiver.map.elements_kind));
+
const object = UnsafeCast<JSObject>(sortState.receiver);
- const dictionary = UnsafeCast<NumberDictionary>(object.elements);
- const intptrIndex = Convert<intptr>(index);
- try {
- BasicStoreNumberDictionaryElement(dictionary, intptrIndex, value)
- otherwise Fail, Fail, ReadOnly;
- return kSuccess;
- }
- label ReadOnly {
- // We cannot write to read-only data properties. Throw the same TypeError
- // as SetProperty would.
- const receiver = sortState.receiver;
- ThrowTypeError(
- kStrictReadOnlyProperty, index, Typeof(receiver), receiver);
- }
- label Fail {
- return Failure(sortState);
- }
+ const elements = UnsafeCast<FixedArray>(object.elements);
+ elements.objects[index] = Hole;
+ return kSuccess;
+ }
+
+ Delete<FastObjectElements>(
+ context: Context, sortState: SortState, index: Smi): Smi {
+ assert(IsHoleyFastElementsKind(sortState.receiver.map.elements_kind));
+
+ const object = UnsafeCast<JSObject>(sortState.receiver);
+ const elements = UnsafeCast<FixedArray>(object.elements);
+ elements.objects[index] = Hole;
+ return kSuccess;
+ }
+
+ Delete<FastDoubleElements>(
+ context: Context, sortState: SortState, index: Smi): Smi {
+ assert(IsHoleyFastElementsKind(sortState.receiver.map.elements_kind));
+
+ const object = UnsafeCast<JSObject>(sortState.receiver);
+ const elements = UnsafeCast<FixedDoubleArray>(object.elements);
+ StoreFixedDoubleArrayHoleSmi(elements, index);
+ return kSuccess;
}
transitioning builtin SortCompareDefault(
@@ -355,12 +376,6 @@
return True;
}
- CanUseSameAccessor<DictionaryElements>(
- context: Context, receiver: JSReceiver, initialReceiverMap: Object,
- initialReceiverLength: Number): Boolean {
- return SelectBooleanConstant(receiver.map == initialReceiverMap);
- }
-
// Re-loading the stack-size is done in a few places. The small macro allows
// for easier invariant checks at all use sites.
macro GetPendingRunsSize(implicit context: Context)(sortState: SortState):
@@ -419,36 +434,6 @@
return tempArray;
}
- // This macro jumps to the Bailout label iff kBailoutStatus is kFailure.
- macro EnsureSuccess(implicit context: Context)(sortState:
- SortState) labels Bailout {
- if (sortState.bailoutStatus == kFailure) goto Bailout;
- }
-
- // Sets kBailoutStatus to kFailure and returns kFailure.
- macro Failure(sortState: SortState): Smi {
- sortState.bailoutStatus = kFailure;
- return kFailure;
- }
-
- // The following Call* macros wrap builtin calls, making call sites more
- // readable since we can use labels and do not have to check kBailoutStatus
- // or the return value.
-
- macro CallLoad(implicit context: Context, sortState: SortState)(
- load: LoadFn, index: Smi): Object
- labels Bailout {
- const result: Object = load(context, sortState, index);
- EnsureSuccess(sortState) otherwise Bailout;
- return result;
- }
-
- macro CallStore(implicit context: Context, sortState: SortState)(
- store: StoreFn, index: Smi, value: Object) labels Bailout {
- store(context, sortState, index, value);
- EnsureSuccess(sortState) otherwise Bailout;
- }
-
transitioning builtin
Copy(implicit context: Context)(
source: FixedArray, srcPos: Smi, target: FixedArray, dstPos: Smi,
@@ -1268,49 +1253,87 @@
}
transitioning macro
- CopyReceiverElementsToWorkArray(
- implicit context: Context, sortState: SortState)(length: Smi) {
- // TODO(szuend): Investigate if we can use COW arrays or a memcpy + range
- // barrier to speed this step up.
- let loadFn = sortState.loadFn;
- const workArray = sortState.workArray;
+ CompactReceiverElementsIntoWorkArray(
+ implicit context: Context, sortState: SortState)(): Smi {
+ let growableWorkArray = growable_fixed_array::GrowableFixedArray{
+ array: sortState.workArray,
+ capacity: Convert<intptr>(sortState.workArray.length),
+ length: 0
+ };
- for (let i: Smi = 0; i < length; ++i) {
- try {
- workArray.objects[i] = CallLoad(loadFn, i) otherwise Bailout;
- }
- label Bailout deferred {
- sortState.ResetToGenericAccessor();
- loadFn = sortState.loadFn;
- workArray.objects[i] = CallLoad(loadFn, i) otherwise unreachable;
+ const loadFn = sortState.loadFn;
+
+ // TODO(szuend): Implement full range sorting, not only up to MaxSmi.
+ // https://crbug.com/v8/7970.
+ const receiverLength: Number = sortState.initialReceiverLength;
+ assert(IsNumberNormalized(receiverLength));
+
+ const sortLength: Smi = TaggedIsSmi(receiverLength) ?
+ UnsafeCast<Smi>(receiverLength) :
+ Convert<PositiveSmi>(kSmiMax) otherwise unreachable;
+
+ // Move all non-undefined elements into {sortState.workArray}, holes
+ // are ignored.
+ let numberOfUndefined: Smi = 0;
+ for (let i: Smi = 0; i < receiverLength; ++i) {
+ const element: Object = loadFn(context, sortState, i);
+
+ if (element == Hole) {
+ // Do nothing for holes. The result is that elements are
+ // compacted at the front of the work array.
+ } else if (element == Undefined) {
+ numberOfUndefined++;
+ } else {
+ growableWorkArray.Push(element);
}
}
+
+ // Reset the workArray on the frameState, as it may have grown.
+ sortState.workArray = growableWorkArray.array;
+ sortState.sortLength = sortLength;
+ sortState.numberOfUndefined = numberOfUndefined;
+
+ return Convert<Smi>(growableWorkArray.length);
}
transitioning macro
CopyWorkArrayToReceiver(implicit context: Context, sortState: SortState)(
- length: Smi) {
- // TODO(szuend): Build fast-path that simply installs the work array as the
- // new backing store where applicable.
- let storeFn = sortState.storeFn;
+ numberOfNonUndefined: Smi) {
+ const storeFn = sortState.storeFn;
const workArray = sortState.workArray;
- for (let i: Smi = 0; i < length; ++i) {
- try {
- CallStore(storeFn, i, workArray.objects[i]) otherwise Bailout;
- }
- label Bailout deferred {
- sortState.ResetToGenericAccessor();
- storeFn = sortState.storeFn;
- CallStore(storeFn, i, workArray.objects[i]) otherwise unreachable;
- }
+ assert(numberOfNonUndefined <= workArray.length);
+ assert(
+ numberOfNonUndefined + sortState.numberOfUndefined <=
+ sortState.sortLength);
+
+ // Writing the elements back is a 3 step process:
+ // 1. Copy the sorted elements from the workarray to the receiver.
+ // 2. Add {nOfUndefined} undefineds to the receiver.
+ // 3. Depending on the backing store either delete properties or
+ // set them to the Hole up to {sortState.sortLength}.
+ let index: Smi = 0;
+ for (; index < numberOfNonUndefined; ++index) {
+ storeFn(context, sortState, index, workArray.objects[index]);
+ }
+
+ const numberOfUndefinedEnd: Smi =
+ sortState.numberOfUndefined + numberOfNonUndefined;
+ for (; index < numberOfUndefinedEnd; ++index) {
+ storeFn(context, sortState, index, Undefined);
+ }
+
+ const end: Smi = sortState.sortLength;
+ const deleteFn = sortState.deleteFn;
+ for (; index < end; ++index) {
+ deleteFn(context, sortState, index);
}
}
transitioning builtin
- ArrayTimSort(context: Context, sortState: SortState, length: Smi): Object {
- CopyReceiverElementsToWorkArray(length);
- ArrayTimSortImpl(context, sortState, length);
+ ArrayTimSort(context: Context, sortState: SortState): Object {
+ const numberOfNonUndefined: Smi = CompactReceiverElementsIntoWorkArray();
+ ArrayTimSortImpl(context, sortState, numberOfNonUndefined);
try {
// The comparison function or toString might have changed the
@@ -1321,24 +1344,10 @@
sortState.ResetToGenericAccessor();
}
- CopyWorkArrayToReceiver(length);
+ CopyWorkArrayToReceiver(numberOfNonUndefined);
return kSuccess;
}
- // For compatibility with JSC, we also sort elements inherited from
- // the prototype chain on non-Array objects.
- // We do this by copying them to this object and sorting only
- // own elements. This is not very efficient, but sorting with
- // inherited elements happens very, very rarely, if at all.
- // The specification allows "implementation dependent" behavior
- // if an element on the prototype chain has an element that
- // might interact with sorting.
- //
- // We also move all non-undefined elements to the front of the
- // array and move the undefineds after that. Holes are removed.
- // This happens for Array as well as non-Array objects.
- extern runtime PrepareElementsForSort(Context, Object, Number): Smi;
-
// https://tc39.github.io/ecma262/#sec-array.prototype.sort
transitioning javascript builtin
ArrayPrototypeSort(context: Context, receiver: Object, ...arguments): Object {
@@ -1356,16 +1365,8 @@
if (len < 2) return receiver;
- // TODO(szuend): Investigate performance tradeoff of skipping this step
- // for PACKED_* and handling Undefineds during sorting.
- const nofNonUndefined: Smi = PrepareElementsForSort(context, obj, len);
- assert(nofNonUndefined <= len);
-
- if (nofNonUndefined < 2) return receiver;
-
- const sortState: SortState =
- NewSortState(obj, comparefn, len, nofNonUndefined, false);
- ArrayTimSort(context, sortState, nofNonUndefined);
+ const sortState: SortState = NewSortState(obj, comparefn, len);
+ ArrayTimSort(context, sortState);
return receiver;
}
