Reland "[array] Move Array#sort pre-processing to Torque"
This is a reland of 2b0ac2fb9f355a7a5f2b6470c6357ebf73cfe4cc
The layout test that caused this revert was fixed with:
https://crrev.com/c/1627386
Original change's description:
> [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}
TBR: jgruber@chromium.org
Bug: v8:8714
Change-Id: If7613f6e5f37c5e0d649e8192195594bc6c32100
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1627977
Commit-Queue: Simon Zünd <szuend@chromium.org>
Auto-Submit: Simon Zünd <szuend@chromium.org>
Reviewed-by: Tobias Tebbi <tebbi@chromium.org>
Cr-Commit-Position: refs/heads/master@{#61827}
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..a4960cd 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;
}