B3/Air should use bubble sort for their insertion sets, because it's faster than...
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 3 Nov 2015 18:48:45 +0000 (18:48 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 3 Nov 2015 18:48:45 +0000 (18:48 +0000)
commitf38f0bbd535334bd4a6309b3b0d4971c40eb4bf6
tree0c86ac38785a7a361974aa5987ca283f9c50efe9
parent064a2fe7505484081fc4eb98ee563371d25ec271
B3/Air should use bubble sort for their insertion sets, because it's faster than std::stable_sort
https://bugs.webkit.org/show_bug.cgi?id=150828

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

Undo the 2% compile time regression caused by http://trac.webkit.org/changeset/191913.

* b3/B3InsertionSet.cpp:
(JSC::B3::InsertionSet::execute): Switch to bubble sort.
* b3/air/AirInsertionSet.cpp:
(JSC::B3::Air::InsertionSet::execute): Switch to bubble sort.
* dfg/DFGBlockInsertionSet.cpp:
(JSC::DFG::BlockInsertionSet::execute): Switch back to quicksort.

Source/WTF:

Add a pretty good bubble sort implementation to WTF. This implementation has three
common tricks:

- Forward and backward scans. This reduces the severity of certain kinds of bubble sort
  pathologies.

- Return if a scan finds the list to be sorted. This gives the algorithm one of its most
  attractive properties: it's super fast when the list is already sorted.

- Each scan eliminates one element from future scans. This makes the algorithm no worse
  than insertion sort.

Why do we want this? Because bubble sort is a really great stable sort for small lists,
or large lists in which only a handful of elements are out of order. Compiler insertion
sets tend to be one of those or somewhere in between: usually they are very small, and
usually they are sorted. It's rare that an element will be out of order, and when it is,
it's usually very close to where it's supposed to be.

This is a significant speed-up for B3 compile times.

* WTF.xcodeproj/project.pbxproj:
* wtf/BubbleSort.h: Added.
(WTF::bubbleSort):
* wtf/CMakeLists.txt:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@191960 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/B3InsertionSet.cpp
Source/JavaScriptCore/b3/air/AirInsertionSet.cpp
Source/JavaScriptCore/dfg/DFGBlockInsertionSet.cpp
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/BubbleSort.h [new file with mode: 0644]
Source/WTF/wtf/CMakeLists.txt