Bug 61025 – Speed up SVGSMILElement::findInstanceTime

• Status: RESOLVED
• Resolution: FIXED
• Component: SVG

[Oliver Varga]

In SVGSMILElement::findInstanceTime function:
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.

[Oliver Varga]

Created attachment 97430 [details]
Speed up SVGSMILElement::findInstanceTime

Speed up SVGSMILElement::findInstanceTime because the previous searches from the beginning was not efficient.
Replace the linear search to binary search on ordered list.

[Nikolas Zimmermann]

Comment on attachment 97430 [details]
Speed up SVGSMILElement::findInstanceTime

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?

[Oliver Varga]

Created attachment 98707 [details]
Speed up SVGSMILElement::findInstanceTime

[WebKit Review Bot]

Comment on attachment 98707 [details]
Speed up SVGSMILElement::findInstanceTime

Attachment 98707 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/8946304

[Collabora GTK+ EWS bot]

Comment on attachment 98707 [details]
Speed up SVGSMILElement::findInstanceTime

Attachment 98707 [details] did not pass gtk-ews (gtk):
Output: http://queues.webkit.org/results/8944342

[Nikolas Zimmermann]

Comment on attachment 98707 [details]
Speed up SVGSMILElement::findInstanceTime

View in context: https://bugs.webkit.org/attachment.cgi?id=98707&action=review

Almost there, still some tweaks to do, but much better than the last one!

> Source/JavaScriptCore/wtf/StdLibExtras.h:128
>  // Optimized for cases where the array contains the key, checked by assertions.

This comment is not true anymore.

> Source/JavaScriptCore/wtf/StdLibExtras.h:130
> +inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key, bool isElementContains)

Please add sth like:
enum BinarySearchMode {
    KeyMustBePresentInArray,
    KeyMustNotBePresentInArray
};
and switch from bool isElementContains, to "BinarySearchMode mode = KeyMustBePresentInArray".
This way you don't need to touch any other place that used binarySearch before, and it's cleaner than a boolean param.

> Source/JavaScriptCore/wtf/StdLibExtras.h:133
>  {
>      // 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.

This can be rephrased as well, and you can fix the existing conatin typo.

> Source/JavaScriptCore/wtf/StdLibExtras.h:152
>          // 'size' should never reach zero.

Comment is also not true anymore for isElementContains=false.

> Source/JavaScriptCore/wtf/StdLibExtras.h:157
>      // If we reach this point we've chopped down to one element, no need to check it matches

Ditto.

> Source/JavaScriptCore/wtf/StdLibExtras.h:162
> +    if (isElementContains)
> +        ASSERT(size == 1);
> +
> +    if (isElementContains)
> +        ASSERT(key == extractKey(&array[0]));

You can combine these if branches into one.

> Source/WebCore/ChangeLog:11
> +        No new tests this is only a  performance tweak.

one space too much.

> Source/WebCore/svg/animation/SVGSMILElement.cpp:620
> +{

Style, must be "* position".

> Source/WebCore/svg/animation/SVGSMILElement.cpp:633
> +    int indexOfResult = (((unsigned)result) - ((unsigned)list.begin())) / sizeof(SMILTime);

C-style casts shouldn't be used. Why do you need these casts? The type is also wrong, if you cast then to ptrdiff_t, but I think it's unncessary.

> Source/WebCore/svg/animation/SVGSMILElement.cpp:636
> +        indexOfResult++;

Use postfix ++indexResult.

> Source/WebCore/svg/animation/SVGSMILElement.cpp:638
> +    if (list[indexOfResult].isIndefinite() && beginOrEnd == Begin)

You should add an assert before this line: ASSERT(indexOfResult < sizeOfList).

> Source/WebCore/svg/animation/SVGSMILElement.cpp:639
> +        // "The special value "indefinite" does not yield an instance time in the begin list."

You can move the comment before the if condition, as its our common style.

> Source/WebCore/svg/animation/SVGSMILElement.cpp:652
> +        indexOfResult++;

Use postfix ++indexResult.

> Source/WebCore/svg/animation/SVGSMILElement.cpp:659
> +        if (indexOfResult + 1 < sizeOfList - 1) {
> +            return list[indexOfResult + 1];
>          }

Braces are not needed.

[Oliver Varga]

Created attachment 98887 [details]
Speed up SVGSMILElement::findInstanceTime

[Nikolas Zimmermann]

Comment on attachment 98887 [details]
Speed up SVGSMILElement::findInstanceTime

View in context: https://bugs.webkit.org/attachment.cgi?id=98887&action=review

Almost r+, but the ChangeLog is wrong :(

> Source/JavaScriptCore/ChangeLog:8
> +        Added a new parameter to StdlibExtras.h::binarySerarch function,
> +        for the case when not sure that the array contains the key value.
> +        It is needed for an svg function.
> +        https://bugs.webkit.org/show_bug.cgi?id=61025

ChangeLog still is wrong, please fix it first.

[Oliver Varga]

Created attachment 98900 [details]
Speed up SVGSMILElement::findInstanceTime

[Nikolas Zimmermann]

Comment on attachment 98900 [details]
Speed up SVGSMILElement::findInstanceTime

View in context: https://bugs.webkit.org/attachment.cgi?id=98900&action=review

> Source/JavaScriptCore/ChangeLog:8
> +        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.
> +        https://bugs.webkit.org/show_bug.cgi?id=61025

This is the part which is wrong. The WebKit ChangeLog style is:

Reviewed by NOBODY (OOPS!).

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

Your text goes here.

> Source/WebCore/ChangeLog:11
> +
> +        Replace the linear search to binary search on ordered list.
> +        https://bugs.webkit.org/show_bug.cgi?id=61025
> +
> +        Speed up SVGSMILElement::findInstanceTime because
> +        the previous searches from the beginning was not efficient.
> +
> +        No new tests this is only a performance tweak.

This has the correct ChangeLog style bug the wrong bug title
the title is "Speed up SVGSMILElement::findInstanceTime" not "Replace the linear search to binary search.." -- that should go into the description text.

[Dirk Schulze]

Please use:

Tools/Scripts/prepare-ChangeLog --bug <bug number> --email=<your email address>

This will create the ChangeLog for you. You just have to fill the description.

[Oliver Varga]

Created attachment 99241 [details]
Speed up SVGSMILElement::findInstanceTime

[Nikolas Zimmermann]

Comment on attachment 99241 [details]
Speed up SVGSMILElement::findInstanceTime

Good job, r=me!

[WebKit Review Bot]

Comment on attachment 99241 [details]
Speed up SVGSMILElement::findInstanceTime

Clearing flags on attachment: 99241

Committed r90102: <http://trac.webkit.org/changeset/90102>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Adam Roben (:aroben)]

This caused lots of assertion failures, so I rolled it out. (See bug 63714 and duplicates.)

[Renata Hodovan]

Created attachment 100452 [details]
Fix for the out of index error

while (list[indexOfResult] == list[indexOfResult + 1] && indexOfResult < sizeOfList - 1)
This loop supposes that our list has at least two elements, so we have to check it.

[Nikolas Zimmermann]

Comment on attachment 100452 [details]
Fix for the out of index error

Looks good, let's retry.

[Renata Hodovan]

Committed r90811: <http://trac.webkit.org/changeset/90811>

[Adam Roben (:aroben)]

This is still causing assertion failures:

http://build.webkit.org/results/SnowLeopard%20Intel%20Leaks/r90811%20(18017)/results.html
http://build.webkit.org/results/Windows%20XP%20Debug%20(Tests)/r90811%20(30579)/results.html

[Adam Roben (:aroben)]

Reverted r90811 for reason:

Several svg tests failing assertions beneath SVGSMILElement::findInstanceTime

Committed r90812: <http://trac.webkit.org/changeset/90812>

[Dirk Schulze]

(In reply to comment #21)
> Reverted r90811 for reason:
> 
> Several svg tests failing assertions beneath SVGSMILElement::findInstanceTime
> 
> Committed r90812: <http://trac.webkit.org/changeset/90812>

Does it just affect Mac or why isn't it recognized before uploading the patch to the bug report?

[Adam Roben (:aroben)]

(In reply to comment #22)
> Does it just affect Mac

No. Note that I linked to <http://build.webkit.org/results/Windows%20XP%20Debug%20(Tests)/r90811%20(30579)/results.html> as well, which is from the Windows XP Debug (Tests) bot (as the URL says).

> or why isn't it recognized before uploading the patch to the bug report?

The Mac and Windows EWS bots don't run tests.

[Dirk Schulze]

(In reply to comment #23)
> (In reply to comment #22)
> > Does it just affect Mac
> 
> No. Note that I linked to <http://build.webkit.org/results/Windows%20XP%20Debug%20(Tests)/r90811%20(30579)/results.html> as well, which is from the Windows XP Debug (Tests) bot (as the URL says).
> 
> > or why isn't it recognized before uploading the patch to the bug report?
> 
> The Mac and Windows EWS bots don't run tests.

Ok, but the normal process should be creating a debug build and test changes locally. Even more when the patch got rolled out before. Thats why I wondered if it was just recognizable on Mac. But when you say that it happens on Win, it should happen on Qt as well.

[Renata Hodovan]

Created attachment 100792 [details]
Fix for the out of index error

The reason of the previous assertions is the converse order of the conditions.

if (list[indexOfResult] < minimumTime && sizeOfList - 1 > indexOfResult)

Here the first part was evaluated first even if the second part wasn't true (which is responsible for the right indexing). So what we should simple do is just change them.

[Renata Hodovan]

Any comment would be welcomed. :) The red style bot isn't related to this patch. I guess was an internal error of ews, but I can resend the patch if it's needed.

[Oliver Varga]

The modified patch was tested on ubuntu-lucid-x86 environment, and it did not cause any regression.

[Oliver Varga]

...on chromium platform.

[Nikolas Zimmermann]

Comment on attachment 100792 [details]
Fix for the out of index error

r=me again :-)

[Renata Hodovan]

Committed r93039: <http://trac.webkit.org/changeset/93039>