Modified: trunk/Source/_javascript_Core/ChangeLog (90101 => 90102)
--- trunk/Source/_javascript_Core/ChangeLog 2011-06-30 10:40:32 UTC (rev 90101)
+++ trunk/Source/_javascript_Core/ChangeLog 2011-06-30 10:56:49 UTC (rev 90102)
@@ -1,3 +1,17 @@
+2011-06-30 Oliver Varga <[email protected]>
+
+ Reviewed by Nikolas Zimmermann.
+
+ Speed up SVGSMILElement::findInstanceTime.
+ https://bugs.webkit.org/show_bug.cgi?id=61025
+
+ Add a new parameter to StdlibExtras.h::binarySerarch function
+ to also handle cases when the array does not contain the key value.
+ This is needed for an svg function.
+
+ * wtf/StdLibExtras.h:
+ (WTF::binarySearch):
+
2011-06-29 Gavin Barraclough <[email protected]>
Reviewed by Geoff Garen.
Modified: trunk/Source/_javascript_Core/wtf/StdLibExtras.h (90101 => 90102)
--- trunk/Source/_javascript_Core/wtf/StdLibExtras.h 2011-06-30 10:40:32 UTC (rev 90101)
+++ trunk/Source/_javascript_Core/wtf/StdLibExtras.h 2011-06-30 10:56:49 UTC (rev 90102)
@@ -123,19 +123,23 @@
return (x + remainderMask) & ~remainderMask;
}
+enum BinarySearchMode {
+ KeyMustBePresentInArray,
+ KeyMustNotBePresentInArray
+};
+
// Binary search algorithm, calls extractKey on pre-sorted elements in array,
// compares result with key (KeyTypes should be comparable with '--', '<', '>').
-// Optimized for cases where the array contains the key, checked by assertions.
template<typename ArrayType, typename KeyType, KeyType(*extractKey)(ArrayType*)>
-inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key)
+inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray)
{
- // The array must contain at least one element (pre-condition, array does conatin key).
- // If the array only contains one element, no need to do the comparison.
+ // The array must contain at least one element (pre-condition, array does contain key).
+ // If the array contains only one element, no need to do the comparison.
while (size > 1) {
// Pick an element to check, half way through the array, and read the value.
int pos = (size - 1) >> 1;
KeyType val = extractKey(&array[pos]);
-
+
// If the key matches, success!
if (val == key)
return &array[pos];
@@ -149,13 +153,18 @@
array += (pos + 1);
}
- // 'size' should never reach zero.
- ASSERT(size);
+ // In case of BinarySearchMode = KeyMustBePresentInArray 'size' should never reach zero.
+ if (mode == KeyMustBePresentInArray)
+ ASSERT(size);
}
-
- // If we reach this point we've chopped down to one element, no need to check it matches
- ASSERT(size == 1);
- ASSERT(key == extractKey(&array[0]));
+
+ // In case of BinarySearchMode = KeyMustBePresentInArray if we reach this point
+ // we've chopped down to one element, no need to check it matches
+ if (mode == KeyMustBePresentInArray) {
+ ASSERT(size == 1);
+ ASSERT(key == extractKey(&array[0]));
+ }
+
return &array[0];
}
Modified: trunk/Source/WebCore/ChangeLog (90101 => 90102)
--- trunk/Source/WebCore/ChangeLog 2011-06-30 10:40:32 UTC (rev 90101)
+++ trunk/Source/WebCore/ChangeLog 2011-06-30 10:56:49 UTC (rev 90102)
@@ -1,3 +1,19 @@
+2011-06-30 Oliver Varga <[email protected]>
+
+ Reviewed by Nikolas Zimmermann.
+
+ Speed up SVGSMILElement::findInstanceTime.
+ https://bugs.webkit.org/show_bug.cgi?id=61025
+
+ Replace the linear search to binary search on ordered list because
+ the previous searches from the beginning was not efficient.
+
+ No new tests this is only a performance tweak.
+
+ * svg/animation/SVGSMILElement.cpp:
+ (WebCore::extractTimeFromVector):
+ (WebCore::SVGSMILElement::findInstanceTime):
+
2011-06-30 Kentaro Hara <[email protected]>
Reviewed by Kent Tamura.
Modified: trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp (90101 => 90102)
--- trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp 2011-06-30 10:40:32 UTC (rev 90101)
+++ trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp 2011-06-30 10:56:49 UTC (rev 90102)
@@ -616,25 +616,52 @@
endListChanged(eventTime);
}
+inline SMILTime extractTimeFromVector(const SMILTime* position)
+{
+ return *position;
+}
+
SMILTime SVGSMILElement::findInstanceTime(BeginOrEnd beginOrEnd, SMILTime minimumTime, bool equalsMinimumOK) const
{
- // FIXME: This searches from the beginning which is inefficient. The list is usually not long
- // (one entry in common cases) but you can construct a case where it does grow.
const Vector<SMILTime>& list = beginOrEnd == Begin ? m_beginTimes : m_endTimes;
- for (unsigned n = 0; n < list.size(); ++n) {
- SMILTime time = list[n];
- ASSERT(!time.isUnresolved());
- if (time.isIndefinite() && beginOrEnd == Begin) {
- // "The special value "indefinite" does not yield an instance time in the begin list."
- continue;
- }
- if (equalsMinimumOK) {
- if (time >= minimumTime)
- return time;
- } else if (time > minimumTime)
- return time;
+ int sizeOfList = list.size();
+
+ if (!sizeOfList)
+ return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
+
+ const SMILTime* result = binarySearch<const SMILTime, SMILTime, extractTimeFromVector>(list.begin(), sizeOfList, minimumTime, WTF::KeyMustNotBePresentInArray);
+ int indexOfResult = result - list.begin();
+
+ if (sizeOfList - 1 > indexOfResult && list[indexOfResult] < minimumTime)
+ ++indexOfResult;
+
+ ASSERT(indexOfResult < sizeOfList);
+
+ // "The special value "indefinite" does not yield an instance time in the begin list."
+ if (list[indexOfResult].isIndefinite() && beginOrEnd == Begin)
+ return SMILTime::unresolved();
+
+ if (list[indexOfResult] < minimumTime)
+ return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
+
+ // If the equals is NOT accepted, we have to find a bigger one.
+ if (list[indexOfResult] == minimumTime && !equalsMinimumOK) {
+ if (indexOfResult + 1 >= sizeOfList)
+ return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
}
- return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
+
+ while (list[indexOfResult] == list[indexOfResult + 1] && indexOfResult < sizeOfList - 1)
+ ++indexOfResult;
+
+ if (list[indexOfResult] > minimumTime)
+ return list[indexOfResult];
+ if (list[indexOfResult] == minimumTime) {
+ if (indexOfResult + 1 < sizeOfList - 1)
+ return list[indexOfResult + 1];
+ return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
+ }
+
+ return list[indexOfResult];
}
SMILTime SVGSMILElement::repeatingDuration() const
