[webkit-reviews] review denied: [Bug 61025] Speed up SVGSMILElement::findInstanceTime : [Attachment 97430] Speed up SVGSMILElement::findInstanceTime

[bugzilla-daemon at webkit.org]

Nikolas Zimmermann <zimmermann at kde.org> has denied Oliver Varga
<Varga.Oliver at stud.u-szeged.hu>'s request for review:
Bug 61025: Speed up SVGSMILElement::findInstanceTime
https://bugs.webkit.org/show_bug.cgi?id=61025

Attachment 97430: Speed up SVGSMILElement::findInstanceTime
https://bugs.webkit.org/attachment.cgi?id=97430&action=review

------- Additional Comments from Nikolas Zimmermann <zimmermann at kde.org>
View in context: https://bugs.webkit.org/attachment.cgi?id=97430&action=review

Nice that you're tackling this, some comments that lead to r-:

> Source/WebCore/ChangeLog:10
> +	   Speed up SVGSMILElement::findInstanceTime because
> +	   the previous searches from the beginning was not efficient.
> +	   Replace the linear search to binary search on ordered list.
> +	   https://bugs.webkit.org/show_bug.cgi?id=61025
> +
> +	   No new tests. (OOPS!)

This has to be changed like this:
Replace the linear...
http://

Speed up ....

No new tests this is only a  performance tweak.

> Source/WebCore/svg/animation/SVGSMILElement.cpp:628
> +    if (right < 0)
> +	   return (beginOrEnd == Begin) ? SMILTime::unresolved() :
SMILTime::indefinite();

I'd move that upwards:
int sizeOfList = list.size();
if (!sizeOfList)
    return beginOrEnd == Begin ? SMILTime::unresolved() :
SMILTime::indefinite();
..

No braces needed around the condition of the ternary operator.
Also common conclusion seems to omit the const from sizeOfList, we don't do
that in other places, though I see the benefit.

> Source/WebCore/svg/animation/SVGSMILElement.cpp:632
> +	   ASSERT(0 <= center && center < sizeOfList);

Don't use && conditions in assertions, it makes it hard to figure out what
exactly happened without further debugging.
ASSERT(center >= 0);
ASSERT(center < sizeOfList);

> Source/WebCore/svg/animation/SVGSMILElement.cpp:641
> +	   if (time > minimumTime) {
> +	       if (center > 0) {
> +		   right = center - 1;
> +		   center = (left + right) / 2;

Hm, I find it very unfortunate that you have to provide your own binary search
algorithm.
It turns out there's a binarySearch template in wtf/StdLibExtras.h that could
be used for this purpose, when tweaking it a little:


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

The problem here is that this algorithm assumes that the key is always present
in the array. That could be changed.
If that's done, we could simple use:

int sizeOfList = list.size();
if (!sizeOfList)
    return beginOrEnd == Begin ? SMILTime::unresolved() :
SMILTime::indefinite();
SMILTime* result = binarySearch<SMILTime, SMILTime,
extractTimeFromVector>(list.begin(), sizeOfList, minimumTime);
...

What do you think? It might be worth to try to re-use an existing binary search
algorithm, no?