Title: [113391] trunk/Source/_javascript_Core
- Revision
- 113391
- Author
- [email protected]
- Date
- 2012-04-05 16:08:13 -0700 (Thu, 05 Apr 2012)
Log Message
Use QuickSort when sorting primitive values by string representation
https://bugs.webkit.org/show_bug.cgi?id=83312
Patch by Benjamin Poulain <[email protected]> on 2012-04-05
Reviewed by Gavin Barraclough.
When the value we are sorting are all primitive values, we do not need to
ensure a stable sort as two values with equal string representation are
indistinguishable from _javascript_.
This gives about 16% performance increase when sorting primitive values.
* runtime/JSArray.cpp:
(JSC::JSArray::sort):
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (113390 => 113391)
--- trunk/Source/_javascript_Core/ChangeLog 2012-04-05 23:00:16 UTC (rev 113390)
+++ trunk/Source/_javascript_Core/ChangeLog 2012-04-05 23:08:13 UTC (rev 113391)
@@ -1,3 +1,19 @@
+2012-04-05 Benjamin Poulain <[email protected]>
+
+ Use QuickSort when sorting primitive values by string representation
+ https://bugs.webkit.org/show_bug.cgi?id=83312
+
+ Reviewed by Gavin Barraclough.
+
+ When the value we are sorting are all primitive values, we do not need to
+ ensure a stable sort as two values with equal string representation are
+ indistinguishable from _javascript_.
+
+ This gives about 16% performance increase when sorting primitive values.
+
+ * runtime/JSArray.cpp:
+ (JSC::JSArray::sort):
+
2012-04-05 Oliver Hunt <[email protected]>
SIGILL in _javascript_Core on a Geode processor
Modified: trunk/Source/_javascript_Core/runtime/JSArray.cpp (113390 => 113391)
--- trunk/Source/_javascript_Core/runtime/JSArray.cpp 2012-04-05 23:00:16 UTC (rev 113390)
+++ trunk/Source/_javascript_Core/runtime/JSArray.cpp 2012-04-05 23:08:13 UTC (rev 113391)
@@ -1475,10 +1475,12 @@
Heap::heap(this)->pushTempSortVector(&values);
+ bool isSortingPrimitiveValues = true;
for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
JSValue value = m_storage->m_vector[i].get();
ASSERT(!value.isUndefined());
values[i].first = value;
+ isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
}
// FIXME: The following loop continues to call toString on subsequent values even after
@@ -1496,7 +1498,10 @@
// than O(N log N).
#if HAVE(MERGESORT)
- mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+ if (isSortingPrimitiveValues)
+ qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+ else
+ mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
#else
// FIXME: The qsort library function is likely to not be a stable sort.
// ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
_______________________________________________
webkit-changes mailing list
[email protected]
http://lists.webkit.org/mailman/listinfo.cgi/webkit-changes
