Changeset 90102 in webkit

Timestamp:

Jun 30, 2011 3:56:49 AM (13 years ago)

Author:

commit-queue@webkit.org

Message:

2011-06-30 Oliver Varga <​Varga.Oliver@stud.u-szeged.hu>

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-30 Oliver Varga <​Varga.Oliver@stud.u-szeged.hu>

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):

Location:

trunk/Source

Files:

• JavaScriptCore/ChangeLog (modified) (1 diff)
• JavaScriptCore/wtf/StdLibExtras.h (modified) (2 diffs)
• WebCore/ChangeLog (modified) (1 diff)
• WebCore/svg/animation/SVGSMILElement.cpp (modified) (1 diff)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2011-06-30  Oliver Varga  <Varga.Oliver@stud.u-szeged.hu>
+
+        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  <barraclough@apple.com>
 

trunk/Source/JavaScriptCore/wtf/StdLibExtras.h

@@ -124 +124 @@
 }
 
+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)
@@ -150 +154 @@
         }
 
-        // '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];
 }

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2011-06-30  Oliver Varga  <Varga.Oliver@stud.u-szeged.hu>
+
+        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  <haraken@google.com>
 

trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp

@@ -617 +617 @@
 }
     
+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;
-    }
-    return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
+    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();
+    }
+
+    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];
 }