Changeset 90811 in webkit


Ignore:
Timestamp:
Jul 12, 2011 3:14:30 AM (13 years ago)
Author:
reni@webkit.org
Message:

Patch by Oliver Varga <Varga.Oliver@stud.u-szeged.hu> on 2011-07-12
Reviewed by Nikolas Zimmermann.

Speed up SVGSMILElement::findInstanceTime.
https://bugs.webkit.org/show_bug.cgi?id=61025

Source/JavaScriptCore:

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

Source/WebCore:

Replace the linear search to binary search on ordered list because
the previous searches from the beginning was not efficient.
Out of index error fixed by Renata Hodovan.

No new tests this is only a performance tweak.

  • svg/animation/SVGSMILElement.cpp:

(WebCore::extractTimeFromVector):
(WebCore::SVGSMILElement::findInstanceTime):

Location:
trunk/Source
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/JavaScriptCore/ChangeLog

    r90799 r90811  
     12011-07-12  Oliver Varga  <Varga.Oliver@stud.u-szeged.hu>
     2
     3        Reviewed by Nikolas Zimmermann.
     4
     5        Speed up SVGSMILElement::findInstanceTime.
     6        https://bugs.webkit.org/show_bug.cgi?id=61025
     7
     8        Add a new parameter to StdlibExtras.h::binarySerarch function
     9        to also handle cases when the array does not contain the key value.
     10        This is needed for an svg function.
     11
     12        * wtf/StdLibExtras.h:
     13        (WTF::binarySearch):
     14
    1152011-07-11  Filip Pizlo  <fpizlo@apple.com>
    216
  • trunk/Source/JavaScriptCore/wtf/StdLibExtras.h

    r90117 r90811  
    124124}
    125125
     126enum BinarySearchMode {
     127    KeyMustBePresentInArray,
     128    KeyMustNotBePresentInArray
     129};
     130
    126131// Binary search algorithm, calls extractKey on pre-sorted elements in array,
    127132// compares result with key (KeyTypes should be comparable with '--', '<', '>').
    128 // Optimized for cases where the array contains the key, checked by assertions.
    129133template<typename ArrayType, typename KeyType, KeyType(*extractKey)(ArrayType*)>
    130 inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key)
     134inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray)
    131135{
    132     // The array must contain at least one element (pre-condition, array does conatin key).
    133     // If the array only contains one element, no need to do the comparison.
     136    // The array must contain at least one element (pre-condition, array does contain key).
     137    // If the array contains only one element, no need to do the comparison.
    134138    while (size > 1) {
    135139        // Pick an element to check, half way through the array, and read the value.
    136140        int pos = (size - 1) >> 1;
    137141        KeyType val = extractKey(&array[pos]);
    138        
     142
    139143        // If the key matches, success!
    140144        if (val == key)
     
    150154        }
    151155
    152         // 'size' should never reach zero.
    153         ASSERT(size);
     156        // In case of BinarySearchMode = KeyMustBePresentInArray 'size' should never reach zero.
     157        if (mode == KeyMustBePresentInArray)
     158            ASSERT(size);
    154159    }
    155    
    156     // If we reach this point we've chopped down to one element, no need to check it matches
    157     ASSERT(size == 1);
    158     ASSERT(key == extractKey(&array[0]));
     160
     161    // In case of BinarySearchMode = KeyMustBePresentInArray if we reach this point
     162    // we've chopped down to one element, no need to check it matches
     163    if (mode == KeyMustBePresentInArray) {
     164        ASSERT(size == 1);
     165        ASSERT(key == extractKey(&array[0]));
     166    }
     167
    159168    return &array[0];
    160169}
  • trunk/Source/WebCore/ChangeLog

    r90809 r90811  
     12011-07-12  Oliver Varga  <Varga.Oliver@stud.u-szeged.hu>
     2
     3        Reviewed by Nikolas Zimmermann.
     4
     5        Speed up SVGSMILElement::findInstanceTime.
     6        https://bugs.webkit.org/show_bug.cgi?id=61025
     7
     8        Replace the linear search to binary search on ordered list because
     9        the previous searches from the beginning was not efficient.
     10        Out of index error fixed by Renata Hodovan.
     11
     12        No new tests this is only a performance tweak.
     13
     14        * svg/animation/SVGSMILElement.cpp:
     15        (WebCore::extractTimeFromVector):
     16        (WebCore::SVGSMILElement::findInstanceTime):
     17
    1182011-07-11  Zeng Huiqing  <huiqing.zeng@intel.com>
    219
  • trunk/Source/WebCore/svg/animation/SVGSMILElement.cpp

    r90117 r90811  
    617617}
    618618   
     619inline SMILTime extractTimeFromVector(const SMILTime* position)
     620{
     621    return *position;
     622}
     623
    619624SMILTime SVGSMILElement::findInstanceTime(BeginOrEnd beginOrEnd, SMILTime minimumTime, bool equalsMinimumOK) const
    620625{
    621     // FIXME: This searches from the beginning which is inefficient. The list is usually not long
    622     // (one entry in common cases) but you can construct a case where it does grow.
    623626    const Vector<SMILTime>& list = beginOrEnd == Begin ? m_beginTimes : m_endTimes;
    624     for (unsigned n = 0; n < list.size(); ++n) {
    625         SMILTime time = list[n];
    626         ASSERT(!time.isUnresolved());
    627         if (time.isIndefinite() && beginOrEnd == Begin) {
    628             // "The special value "indefinite" does not yield an instance time in the begin list."
    629             continue;
    630         }
    631         if (equalsMinimumOK) {
    632             if (time >= minimumTime)
    633                 return time;
    634         } else if (time > minimumTime)
    635             return time;
    636     }
    637     return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
     627    int sizeOfList = list.size();
     628
     629    if (!sizeOfList)
     630        return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
     631
     632    const SMILTime* result = binarySearch<const SMILTime, SMILTime, extractTimeFromVector>(list.begin(), sizeOfList, minimumTime, WTF::KeyMustNotBePresentInArray);
     633    int indexOfResult = result - list.begin();
     634
     635    if (sizeOfList - 1 > indexOfResult && list[indexOfResult] < minimumTime)
     636        ++indexOfResult;
     637
     638    ASSERT(indexOfResult < sizeOfList);
     639
     640    // "The special value "indefinite" does not yield an instance time in the begin list."
     641    if (list[indexOfResult].isIndefinite() && beginOrEnd == Begin)
     642        return SMILTime::unresolved();
     643
     644    if (list[indexOfResult] < minimumTime)
     645        return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
     646
     647    // If the equals is NOT accepted, we have to find a bigger one.
     648    if (list[indexOfResult] == minimumTime && !equalsMinimumOK) {
     649        if (indexOfResult + 1 >= sizeOfList)
     650            return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
     651    }
     652
     653    if (sizeOfList > 1) {
     654        while (list[indexOfResult] == list[indexOfResult + 1] && indexOfResult < sizeOfList - 1)
     655            ++indexOfResult;
     656    }
     657
     658    if (list[indexOfResult] > minimumTime)
     659        return list[indexOfResult];
     660    if (list[indexOfResult] == minimumTime) {
     661        if (indexOfResult + 1 < sizeOfList - 1)
     662            return list[indexOfResult + 1];
     663        return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
     664    }
     665
     666    return list[indexOfResult];
    638667}
    639668
Note: See TracChangeset for help on using the changeset viewer.