Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

BUG: Array prototype values copied to non-array when using sort #5719

Closed
rhuanjl opened this issue Sep 21, 2018 · 0 comments · Fixed by #5724
Closed

BUG: Array prototype values copied to non-array when using sort #5719

rhuanjl opened this issue Sep 21, 2018 · 0 comments · Fixed by #5724
Assignees
Milestone

Comments

@rhuanjl
Copy link
Collaborator

rhuanjl commented Sep 21, 2018

Note I am intending to fix this bug as part of the pull request I'm working on to implement a stable array sort.

Opening this issue as a reminder/record and also in case my upcoming pull request can't be accepted for some reason.

With the current Array.prototype.sort method in ChakraCore if an array-like object with missing properties has the sort method called on it ChakraCore will fill the holes by copying from the array prototype if it has applicable values on it.

Including if the array-like object is not an instance of Array and does not inherit from the array prototype.

Array.prototype[1] = 321;

var o = {};
o[0] = 10;
o.length = 3;
o.sort = Array.prototype.sort;
o.join = Array.prototype.join;
o.toString = Array.prototype.toString;

print (o.sort().toString());

eshost output:

#### ChakraCore v1.11
10,321,

#### SpiderMonkey
10,,

#### ChakraCore master
10,321,

#### V8 --harmony
10,,

#### JavaScriptCore
10,,

Additionally this incorrect behaviour is currently tested in es5/defineIndexProperty.js as test_321_i.

@kfarnung kfarnung added this to the vNext milestone Sep 26, 2018
chakrabot pushed a commit that referenced this issue Nov 1, 2018
….sort

Merge pull request #5724 from rhuanjl:mergeSort

Picking up on the discussion in #5661 This PR implements a stable bottom up Merge Sort as a JsBuiltin for arrays of any length up to 2^32 (well I hit out of memory trying to allocate an array with length above 2^29 but in theory).

I'm not sure if it's good enough to merge as is but would appreciate feedback.

**EDIT:** I've made some large edits to the below to reflect changes made.

**Issues to consider:**
1. **Performance - DefaultCompare** - My Default Compare sort is very slow despite cacheing all the string conversions at the start it. The string less than operation is a significant bottle neck - I have tried:
    - a native chakraLibrary method to compare strings - this was about the same performance as using less than
    - using charCodeAt in a loop - this was also about the same performance as using less than

1. **Insertion sort** - I have included an insertion sort directly in the Array.prototype.sort function used for short arrays - could consider what the best cut off is before switching to mergeSort instead - currently length of 2048 is used.

1. **Memory usage** - My implementation of merge sort needs a buffer array with length up to half the length of the array being sorted.

1. **Scope** - I've not looked at the sort method for TypedArrays obviously stabilising that doesn't make sense (though may be worth looking at its performance on xplat as it uses the earlier mentioned slow xplat qsort for arrays of any length)

1. **Tests** - I've consolidated most of the pre-existing array sort tests and also added a test for sorting a variety of random arrays and ensuring that the sort is both correct and stable

1. **General** - see other comments I've added below...

fixes: #5661
fixes: #5719
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants