<!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" /><style type="text/css"><!--
#msg dl { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer { 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, #msg p { overflow: auto; background: #ffc; border: 1px #fc0 solid; padding: 6px; }
#msg ul { overflow: auto; }
#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>
<title>[28782] trunk/JavaScriptCore</title>
</head>
<body>

<div id="msg">
<dl>
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/28782">28782</a></dd>
<dt>Author</dt> <dd>mrowe@apple.com</dd>
<dt>Date</dt> <dd>2007-12-16 17:14:36 -0800 (Sun, 16 Dec 2007)</dd>
</dl>

<h3>Log Message</h3>
<pre>Fix http://bugs.webkit.org/show_bug.cgi?id=16448 ([GTK] Celtic Kane JavaScript performance on Array test is slow relative to Mac).

Reviewed by Maciej Stachowiak.

* kjs/array_instance.cpp:
(KJS::compareByStringPairForQSort):
(KJS::ArrayInstance::sort): Convert JSValue's to strings once up front and then sort the
results.  This avoids calling toString twice per comparison, but requires a temporary buffer
so we only use this approach in cases where the array being sorted is not too large.</pre>

<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkJavaScriptCoreChangeLog">trunk/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkJavaScriptCorekjsarray_instancecpp">trunk/JavaScriptCore/kjs/array_instance.cpp</a></li>
</ul>

</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/JavaScriptCore/ChangeLog (28781 => 28782)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JavaScriptCore/ChangeLog        2007-12-17 00:24:48 UTC (rev 28781)
+++ trunk/JavaScriptCore/ChangeLog        2007-12-17 01:14:36 UTC (rev 28782)
</span><span class="lines">@@ -1,3 +1,16 @@
</span><ins>+2007-12-16  Mark Rowe  &lt;mrowe@apple.com&gt;
+
+        Reviewed by Maciej Stachowiak.
+
+        Fix http://bugs.webkit.org/show_bug.cgi?id=16448
+        Bug 16448: [GTK] Celtic Kane JavaScript performance on Array test is slow relative to Mac
+
+        * kjs/array_instance.cpp:
+        (KJS::compareByStringPairForQSort):
+        (KJS::ArrayInstance::sort): Convert JSValue's to strings once up front and then sort the
+        results.  This avoids calling toString twice per comparison, but requires a temporary buffer
+        so we only use this approach in cases where the array being sorted is not too large.
+
</ins><span class="cx"> 2007-12-16  Geoffrey Garen  &lt;ggaren@apple.com&gt;
</span><span class="cx"> 
</span><span class="cx">         Reviewed by Darin Adler and Maciej Stachowiak.
</span></span></pre></div>
<a id="trunkJavaScriptCorekjsarray_instancecpp"></a>
<div class="modfile"><h4>Modified: trunk/JavaScriptCore/kjs/array_instance.cpp (28781 => 28782)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JavaScriptCore/kjs/array_instance.cpp        2007-12-17 00:24:48 UTC (rev 28781)
+++ trunk/JavaScriptCore/kjs/array_instance.cpp        2007-12-17 01:14:36 UTC (rev 28782)
</span><span class="lines">@@ -49,7 +49,7 @@
</span><span class="cx"> static const unsigned sparseArrayCutoff = 10000;
</span><span class="cx"> static const unsigned minDensityMultiplier = 8;
</span><span class="cx"> 
</span><del>-static const unsigned mergeSortCutoff = 10000;
</del><ins>+static const unsigned copyingSortCutoff = 50000;
</ins><span class="cx"> 
</span><span class="cx"> const ClassInfo ArrayInstance::info = {&quot;Array&quot;, 0, 0};
</span><span class="cx"> 
</span><span class="lines">@@ -429,8 +429,14 @@
</span><span class="cx">     }
</span><span class="cx"> }
</span><span class="cx"> 
</span><ins>+static int compareByStringPairForQSort(const void* a, const void* b)
+{
+    const std::pair&lt;JSValue*, UString&gt;* va = static_cast&lt;const std::pair&lt;JSValue*, UString&gt;*&gt;(a);
+    const std::pair&lt;JSValue*, UString&gt;* vb = static_cast&lt;const std::pair&lt;JSValue*, UString&gt;*&gt;(b);
+    return compare(va-&gt;second, vb-&gt;second);
+}
+
</ins><span class="cx"> static ExecState* execForCompareByStringForQSort = 0;
</span><del>-
</del><span class="cx"> static int compareByStringForQSort(const void* a, const void* b)
</span><span class="cx"> {
</span><span class="cx">     ExecState* exec = execForCompareByStringForQSort;
</span><span class="lines">@@ -447,34 +453,34 @@
</span><span class="cx"> {
</span><span class="cx">     unsigned lengthNotIncludingUndefined = compactForSorting();
</span><span class="cx"> 
</span><del>-    ExecState* oldExec = execForCompareByStringForQSort;
-    execForCompareByStringForQSort = exec;
</del><ins>+    if (lengthNotIncludingUndefined &lt; copyingSortCutoff) {
+        // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
+        // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
+        // buffer.  For large arrays, we fall back to a qsort on the JavaScriptValues to avoid creating copies.
</ins><span class="cx"> 
</span><del>-#if HAVE(MERGESORT)
-    // Because mergesort usually does fewer compares, it is faster than qsort here.
-    // However, because it requires extra copies of the storage buffer, don't use it for very
-    // large arrays.
</del><ins>+        Vector&lt;std::pair&lt;JSValue*, UString&gt; &gt; values(lengthNotIncludingUndefined);
+        for (size_t i = 0; i &lt; lengthNotIncludingUndefined; i++) {
+            JSValue* value = m_storage-&gt;m_vector[i];
+            ASSERT(!value-&gt;isUndefined());
+            values[i].first = value;
+            values[i].second = value-&gt;toString(exec);
+        }
</ins><span class="cx"> 
</span><del>-    // FIXME: Since we sort by string value, a fast algorithm might be to convert all the
-    // values to string once up front, and then use a radix sort. That would be O(N) rather
-    // than O(N log N).
</del><ins>+        // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
+        // than O(N log N).
</ins><span class="cx"> 
</span><del>-    if (lengthNotIncludingUndefined &lt; mergeSortCutoff) {
-        // During the sort, we could do a garbage collect, and it's important to still
-        // have references to every object in the array for ArrayInstance::mark.
-        // The mergesort algorithm does not guarantee this, so we sort a copy rather
-        // than the original.
-        size_t size = storageSize(m_vectorLength);
-        ArrayStorage* copy = static_cast&lt;ArrayStorage*&gt;(fastMalloc(size));
-        memcpy(copy, m_storage, size);
-        mergesort(copy-&gt;m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
-        fastFree(m_storage);
-        m_storage = copy;
-        execForCompareByStringForQSort = oldExec;
</del><ins>+#if HAVE(MERGESORT)
+        mergesort(values.begin(), values.size(), sizeof(std::pair&lt;JSValue*, UString&gt;), compareByStringPairForQSort);
+#else
+        qsort(values.begin(), values.size(), sizeof(std::pair&lt;JSValue*, UString&gt;), compareByStringPairForQSort);
+#endif
+        for (size_t i = 0; i &lt; lengthNotIncludingUndefined; i++)
+            m_storage-&gt;m_vector[i] = values[i].first;
</ins><span class="cx">         return;
</span><span class="cx">     }
</span><del>-#endif
</del><span class="cx"> 
</span><ins>+    ExecState* oldExec = execForCompareByStringForQSort;
+    execForCompareByStringForQSort = exec;
</ins><span class="cx">     qsort(m_storage-&gt;m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
</span><span class="cx">     execForCompareByStringForQSort = oldExec;
</span><span class="cx"> }
</span><span class="lines">@@ -528,7 +534,7 @@
</span><span class="cx">     // FIXME: A tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even
</span><span class="cx">     // better job of minimizing compares.
</span><span class="cx"> 
</span><del>-    if (lengthNotIncludingUndefined &lt; mergeSortCutoff) {
</del><ins>+    if (lengthNotIncludingUndefined &lt; copyingSortCutoff) {
</ins><span class="cx">         // During the sort, we could do a garbage collect, and it's important to still
</span><span class="cx">         // have references to every object in the array for ArrayInstance::mark.
</span><span class="cx">         // The mergesort algorithm does not guarantee this, so we sort a copy rather
</span></span></pre>
</div>
</div>

</body>
</html>