It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 29 Apr 2015 19:48:00 +0000 (19:48 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 29 Apr 2015 19:48:00 +0000 (19:48 +0000)
commitb680b534071e96c60a0ba40b472c7722e3ce07ba
treeba85c27bd9acf6384c4691327e097540c6d91bfe
parent103089758fe9ab3800d4883698740865d228e652
It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.
https://bugs.webkit.org/show_bug.cgi?id=144013

Reviewed by Mark Lam.

Source/JavaScriptCore:

This patch implements Array.prototype.sort in JavaScript, removing the
C++ implementations. It is simpler and less error-prone to express our
operations in JavaScript, which provides memory safety, exception safety,
and recursion safety.

The performance result is mixed, but net positive in my opinion. It's
difficult to enumerate all the results, since we used to have so many
different sorting modes, and there are lots of different data patterns
across which you might want to measure sorting. Suffice it to say:

    (*) The benchmarks we track are faster or unchanged.

    (*) Sorting random input using a comparator -- which we think is
    common -- is 3X faster.

    (*) Sorting random input in a non-array object -- which jQuery does
    -- is 4X faster.

    (*) Sorting random input in a compact array of integers using a
    trivial pattern-matchable comparator is 2X *slower*.

* builtins/Array.prototype.js:
(sort.min):
(sort.stringComparator):
(sort.compactSparse): Special case compaction for sparse arrays because
we don't want to hang when sorting new Array(BIG).

(sort.compact):
(sort.merge):
(sort.mergeSort): Use merge sort because it's a reasonably efficient
stable sort. We have evidence that some sites depend on stable sort,
even though the ES6 spec does not mandate it. (See
<http://trac.webkit.org/changeset/33967>.)

This is a textbook implementation of merge sort with three optimizations:

    (1) Use iteration instead of recursion;

    (2) Use array subscripting instead of array copying in order to
    create logical sub-lists without creating physical sub-lists;

    (3) Swap src and dst at each iteration instead of copying src into
    dst, and only copy src into the subject array at the end if src is
    not the subject array.

(sort.inflate):
(sort.comparatorSort):
(sort): Sort in JavaScript for the win.

* builtins/BuiltinExecutables.cpp:
(JSC::BuiltinExecutables::createExecutableInternal): Allow non-private
names so we can use helper functions.

* bytecode/CodeBlock.h:
(JSC::CodeBlock::isNumericCompareFunction): Deleted.
* bytecode/UnlinkedCodeBlock.cpp:
(JSC::UnlinkedCodeBlock::UnlinkedCodeBlock):
* bytecode/UnlinkedCodeBlock.h:
(JSC::UnlinkedCodeBlock::setIsNumericCompareFunction): Deleted.
(JSC::UnlinkedCodeBlock::isNumericCompareFunction): Deleted.
* bytecompiler/BytecodeGenerator.cpp:
(JSC::BytecodeGenerator::setIsNumericCompareFunction): Deleted.
* bytecompiler/BytecodeGenerator.h:
* bytecompiler/NodesCodegen.cpp:
(JSC::FunctionNode::emitBytecode): We don't do this special casing based
on pattern matching anymore. This was mainly an optimization to avoid
the overhead of calling from C++ to JS, which we now avoid by
sorting in JS.

* heap/Heap.cpp:
(JSC::Heap::markRoots):
(JSC::Heap::pushTempSortVector): Deleted.
(JSC::Heap::popTempSortVector): Deleted.
(JSC::Heap::visitTempSortVectors): Deleted.
* heap/Heap.h: We don't have temp sort vectors anymore because we sort
in JavaScript using a normal JavaScript array for our temporary storage.

* parser/Parser.cpp:
(JSC::Parser<LexerType>::parseInner): Allow capturing so we can use
helper functions.

* runtime/ArrayPrototype.cpp:
(JSC::isNumericCompareFunction): Deleted.
(JSC::attemptFastSort): Deleted.
(JSC::performSlowSort): Deleted.
(JSC::arrayProtoFuncSort): Deleted.

* runtime/CommonIdentifiers.h: New strings used by sort.

* runtime/JSArray.cpp:
(JSC::compareNumbersForQSortWithInt32): Deleted.
(JSC::compareNumbersForQSortWithDouble): Deleted.
(JSC::compareNumbersForQSort): Deleted.
(JSC::compareByStringPairForQSort): Deleted.
(JSC::JSArray::sortNumericVector): Deleted.
(JSC::JSArray::sortNumeric): Deleted.
(JSC::ContiguousTypeAccessor::getAsValue): Deleted.
(JSC::ContiguousTypeAccessor::setWithValue): Deleted.
(JSC::ContiguousTypeAccessor::replaceDataReference): Deleted.
(JSC::ContiguousTypeAccessor<ArrayWithDouble>::getAsValue): Deleted.
(JSC::ContiguousTypeAccessor<ArrayWithDouble>::setWithValue): Deleted.
(JSC::ContiguousTypeAccessor<ArrayWithDouble>::replaceDataReference): Deleted.
(JSC::JSArray::sortCompactedVector): Deleted.
(JSC::JSArray::sort): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::get_less): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::set_less): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::get_greater): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::set_greater): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::get_balance_factor): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::set_balance_factor): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::compare_key_key): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::compare_key_node): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::compare_node_node): Deleted.
(JSC::AVLTreeAbstractorForArrayCompare::null): Deleted.
(JSC::JSArray::sortVector): Deleted.
(JSC::JSArray::compactForSorting): Deleted.
* runtime/JSArray.h:

* runtime/JSGlobalObject.cpp:
(JSC::JSGlobalObject::init):
* runtime/ObjectConstructor.cpp:
(JSC::ObjectConstructor::finishCreation): Provide some builtins used
by sort.

Source/WTF:

Remove this custom tree implementation because it is unused. (It was
previously used to achieve a stable array sort in certain cases.)

* WTF.vcxproj/WTF.vcxproj:
* WTF.vcxproj/WTF.vcxproj.filters:
* WTF.xcodeproj/project.pbxproj:
* wtf/AVLTree.h: Removed.
* wtf/CMakeLists.txt:

LayoutTests:

* js/script-tests/array-holes.js:
* js/array-holes-expected.txt: This result now matches Firefox. We see
'peekaboo', which is a prototype property, rather than a hole, because
sorting uses [[Get]], which sees prototype properties.

The ES6 spec says that sorting should use [[Get]], so this new result
matches the spec a little better -- although the spec also says that the
result of sorting is undefined in this case because of the presence of
an indexed property in the prototype chain.

* js/dom/array-prototype-properties-expected.txt: Updated error message
to match other array prototype error messages.

* js/comparefn-sort-stability-expected.txt:
* js/script-tests/comparefn-sort-stability.js: Made this test bigger in
order to demonstrate that Firefox and Safari use a stable sort, and
Chrome does not.

* js/script-tests/array-sort-sparse.js:
* js/array-sort-sparse-expected.txt: Added some tests for things I got
wrong in this patch.

* script-tests/sort-with-side-effecting-comparisons.js: Made this test
shorter so that it wouldn't hang debug builds. This test is O(N^2). It
used to terminate sooner because our sort implementation would (sometimes)
terminate sooner if you shrank the array. Our new sort does not accept
intermediate updates to the array's length, matching Firefox. I spoke
to Gavin and Alexey about this, and we think that going out of our way
to honor length changes mid-sort doesn't make much sense because it's
not possible to honor the general case of value changes in a predictable
way.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@183570 268f45cc-cd09-0410-ab3c-d52691b4dbfc
32 files changed:
LayoutTests/ChangeLog
LayoutTests/js/array-holes-expected.txt
LayoutTests/js/array-sort-sparse-expected.txt
LayoutTests/js/comparefn-sort-stability-expected.txt
LayoutTests/js/dom/array-prototype-properties-expected.txt
LayoutTests/js/script-tests/array-holes.js
LayoutTests/js/script-tests/array-sort-sparse.js
LayoutTests/js/script-tests/comparefn-sort-stability.js
LayoutTests/js/script-tests/sort-with-side-effecting-comparisons.js
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/builtins/Array.prototype.js
Source/JavaScriptCore/builtins/BuiltinExecutables.cpp
Source/JavaScriptCore/bytecode/CodeBlock.h
Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp
Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h
Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp
Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h
Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp
Source/JavaScriptCore/heap/Heap.cpp
Source/JavaScriptCore/heap/Heap.h
Source/JavaScriptCore/runtime/ArrayPrototype.cpp
Source/JavaScriptCore/runtime/CommonIdentifiers.h
Source/JavaScriptCore/runtime/JSArray.cpp
Source/JavaScriptCore/runtime/JSArray.h
Source/JavaScriptCore/runtime/JSGlobalObject.cpp
Source/JavaScriptCore/runtime/ObjectConstructor.cpp
Source/WTF/ChangeLog
Source/WTF/WTF.vcxproj/WTF.vcxproj
Source/WTF/WTF.vcxproj/WTF.vcxproj.filters
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/AVLTree.h [deleted file]
Source/WTF/wtf/CMakeLists.txt