Modified: trunk/Source/_javascript_Core/ChangeLog (185066 => 185067)
--- trunk/Source/_javascript_Core/ChangeLog 2015-06-01 18:17:40 UTC (rev 185066)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-06-01 18:40:30 UTC (rev 185067)
@@ -1,3 +1,30 @@
+2015-05-29 Geoffrey Garen <[email protected]>
+
+ 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 <[email protected]>
HandlerInfo::initialize() should not assume that CodeLocationLabel is available.
Modified: trunk/Source/_javascript_Core/builtins/Array.prototype.js (185066 => 185067)
--- trunk/Source/_javascript_Core/builtins/Array.prototype.js 2015-06-01 18:17:40 UTC (rev 185066)
+++ trunk/Source/_javascript_Core/builtins/Array.prototype.js 2015-06-01 18:40:30 UTC (rev 185067)
@@ -420,8 +420,7 @@
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 @@
var value = array[src];
if (value === undefined)
continue;
+
array[dst++] = value;
}
@@ -451,6 +451,17 @@
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 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 @@
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)
