<!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>[183749] trunk/Source/JavaScriptCore</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/183749">183749</a></dd>
<dt>Author</dt> <dd>ggaren@apple.com</dd>
<dt>Date</dt> <dd>2015-05-04 10:27:34 -0700 (Mon, 04 May 2015)</dd>
</dl>

<h3>Log Message</h3>
<pre>REGRESSION(<a href="http://trac.webkit.org/projects/webkit/changeset/183570">r183570</a>): jslib-traverse-jquery is 22% slower
https://bugs.webkit.org/show_bug.cgi?id=144476

Reviewed by Sam Weinig.

jslib-traverse-jquery is now 31% faster than its unregressed baseline.

The jQuery algorithm for sorting DOM nodes is so pathologically slow that,
to my knowledge, the topic of how to optimize it is not covered in any
literature about sorting.

On the slowest jQuery sorting test -- prevAll -- our new
Array.prototype.sort, compared to its predecessor, performed 12% fewer
comparisons and requireed 10X less overhead per comparison. Yet, it was
slower.

It was slower because it inadvertantly increased the average cost of the
comparison function by 2X. jQuery uses compareDocumentPosition to compare
DOM nodes, and compareDocumentPosition(a, b) is O(N) in the distance
required to traverse backwards from b to a. In prevAll, we encounter the
worst case for merge sort of compareDocumentPosition: A long list of DOM
nodes in mostly reverse order. In this case, merge sort will sequentially
compareDocumentPosition(a, b), where a is not reachable backwards from
b, and therefore compareDocumentPosition will traverse the whole sibling
list.

The solution is simple enough: Call compareDocumentPosition(b, a) instead.

This is a pretty silly thing to do, but it is harmless, and jQuery is
popular, so let's do it.

We do not risk suffering the same problem in reverse when sorting a long
list of DOM nodes in forward order. (We still have a 37% speedup on the
nextAll benchmark.) The reason is that merge sort performs 2X fewer
comparisons when the list is already sorted, so we can worry less about
the cost of each comparison.

A fully principled soultion to this problem would probably do something
like Python's timsort, which special-cases ordered ranges to perform
only O(n) comparisons. But that would contradict our original
goal of just having something simple that works.

Another option is for elements to keep a compareDocumentPosition cache,
like a node list cache, which allows you to determine the absolute
position of a node using a hash lookup. I will leave this as an exercise
for kling.

* builtins/Array.prototype.js:
(sort.merge): Compare in an order that is favorable to a comparator
that calls compareDocumentPosition.</pre>

<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCorebuiltinsArrayprototypejs">trunk/Source/JavaScriptCore/builtins/Array.prototype.js</a></li>
</ul>

</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (183748 => 183749)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog        2015-05-04 17:25:21 UTC (rev 183748)
+++ trunk/Source/JavaScriptCore/ChangeLog        2015-05-04 17:27:34 UTC (rev 183749)
</span><span class="lines">@@ -1,3 +1,56 @@
</span><ins>+2015-05-01  Geoffrey Garen  &lt;ggaren@apple.com&gt;
+
+        REGRESSION(r183570): jslib-traverse-jquery is 22% slower
+        https://bugs.webkit.org/show_bug.cgi?id=144476
+
+        Reviewed by Sam Weinig.
+
+        jslib-traverse-jquery is now 31% faster than its unregressed baseline.
+
+        The jQuery algorithm for sorting DOM nodes is so pathologically slow that,
+        to my knowledge, the topic of how to optimize it is not covered in any
+        literature about sorting.
+
+        On the slowest jQuery sorting test -- prevAll -- our new
+        Array.prototype.sort, compared to its predecessor, performed 12% fewer
+        comparisons and requireed 10X less overhead per comparison. Yet, it was
+        slower.
+
+        It was slower because it inadvertantly increased the average cost of the
+        comparison function by 2X. jQuery uses compareDocumentPosition to compare
+        DOM nodes, and compareDocumentPosition(a, b) is O(N) in the distance
+        required to traverse backwards from b to a. In prevAll, we encounter the
+        worst case for merge sort of compareDocumentPosition: A long list of DOM
+        nodes in mostly reverse order. In this case, merge sort will sequentially
+        compareDocumentPosition(a, b), where a is not reachable backwards from
+        b, and therefore compareDocumentPosition will traverse the whole sibling
+        list.
+
+        The solution is simple enough: Call compareDocumentPosition(b, a) instead.
+
+        This is a pretty silly thing to do, but it is harmless, and jQuery is
+        popular, so let's do it.
+
+        We do not risk suffering the same problem in reverse when sorting a long
+        list of DOM nodes in forward order. (We still have a 37% speedup on the
+        nextAll benchmark.) The reason is that merge sort performs 2X fewer
+        comparisons when the list is already sorted, so we can worry less about
+        the cost of each comparison.
+
+        A fully principled soultion to this problem would probably do something
+        like Python's timsort, which special-cases ordered ranges to perform
+        only O(n) comparisons. But that would contradict our original
+        goal of just having something simple that works.
+
+        Another option is for elements to keep a compareDocumentPosition cache,
+        like a node list cache, which allows you to determine the absolute
+        position of a node using a hash lookup. I will leave this as an exercise
+        for kling.
+
+        * builtins/Array.prototype.js:
+        (sort.merge): Compare in an order that is favorable to a comparator
+        that calls compareDocumentPosition.
+
</ins><span class="cx"> 2015-05-04  Csaba Osztrogonác  &lt;ossy@webkit.org&gt;
</span><span class="cx"> 
</span><span class="cx">         [cmake] Fix generate-js-builtins related incremental build issue
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebuiltinsArrayprototypejs"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/builtins/Array.prototype.js (183748 => 183749)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/builtins/Array.prototype.js        2015-05-04 17:25:21 UTC (rev 183748)
+++ trunk/Source/JavaScriptCore/builtins/Array.prototype.js        2015-05-04 17:27:34 UTC (rev 183749)
</span><span class="lines">@@ -398,7 +398,7 @@
</span><span class="cx"> 
</span><span class="cx">         for (var dstIndex = left; dstIndex &lt; rightEnd; ++dstIndex) {
</span><span class="cx">             if (right &lt; rightEnd) {
</span><del>-                if (left &gt;= leftEnd || comparator(src[left], src[right]) &gt; 0) {
</del><ins>+                if (left &gt;= leftEnd || comparator(src[right], src[left]) &lt; 0) {
</ins><span class="cx">                     dst[dstIndex] = src[right++];
</span><span class="cx">                     continue;
</span><span class="cx">                 }
</span></span></pre>
</div>
</div>

</body>
</html>