REGRESSION: These sorting idioms used by Peacekeeper and Browsermark are ~20X slower
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 1 Jun 2015 18:40:30 +0000 (18:40 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 1 Jun 2015 18:40:30 +0000 (18:40 +0000)
https://bugs.webkit.org/show_bug.cgi?id=145412

Reviewed by Darin Adler.

Moar speedup.

Added a bucket sort for string sorting.

* builtins/Array.prototype.js:
(sort.compactSparse):
(sort.compactSlow):
(sort.compact): Split out a compaction fast path for dense arrays. Without
it, compaction can increase sort time by 2X for simple sorts.

(sort.bucketSort):
(sort.stringSort): Use a bucket sorting algorithm if we know we're sorting
strings. This makes average case string sorting O(N) with O(N) additional
memory use.

The worst case bucket sort can require O(M * N) additional
space. We avoid this by falling back to merge sort when things are
simple or overly duplicative. These are the two cases that accumulate
excessive -- and potentially pathological -- bucketing overhead.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@185067 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/builtins/Array.prototype.js

index 6b8a274..adc31df 100644 (file)
@@ -1,3 +1,30 @@
+2015-05-29  Geoffrey Garen  <ggaren@apple.com>
+
+        REGRESSION: These sorting idioms used by Peacekeeper and Browsermark are ~20X slower
+        https://bugs.webkit.org/show_bug.cgi?id=145412
+
+        Reviewed by Darin Adler.
+
+        Moar speedup.
+
+        Added a bucket sort for string sorting.
+
+        * builtins/Array.prototype.js:
+        (sort.compactSparse):
+        (sort.compactSlow):
+        (sort.compact): Split out a compaction fast path for dense arrays. Without
+        it, compaction can increase sort time by 2X for simple sorts.
+
+        (sort.bucketSort):
+        (sort.stringSort): Use a bucket sorting algorithm if we know we're sorting
+        strings. This makes average case string sorting O(N) with O(N) additional
+        memory use.
+
+        The worst case bucket sort can require O(M * N) additional
+        space. We avoid this by falling back to merge sort when things are
+        simple or overly duplicative. These are the two cases that accumulate
+        excessive -- and potentially pathological -- bucketing overhead.
+
 2015-06-01  Mark Lam  <mark.lam@apple.com>
 
         HandlerInfo::initialize() should not assume that CodeLocationLabel is available.
index dd022d3..b5c190f 100644 (file)
@@ -420,8 +420,7 @@ function sort(comparator)
         return valueCount;
     }
 
-    // Move undefineds and holes to the end of an array. Result is [values..., undefineds..., holes...].
-    function compact(array, length)
+    function compactSlow(array, length)
     {
         var holeCount = 0;
 
@@ -436,6 +435,7 @@ function sort(comparator)
             var value = array[src];
             if (value === undefined)
                 continue;
+
             array[dst++] = value;
         }
 
@@ -451,6 +451,17 @@ function sort(comparator)
         return valueCount;
     }
 
+    // Move undefineds and holes to the end of an array. Result is [values..., undefineds..., holes...].
+    function compact(array, length)
+    {
+        for (var i = 0; i < array.length; ++i) {
+            if (array[i] === undefined)
+                return compactSlow(array, length);
+        }
+
+        return length;
+    }
+
     function merge(dst, src, srcIndex, srcEnd, width, comparator)
     {
         var left = srcIndex;
@@ -492,6 +503,39 @@ function sort(comparator)
         }
     }
 
+    function bucketSort(array, dst, bucket, depth)
+    {
+        if (bucket.length < 32 || depth > 32) {
+            mergeSort(bucket, bucket.length, stringComparator);
+            for (var i = 0; i < bucket.length; ++i)
+                array[dst++] = bucket[i].value;
+            return dst;
+        }
+
+        var buckets = [ ];
+        for (var i = 0; i < bucket.length; ++i) {
+            var entry = bucket[i];
+            var string = entry.string;
+            if (string.length == depth) {
+                array[dst++] = entry.value;
+                continue;
+            }
+
+            var c = string.@charCodeAt(depth);
+            if (!buckets[c])
+                buckets[c] = [ ];
+            buckets[c][buckets[c].length] = entry;
+        }
+
+        for (var i = 0; i < buckets.length; ++i) {
+            if (!buckets[i])
+                continue;
+            dst = bucketSort(array, dst, buckets[i], depth + 1);
+        }
+
+        return dst;
+    }
+
     function comparatorSort(array, comparator)
     {
         var length = array.length >>> 0;
@@ -520,10 +564,7 @@ function sort(comparator)
         for (var i = 0; i < valueCount; ++i)
             strings[i] = { string: @toString(array[i]), value: array[i] };
 
-        mergeSort(strings, valueCount, stringComparator);
-
-        for (var i = 0; i < valueCount; ++i)
-            array[i] = strings[i].value;
+        bucketSort(array, 0, strings, 0);
     }
 
     if (this === null)