{"action":"created","comment":{"url":"https://api.github.com/repos/Microsoft/ChakraCore/pulls/comments/219943205","pull_request_review_id":158238101,"id":219943205,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDIxOTk0MzIwNQ==","diff_hunk":"@@ -181,6 +181,232 @@\n         }\n     });\n \n+    platform.registerChakraLibraryFunction(\"DefaultMergeSort\", function(array, length) {\n+        const compareArray = [];\n+        for (let index = 0; index < length; ++index) {\n+            __chakraLibrary.arrayCreateDataPropertyOrThrow(compareArray, index, \"\" + array[index]);\n+        }\n+\n+        const fast = length < 1073741825;\n+        const buffer = [];\n+        const stringBuffer = [];\n+\n+        let i = 1, j = 0, k = 0, bucketSize = 4, position = 0;\n+\n+        // handle pairs first\n+        while (i < length) {\n+            if (compareArray[i] < compareArray[i - 1]) {\n+                const cache = array[i];\n+                array[i] = array[i - 1];\n+                array[i - 1] = cache;\n+\n+                const stringCache = compareArray[i];\n+                compareArray[i] = compareArray[i - 1];\n+                compareArray[i - 1] = stringCache;\n+            }\n+            i += 2;\n+        }\n+        const doubleLength = length * 2;\n+\n+        while (bucketSize < doubleLength) {\n+            while (position < length) {\n+                const left = position;\n+                let right = position + bucketSize;\n+                right < length ? right : length;","path":"lib/Runtime/Library/JsBuiltIn/JsBuiltIn.js","position":35,"original_position":35,"commit_id":"3f290d82fa88d8feb398a2916f02d832f87f7322","original_commit_id":"3f290d82fa88d8feb398a2916f02d832f87f7322","user":{"login":"fatcerberus","id":4097841,"node_id":"MDQ6VXNlcjQwOTc4NDE=","avatar_url":"https://avatars2.githubusercontent.com/u/4097841?v=4","gravatar_id":"","url":"https://api.github.com/users/fatcerberus","html_url":"https://github.com/fatcerberus","followers_url":"https://api.github.com/users/fatcerberus/followers","following_url":"https://api.github.com/users/fatcerberus/following{/other_user}","gists_url":"https://api.github.com/users/fatcerberus/gists{/gist_id}","starred_url":"https://api.github.com/users/fatcerberus/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/fatcerberus/subscriptions","organizations_url":"https://api.github.com/users/fatcerberus/orgs","repos_url":"https://api.github.com/users/fatcerberus/repos","events_url":"https://api.github.com/users/fatcerberus/events{/privacy}","received_events_url":"https://api.github.com/users/fatcerberus/received_events","type":"User","site_admin":false},"body":"That looks like a no-op; it evaluates to either `right;` or `length;` which will have no effect.  Remnant from refactoring maybe?","created_at":"2018-09-24T18:33:56Z","updated_at":"2018-09-24T18:33:56Z","html_url":"https://github.com/Microsoft/ChakraCore/pull/5724#discussion_r219943205","pull_request_url":"https://api.github.com/repos/Microsoft/ChakraCore/pulls/5724","author_association":"CONTRIBUTOR","_links":{"self":{"href":"https://api.github.com/repos/Microsoft/ChakraCore/pulls/comments/219943205"},"html":{"href":"https://github.com/Microsoft/ChakraCore/pull/5724#discussion_r219943205"},"pull_request":{"href":"https://api.github.com/repos/Microsoft/ChakraCore/pulls/5724"}},"in_reply_to_id":219931904},"pull_request":{"url":"https://api.github.com/repos/Microsoft/ChakraCore/pulls/5724","id":217477350,"node_id":"MDExOlB1bGxSZXF1ZXN0MjE3NDc3MzUw","html_url":"https://github.com/Microsoft/ChakraCore/pull/5724","diff_url":"https://github.com/Microsoft/ChakraCore/pull/5724.diff","patch_url":"https://github.com/Microsoft/ChakraCore/pull/5724.patch","issue_url":"https://api.github.com/repos/Microsoft/ChakraCore/issues/5724","number":5724,"state":"open","locked":false,"title":"Implement stable MergeSort for Array.prototype.sort","user":{"login":"rhuanjl","id":30090552,"node_id":"MDQ6VXNlcjMwMDkwNTUy","avatar_url":"https://avatars3.githubusercontent.com/u/30090552?v=4","gravatar_id":"","url":"https://api.github.com/users/rhuanjl","html_url":"https://github.com/rhuanjl","followers_url":"https://api.github.com/users/rhuanjl/followers","following_url":"https://api.github.com/users/rhuanjl/following{/other_user}","gists_url":"https://api.github.com/users/rhuanjl/gists{/gist_id}","starred_url":"https://api.github.com/users/rhuanjl/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rhuanjl/subscriptions","organizations_url":"https://api.github.com/users/rhuanjl/orgs","repos_url":"https://api.github.com/users/rhuanjl/repos","events_url":"https://api.github.com/users/rhuanjl/events{/privacy}","received_events_url":"https://api.github.com/users/rhuanjl/received_events","type":"User","site_admin":false},"body":"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).\r\n\r\nI'm not sure if it's good enough to merge as is but would appreciate feedback.\r\n\r\n**Performance Comparisons**\r\nSee the comparisons I've done between the current sort, this sort and other engines at https://gist.github.com/rhuanjl/bb9d63070487b342870de50708c8999f\r\n\r\n**Issues to consider:**\r\n1. **Performance** - sorting a random array of 500,000 elements this currently takes longer than the old windows qsort. However if I write the same sort function in a normal JS file and use it in that file it matches the performance of the qsort - I believe that the performance drop is due to this not being inlined and the compare function not being inlined into it when it's a JsBuiltin. Despite this issue it is drastically faster than the currently used xplat qsort.\r\n\r\n1. **Performance** - I have also written (though not currently included) a stable insertion sort which is faster for short arrays (length < 2000) - could add this in if we want to optimise speed at the expense of slightly more complexity.\r\n\r\n1. **Performance** - A small increase could be gained from there being a Jit fast path for __chakraLibrary.arrayCreateDataPropertyOrThrow (or an alternative to using it) - I use this whenever I need to grow a working array (the compareArray for the default comparison and the buffer used when performing a Merge) as if I don't use this edits to Array.prototype can result in unexpected errors. (I did try using CreateObject(null) but that incurred much worse performance)\r\n\r\n1. **Performance - DefaultCompare** - My Default Compare sort is very slow despite cacheing all the string conversions at the start it measures a lot slower than the current version and the other engines - not sure what I can do here string coercion seems to be a very slow op and can't see a different way to be compliant.\r\n\r\n1. **Memory usage** - My implementation of merge sort needs a buffer array half the length of the array being sorted - I can't see a way around that. Additionally my sort for when there's no comparison function creates an array out of string versions of the elements in the first array - so that they don't have to be toString'd for every comparison - this obviously could use a lot of extra memory.\r\n\r\n1. **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)\r\n\r\n1. **Error handling** - I've not put any special error messages in for issues with non-writable array elements or the like - unsure if this is worth doing. Also the previous native version would sort a copy of the array if the array included getters/setters then overwrite the orriginal - I don't think this was right so i have not duplicated it (per spec the sort is done by using get/set on the provided array)\r\n\r\n1. **General** - see other comments I've added below...\r\n\r\nfixes: #5661\r\nfixes: #5719","created_at":"2018-09-22T20:41:20Z","updated_at":"2018-09-24T18:33:56Z","closed_at":null,"merged_at":null,"merge_commit_sha":"147692fab4f4ef44469e78236adaa4d8f4434869","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[{"id":1034800413,"node_id":"MDU6TGFiZWwxMDM0ODAwNDEz","url":"https://api.github.com/repos/Microsoft/ChakraCore/labels/Bytecode-Update","name":"Bytecode-Update","color":"ffee99","default":false},{"id":546598686,"node_id":"MDU6TGFiZWw1NDY1OTg2ODY=","url":"https://api.github.com/repos/Microsoft/ChakraCore/labels/External%20Contributor","name":"External Contributor","color":"D95D00","default":false}],"milestone":null,"commits_url":"https://api.github.com/repos/Microsoft/ChakraCore/pulls/5724/commits","review_comments_url":"https://api.github.com/repos/Microsoft/ChakraCore/pulls/5724/comments","review_comment_url":"https://api.github.com/repos/Microsoft/ChakraCore/pulls/comments{/number}","comments_url":"https://api.github.com/repos/Microsoft/ChakraCore/issues/5724/comments","statuses_url":"https://api.github.com/repos/Microsoft/ChakraCore/statuses/3f290d82fa88d8feb398a2916f02d832f87f7322","head":{"label":"rhuanjl:mergeSort","ref":"mergeSort","sha":"3f290d82fa88d8feb398a2916f02d832f87f7322","user":{"login":"rhuanjl","id":30090552,"node_id":"MDQ6VXNlcjMwMDkwNTUy","avatar_url":"https://avatars3.githubusercontent.com/u/30090552?v=4","gravatar_id":"","url":"https://api.github.com/users/rhuanjl","html_url":"https://github.com/rhuanjl","followers_url":"https://api.github.com/users/rhuanjl/followers","following_url":"https://api.github.com/users/rhuanjl/following{/other_user}","gists_url":"https://api.github.com/users/rhuanjl/gists{/gist_id}","starred_url":"https://api.github.com/users/rhuanjl/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rhuanjl/subscriptions","organizations_url":"https://api.github.com/users/rhuanjl/orgs","repos_url":"https://api.github.com/users/rhuanjl/repos","events_url":"https://api.github.com/users/rhuanjl/events{/privacy}","received_events_url":"https://api.github.com/users/rhuanjl/received_events","type":"User","site_admin":false},"repo":{"id":117721683,"node_id":"MDEwOlJlcG9zaXRvcnkxMTc3MjE2ODM=","name":"ChakraCore","full_name":"rhuanjl/ChakraCore","private":false,"owner":{"login":"rhuanjl","id":30090552,"node_id":"MDQ6VXNlcjMwMDkwNTUy","avatar_url":"https://avatars3.githubusercontent.com/u/30090552?v=4","gravatar_id":"","url":"https://api.github.com/users/rhuanjl","html_url":"https://github.com/rhuanjl","followers_url":"https://api.github.com/users/rhuanjl/followers","following_url":"https://api.github.com/users/rhuanjl/following{/other_user}","gists_url":"https://api.github.com/users/rhuanjl/gists{/gist_id}","starred_url":"https://api.github.com/users/rhuanjl/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rhuanjl/subscriptions","organizations_url":"https://api.github.com/users/rhuanjl/orgs","repos_url":"https://api.github.com/users/rhuanjl/repos","events_url":"https://api.github.com/users/rhuanjl/events{/privacy}","received_events_url":"https://api.github.com/users/rhuanjl/received_events","type":"User","site_admin":false},"html_url":"https://github.com/rhuanjl/ChakraCore","description":"ChakraCore is the core part of the Chakra Javascript engine that powers Microsoft Edge","fork":true,"url":"https://api.github.com/repos/rhuanjl/ChakraCore","forks_url":"https://api.github.com/repos/rhuanjl/ChakraCore/forks","keys_url":"https://api.github.com/repos/rhuanjl/ChakraCore/keys{/key_id}","collaborators_url":"https://api.github.com/repos/rhuanjl/ChakraCore/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/rhuanjl/ChakraCore/teams","hooks_url":"https://api.github.com/repos/rhuanjl/ChakraCore/hooks","issue_events_url":"https://api.github.com/repos/rhuanjl/ChakraCore/issues/events{/number}","events_url":"https://api.github.com/repos/rhuanjl/ChakraCore/events","assignees_url":"https://api.github.com/repos/rhuanjl/ChakraCore/assignees{/user}","branches_url":"https://api.github.com/repos/rhuanjl/ChakraCore/branches{/branch}","tags_url":"https://api.github.com/repos/rhuanjl/ChakraCore/tags","blobs_url":"https://api.github.com/repos/rhuanjl/ChakraCore/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/rhuanjl/ChakraCore/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/rhuanjl/ChakraCore/git/refs{/sha}","trees_url":"https://api.github.com/repos/rhuanjl/ChakraCore/git/trees{/sha}","statuses_url":"https://api.github.com/repos/rhuanjl/ChakraCore/statuses/{sha}","languages_url":"https://api.github.com/repos/rhuanjl/ChakraCore/languages","stargazers_url":"https://api.github.com/repos/rhuanjl/ChakraCore/stargazers","contributors_url":"https://api.github.com/repos/rhuanjl/ChakraCore/contributors","subscribers_url":"https://api.github.com/repos/rhuanjl/ChakraCore/subscribers","subscription_url":"https://api.github.com/repos/rhuanjl/ChakraCore/subscription","commits_url":"https://api.github.com/repos/rhuanjl/ChakraCore/commits{/sha}","git_commits_url":"https://api.github.com/repos/rhuanjl/ChakraCore/git/commits{/sha}","comments_url":"https://api.github.com/repos/rhuanjl/ChakraCore/comments{/number}","issue_comment_url":"https://api.github.com/repos/rhuanjl/ChakraCore/issues/comments{/number}","contents_url":"https://api.github.com/repos/rhuanjl/ChakraCore/contents/{+path}","compare_url":"https://api.github.com/repos/rhuanjl/ChakraCore/compare/{base}...{head}","merges_url":"https://api.github.com/repos/rhuanjl/ChakraCore/merges","archive_url":"https://api.github.com/repos/rhuanjl/ChakraCore/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/rhuanjl/ChakraCore/downloads","issues_url":"https://api.github.com/repos/rhuanjl/ChakraCore/issues{/number}","pulls_url":"https://api.github.com/repos/rhuanjl/ChakraCore/pulls{/number}","milestones_url":"https://api.github.com/repos/rhuanjl/ChakraCore/milestones{/number}","notifications_url":"https://api.github.com/repos/rhuanjl/ChakraCore/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/rhuanjl/ChakraCore/labels{/name}","releases_url":"https://api.github.com/repos/rhuanjl/ChakraCore/releases{/id}","deployments_url":"https://api.github.com/repos/rhuanjl/ChakraCore/deployments","created_at":"2018-01-16T18:11:05Z","updated_at":"2018-09-18T21:58:13Z","pushed_at":"2018-09-24T18:23:30Z","git_url":"git://github.com/rhuanjl/ChakraCore.git","ssh_url":"git@github.com:rhuanjl/ChakraCore.git","clone_url":"https://github.com/rhuanjl/ChakraCore.git","svn_url":"https://github.com/rhuanjl/ChakraCore","homepage":"","size":148653,"stargazers_count":0,"watchers_count":0,"language":"JavaScript","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":{"key":"mit","name":"MIT License","spdx_id":"MIT","url":"https://api.github.com/licenses/mit","node_id":"MDc6TGljZW5zZTEz"},"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"Microsoft:master","ref":"master","sha":"6efd6f66df3423e6d505ce3e6c1a9a3387bcf58a","user":{"login":"Microsoft","id":6154722,"node_id":"MDEyOk9yZ2FuaXphdGlvbjYxNTQ3MjI=","avatar_url":"https://avatars2.githubusercontent.com/u/6154722?v=4","gravatar_id":"","url":"https://api.github.com/users/Microsoft","html_url":"https://github.com/Microsoft","followers_url":"https://api.github.com/users/Microsoft/followers","following_url":"https://api.github.com/users/Microsoft/following{/other_user}","gists_url":"https://api.github.com/users/Microsoft/gists{/gist_id}","starred_url":"https://api.github.com/users/Microsoft/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Microsoft/subscriptions","organizations_url":"https://api.github.com/users/Microsoft/orgs","repos_url":"https://api.github.com/users/Microsoft/repos","events_url":"https://api.github.com/users/Microsoft/events{/privacy}","received_events_url":"https://api.github.com/users/Microsoft/received_events","type":"Organization","site_admin":false},"repo":{"id":49086513,"node_id":"MDEwOlJlcG9zaXRvcnk0OTA4NjUxMw==","name":"ChakraCore","full_name":"Microsoft/ChakraCore","private":false,"owner":{"login":"Microsoft","id":6154722,"node_id":"MDEyOk9yZ2FuaXphdGlvbjYxNTQ3MjI=","avatar_url":"https://avatars2.githubusercontent.com/u/6154722?v=4","gravatar_id":"","url":"https://api.github.com/users/Microsoft","html_url":"https://github.com/Microsoft","followers_url":"https://api.github.com/users/Microsoft/followers","following_url":"https://api.github.com/users/Microsoft/following{/other_user}","gists_url":"https://api.github.com/users/Microsoft/gists{/gist_id}","starred_url":"https://api.github.com/users/Microsoft/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Microsoft/subscriptions","organizations_url":"https://api.github.com/users/Microsoft/orgs","repos_url":"https://api.github.com/users/Microsoft/repos","events_url":"https://api.github.com/users/Microsoft/events{/privacy}","received_events_url":"https://api.github.com/users/Microsoft/received_events","type":"Organization","site_admin":false},"html_url":"https://github.com/Microsoft/ChakraCore","description":"ChakraCore is the core part of the Chakra Javascript engine that powers Microsoft Edge","fork":false,"url":"https://api.github.com/repos/Microsoft/ChakraCore","forks_url":"https://api.github.com/repos/Microsoft/ChakraCore/forks","keys_url":"https://api.github.com/repos/Microsoft/ChakraCore/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Microsoft/ChakraCore/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Microsoft/ChakraCore/teams","hooks_url":"https://api.github.com/repos/Microsoft/ChakraCore/hooks","issue_events_url":"https://api.github.com/repos/Microsoft/ChakraCore/issues/events{/number}","events_url":"https://api.github.com/repos/Microsoft/ChakraCore/events","assignees_url":"https://api.github.com/repos/Microsoft/ChakraCore/assignees{/user}","branches_url":"https://api.github.com/repos/Microsoft/ChakraCore/branches{/branch}","tags_url":"https://api.github.com/repos/Microsoft/ChakraCore/tags","blobs_url":"https://api.github.com/repos/Microsoft/ChakraCore/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Microsoft/ChakraCore/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Microsoft/ChakraCore/git/refs{/sha}","trees_url":"https://api.github.com/repos/Microsoft/ChakraCore/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Microsoft/ChakraCore/statuses/{sha}","languages_url":"https://api.github.com/repos/Microsoft/ChakraCore/languages","stargazers_url":"https://api.github.com/repos/Microsoft/ChakraCore/stargazers","contributors_url":"https://api.github.com/repos/Microsoft/ChakraCore/contributors","subscribers_url":"https://api.github.com/repos/Microsoft/ChakraCore/subscribers","subscription_url":"https://api.github.com/repos/Microsoft/ChakraCore/subscription","commits_url":"https://api.github.com/repos/Microsoft/ChakraCore/commits{/sha}","git_commits_url":"https://api.github.com/repos/Microsoft/ChakraCore/git/commits{/sha}","comments_url":"https://api.github.com/repos/Microsoft/ChakraCore/comments{/number}","issue_comment_url":"https://api.github.com/repos/Microsoft/ChakraCore/issues/comments{/number}","contents_url":"https://api.github.com/repos/Microsoft/ChakraCore/contents/{+path}","compare_url":"https://api.github.com/repos/Microsoft/ChakraCore/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Microsoft/ChakraCore/merges","archive_url":"https://api.github.com/repos/Microsoft/ChakraCore/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Microsoft/ChakraCore/downloads","issues_url":"https://api.github.com/repos/Microsoft/ChakraCore/issues{/number}","pulls_url":"https://api.github.com/repos/Microsoft/ChakraCore/pulls{/number}","milestones_url":"https://api.github.com/repos/Microsoft/ChakraCore/milestones{/number}","notifications_url":"https://api.github.com/repos/Microsoft/ChakraCore/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Microsoft/ChakraCore/labels{/name}","releases_url":"https://api.github.com/repos/Microsoft/ChakraCore/releases{/id}","deployments_url":"https://api.github.com/repos/Microsoft/ChakraCore/deployments","created_at":"2016-01-05T19:05:31Z","updated_at":"2018-09-24T18:12:48Z","pushed_at":"2018-09-24T17:59:17Z","git_url":"git://github.com/Microsoft/ChakraCore.git","ssh_url":"git@github.com:Microsoft/ChakraCore.git","clone_url":"https://github.com/Microsoft/ChakraCore.git","svn_url":"https://github.com/Microsoft/ChakraCore","homepage":"","size":153059,"stargazers_count":7404,"watchers_count":7404,"language":"JavaScript","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":993,"mirror_url":null,"archived":false,"open_issues_count":347,"license":{"key":"mit","name":"MIT License","spdx_id":"MIT","url":"https://api.github.com/licenses/mit","node_id":"MDc6TGljZW5zZTEz"},"forks":993,"open_issues":347,"watchers":7404,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/Microsoft/ChakraCore/pulls/5724"},"html":{"href":"https://github.com/Microsoft/ChakraCore/pull/5724"},"issue":{"href":"https://api.github.com/repos/Microsoft/ChakraCore/issues/5724"},"comments":{"href":"https://api.github.com/repos/Microsoft/ChakraCore/issues/5724/comments"},"review_comments":{"href":"https://api.github.com/repos/Microsoft/ChakraCore/pulls/5724/comments"},"review_comment":{"href":"https://api.github.com/repos/Microsoft/ChakraCore/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/Microsoft/ChakraCore/pulls/5724/commits"},"statuses":{"href":"https://api.github.com/repos/Microsoft/ChakraCore/statuses/3f290d82fa88d8feb398a2916f02d832f87f7322"}},"author_association":"CONTRIBUTOR"}}
{"actor":{"display_login":"fatcerberus"}}