<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[191960] trunk/Source</title>
</head>
<body>

<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt;  }
#msg dl a { font-weight: bold}
#msg dl a:link    { color:#fc3; }
#msg dl a:active  { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff  {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/191960">191960</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-11-03 10:48:45 -0800 (Tue, 03 Nov 2015)</dd>
</dl>

<h3>Log Message</h3>
<pre>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:</pre>

<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3InsertionSetcpp">trunk/Source/JavaScriptCore/b3/B3InsertionSet.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirInsertionSetcpp">trunk/Source/JavaScriptCore/b3/air/AirInsertionSet.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGBlockInsertionSetcpp">trunk/Source/JavaScriptCore/dfg/DFGBlockInsertionSet.cpp</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFwtfCMakeListstxt">trunk/Source/WTF/wtf/CMakeLists.txt</a></li>
</ul>

<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWTFwtfBubbleSorth">trunk/Source/WTF/wtf/BubbleSort.h</a></li>
</ul>

</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (191959 => 191960)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog        2015-11-03 18:44:44 UTC (rev 191959)
+++ trunk/Source/JavaScriptCore/ChangeLog        2015-11-03 18:48:45 UTC (rev 191960)
</span><span class="lines">@@ -1,3 +1,19 @@
</span><ins>+2015-11-02  Filip Pizlo  &lt;fpizlo@apple.com&gt;
+
+        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.
+
+        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.
+
</ins><span class="cx"> 2015-11-03  Csaba Osztrogonác  &lt;ossy@webkit.org&gt;
</span><span class="cx"> 
</span><span class="cx">         Unreviewed, partially revert r191952.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3InsertionSetcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3InsertionSet.cpp (191959 => 191960)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3InsertionSet.cpp        2015-11-03 18:44:44 UTC (rev 191959)
+++ trunk/Source/JavaScriptCore/b3/B3InsertionSet.cpp        2015-11-03 18:48:45 UTC (rev 191960)
</span><span class="lines">@@ -29,12 +29,13 @@
</span><span class="cx"> #if ENABLE(B3_JIT)
</span><span class="cx"> 
</span><span class="cx"> #include &quot;B3BasicBlock.h&quot;
</span><ins>+#include &lt;wtf/BubbleSort.h&gt;
</ins><span class="cx"> 
</span><span class="cx"> namespace JSC { namespace B3 {
</span><span class="cx"> 
</span><span class="cx"> void InsertionSet::execute(BasicBlock* block)
</span><span class="cx"> {
</span><del>-    std::stable_sort(m_insertions.begin(), m_insertions.end());
</del><ins>+    bubbleSort(m_insertions.begin(), m_insertions.end());
</ins><span class="cx">     executeInsertions(block-&gt;m_values, m_insertions);
</span><span class="cx"> }
</span><span class="cx"> 
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirInsertionSetcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirInsertionSet.cpp (191959 => 191960)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirInsertionSet.cpp        2015-11-03 18:44:44 UTC (rev 191959)
+++ trunk/Source/JavaScriptCore/b3/air/AirInsertionSet.cpp        2015-11-03 18:48:45 UTC (rev 191960)
</span><span class="lines">@@ -29,13 +29,13 @@
</span><span class="cx"> #if ENABLE(B3_JIT)
</span><span class="cx"> 
</span><span class="cx"> #include &quot;AirBasicBlock.h&quot;
</span><del>-#include &lt;algorithm&gt;
</del><ins>+#include &lt;wtf/BubbleSort.h&gt;
</ins><span class="cx"> 
</span><span class="cx"> namespace JSC { namespace B3 { namespace Air {
</span><span class="cx"> 
</span><span class="cx"> void InsertionSet::execute(BasicBlock* block)
</span><span class="cx"> {
</span><del>-    std::stable_sort(m_insertions.begin(), m_insertions.end());
</del><ins>+    bubbleSort(m_insertions.begin(), m_insertions.end());
</ins><span class="cx">     executeInsertions(block-&gt;m_insts, m_insertions);
</span><span class="cx"> }
</span><span class="cx"> 
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGBlockInsertionSetcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGBlockInsertionSet.cpp (191959 => 191960)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGBlockInsertionSet.cpp        2015-11-03 18:44:44 UTC (rev 191959)
+++ trunk/Source/JavaScriptCore/dfg/DFGBlockInsertionSet.cpp        2015-11-03 18:48:45 UTC (rev 191960)
</span><span class="lines">@@ -71,9 +71,10 @@
</span><span class="cx">     if (m_insertions.isEmpty())
</span><span class="cx">         return false;
</span><span class="cx">     
</span><del>-    // We allow insertions to be given to us in any order. So, we need to
-    // sort them before running WTF::executeInsertions.
-    std::stable_sort(m_insertions.begin(), m_insertions.end());
</del><ins>+    // We allow insertions to be given to us in any order. So, we need to sort them before
+    // running WTF::executeInsertions. Also, we don't really care if the sort is stable since
+    // basic block order doesn't have semantics - it's just to make code easier to read.
+    std::sort(m_insertions.begin(), m_insertions.end());
</ins><span class="cx"> 
</span><span class="cx">     executeInsertions(m_graph.m_blocks, m_insertions);
</span><span class="cx">     
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (191959 => 191960)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog        2015-11-03 18:44:44 UTC (rev 191959)
+++ trunk/Source/WTF/ChangeLog        2015-11-03 18:48:45 UTC (rev 191960)
</span><span class="lines">@@ -1,3 +1,35 @@
</span><ins>+2015-11-02  Filip Pizlo  &lt;fpizlo@apple.com&gt;
+
+        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:
+
</ins><span class="cx"> 2015-11-02  Andy Estes  &lt;aestes@apple.com&gt;
</span><span class="cx"> 
</span><span class="cx">         [Cocoa] Add tvOS and watchOS to SUPPORTED_PLATFORMS
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (191959 => 191960)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj        2015-11-03 18:44:44 UTC (rev 191959)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj        2015-11-03 18:48:45 UTC (rev 191960)
</span><span class="lines">@@ -26,6 +26,7 @@
</span><span class="cx">                 0F2B66A717B6B4FD00A7AE3F /* FlipBytes.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A517B6B4F700A7AE3F /* FlipBytes.h */; };
</span><span class="cx">                 0F3501641BB258D500F0A2A3 /* WeakRandom.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F3501631BB258C800F0A2A3 /* WeakRandom.h */; };
</span><span class="cx">                 0F4570431BE5B58F0062A629 /* Dominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4570421BE5B58F0062A629 /* Dominators.h */; };
</span><ins>+                0F4570451BE834410062A629 /* BubbleSort.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4570441BE834410062A629 /* BubbleSort.h */; };
</ins><span class="cx">                 0F824A681B7443A0002E345D /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F824A641B7443A0002E345D /* ParkingLot.cpp */; };
</span><span class="cx">                 0F824A691B7443A0002E345D /* ParkingLot.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F824A651B7443A0002E345D /* ParkingLot.h */; };
</span><span class="cx">                 0F87105A16643F190090B0AD /* RawPointer.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F87105916643F190090B0AD /* RawPointer.h */; };
</span><span class="lines">@@ -323,6 +324,7 @@
</span><span class="cx">                 0F300B7D18AB48B400A6D72E /* HashMethod.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = HashMethod.h; sourceTree = &quot;&lt;group&gt;&quot;; };
</span><span class="cx">                 0F3501631BB258C800F0A2A3 /* WeakRandom.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakRandom.h; sourceTree = &quot;&lt;group&gt;&quot;; };
</span><span class="cx">                 0F4570421BE5B58F0062A629 /* Dominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Dominators.h; sourceTree = &quot;&lt;group&gt;&quot;; };
</span><ins>+                0F4570441BE834410062A629 /* BubbleSort.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BubbleSort.h; sourceTree = &quot;&lt;group&gt;&quot;; };
</ins><span class="cx">                 0F824A641B7443A0002E345D /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = &quot;&lt;group&gt;&quot;; };
</span><span class="cx">                 0F824A651B7443A0002E345D /* ParkingLot.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParkingLot.h; sourceTree = &quot;&lt;group&gt;&quot;; };
</span><span class="cx">                 0F87105916643F190090B0AD /* RawPointer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RawPointer.h; sourceTree = &quot;&lt;group&gt;&quot;; };
</span><span class="lines">@@ -742,6 +744,7 @@
</span><span class="cx">                                 A8A47261151A825A004123FF /* BitVector.h */,
</span><span class="cx">                                 A8A47264151A825A004123FF /* BlockStack.h */,
</span><span class="cx">                                 A8A47265151A825A004123FF /* BloomFilter.h */,
</span><ins>+                                0F4570441BE834410062A629 /* BubbleSort.h */,
</ins><span class="cx">                                 A8A47267151A825A004123FF /* BumpPointerAllocator.h */,
</span><span class="cx">                                 EB95E1EF161A72410089A2F5 /* ByteOrder.h */,
</span><span class="cx">                                 A8A4726A151A825A004123FF /* CheckedArithmetic.h */,
</span><span class="lines">@@ -1229,6 +1232,7 @@
</span><span class="cx">                                 FEDACD3E1630F83F00C69634 /* StackStats.h in Headers */,
</span><span class="cx">                                 A8A47429151A825B004123FF /* StaticConstructors.h in Headers */,
</span><span class="cx">                                 A8A4742A151A825B004123FF /* StdLibExtras.h in Headers */,
</span><ins>+                                0F4570451BE834410062A629 /* BubbleSort.h in Headers */,
</ins><span class="cx">                                 C4F8A93719C65EB400B2B15D /* Stopwatch.h in Headers */,
</span><span class="cx">                                 1A6BB769162F300500DD16DB /* StreamBuffer.h in Headers */,
</span><span class="cx">                                 A8A4743B151A825B004123FF /* StringBuffer.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfBubbleSorth"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/BubbleSort.h (0 => 191960)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/BubbleSort.h                                (rev 0)
+++ trunk/Source/WTF/wtf/BubbleSort.h        2015-11-03 18:48:45 UTC (rev 191960)
</span><span class="lines">@@ -0,0 +1,103 @@
</span><ins>+/*
+ * Copyright (C) 2015 Apple Inc. All Rights Reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef BubbleSort_h
+#define BubbleSort_h
+
+namespace WTF {
+
+// Why would you want to use bubble sort? When you know that your input is already mostly
+// sorted! This sort is guaranteed stable (it won't reorder elements that were equal), it
+// doesn't require any scratch memory, and is the fastest available sorting algorithm if your
+// input already happens to be sorted. This sort is also likely to have competetive performance
+// for small inputs, even if they are very unsorted.
+
+// We use this sorting algorithm for compiler insertion sets. An insertion set is usually very
+// nearly sorted. It shouldn't take more than a few bubbles to make it fully sorted. We made
+// this decision deliberately. Here's the performance of the testb3 Complex(64, 384) benchmark
+// with the Air::InsertionSet doing no sorting, std::stable_sorting, and bubbleSorting:
+//
+// no sort:          8.8222 +- 0.1911 ms.
+// std::stable_sort: 9.0135 +- 0.1418 ms.
+// bubbleSort:       8.8457 +- 0.1511 ms.
+//
+// Clearly, bubble sort is superior.
+//
+// Note that the critical piece here is that insertion sets tend to be small, they must be
+// sorted, the sort must be stable, they are usually already sorted to begin with, and when they
+// are unsorted it's usually because of a few out-of-place elements.
+
+template&lt;typename IteratorType, typename LessThan&gt;
+void bubbleSort(IteratorType begin, IteratorType end, const LessThan&amp; lessThan)
+{
+    for (;;) {
+        bool changed = false;
+        ASSERT(end &gt;= begin);
+        size_t limit = end - begin;
+        for (size_t i = limit; i-- &gt; 1;) {
+            if (lessThan(begin[i], begin[i - 1])) {
+                std::swap(begin[i], begin[i - 1]);
+                changed = true;
+            }
+        }
+        if (!changed)
+            return;
+        // After one run, the first element in the list is guaranteed to be the smallest.
+        begin++;
+
+        // Now go in the other direction. This eliminates most sorting pathologies.
+        changed = false;
+        ASSERT(end &gt;= begin);
+        limit = end - begin;
+        for (size_t i = 1; i &lt; limit; ++i) {
+            if (lessThan(begin[i], begin[i - 1])) {
+                std::swap(begin[i], begin[i - 1]);
+                changed = true;
+            }
+        }
+        if (!changed)
+            return;
+        // Now the last element is guaranteed to be the largest.
+        end--;
+    }
+}
+
+template&lt;typename IteratorType&gt;
+void bubbleSort(IteratorType begin, IteratorType end)
+{
+    bubbleSort(
+        begin, end,
+        [] (typename std::iterator_traits&lt;IteratorType&gt;::value_type left,
+            typename std::iterator_traits&lt;IteratorType&gt;::value_type right) -&gt; bool {
+            return left &lt; right;
+        });
+}
+
+} // namespace WTF
+
+using WTF::bubbleSort;
+
+#endif // BubbleSort_h
+
</ins></span></pre></div>
<a id="trunkSourceWTFwtfCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/CMakeLists.txt (191959 => 191960)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/CMakeLists.txt        2015-11-03 18:44:44 UTC (rev 191959)
+++ trunk/Source/WTF/wtf/CMakeLists.txt        2015-11-03 18:48:45 UTC (rev 191960)
</span><span class="lines">@@ -6,6 +6,7 @@
</span><span class="cx">     BagToHashMap.h
</span><span class="cx">     BitVector.h
</span><span class="cx">     Bitmap.h
</span><ins>+    BubbleSort.h
</ins><span class="cx">     BumpPointerAllocator.h
</span><span class="cx">     ByteOrder.h
</span><span class="cx">     CompilationThread.h
</span></span></pre>
</div>
</div>

</body>
</html>