B3/Air should use bubble sort for their insertion sets, because it's faster than...
[WebKit-https.git] / Source / WTF / ChangeLog
index 61d50a657fa2244f7f77b9f3a43432b889e893c8..f6823284b3a286383364851d8d76a93fc24d6e09 100644 (file)
@@ -1,3 +1,35 @@
+2015-11-02  Filip Pizlo  <fpizlo@apple.com>
+
+        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.
+
+        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:
+
 2015-11-02  Andy Estes  <aestes@apple.com>
 
         [Cocoa] Add tvOS and watchOS to SUPPORTED_PLATFORMS