Bug 61025 - Speed up SVGSMILElement::findInstanceTime
: Speed up SVGSMILElement::findInstanceTime
Status: RESOLVED FIXED
Product: WebKit
Classification: Unclassified
Component: SVG
: 528+ (Nightly build)
: All All
: P2 Normal
Assigned To: Renata Hodovan
:
Depends on: 63714 63719
Blocks:
  Show dependency treegraph
 
Reported: 2011-05-18 00:23 PDT by Oliver Varga
Modified: 2011-08-16 12:38 PDT (History)
11 users (show)

See Also:


Attachments
Speed up SVGSMILElement::findInstanceTime (4.15 KB, patch)
2011-06-16 03:18 PDT, Oliver Varga
zimmermann: review-
Details | Formatted Diff | Diff
Speed up SVGSMILElement::findInstanceTime (9.04 KB, patch)
2011-06-27 05:37 PDT, Oliver Varga
zimmermann: review-
webkit.review.bot: commit‑queue-
Details | Formatted Diff | Diff
Speed up SVGSMILElement::findInstanceTime (7.51 KB, patch)
2011-06-28 02:30 PDT, Oliver Varga
zimmermann: review-
Details | Formatted Diff | Diff
Speed up SVGSMILElement::findInstanceTime (7.51 KB, patch)
2011-06-28 04:45 PDT, Oliver Varga
zimmermann: review-
zimmermann: commit‑queue-
Details | Formatted Diff | Diff
Speed up SVGSMILElement::findInstanceTime (7.56 KB, patch)
2011-06-29 23:18 PDT, Oliver Varga
no flags Details | Formatted Diff | Diff
Fix for the out of index error (7.67 KB, patch)
2011-07-12 02:13 PDT, Renata Hodovan
zimmermann: review+
Details | Formatted Diff | Diff
Fix for the out of index error (7.63 KB, patch)
2011-07-14 02:37 PDT, Renata Hodovan
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Oliver Varga 2011-05-18 00:23:00 PDT
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.
Comment 1 Oliver Varga 2011-06-16 03:18:18 PDT
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.
Comment 2 Nikolas Zimmermann 2011-06-16 03:48:59 PDT
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?
Comment 3 Oliver Varga 2011-06-27 05:37:35 PDT
Created attachment 98707 [details]
Speed up SVGSMILElement::findInstanceTime
Comment 4 WebKit Review Bot 2011-06-27 06:10:25 PDT
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
Comment 5 Collabora GTK+ EWS bot 2011-06-27 06:59:19 PDT
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
Comment 6 Nikolas Zimmermann 2011-06-27 08:33:54 PDT
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.
Comment 7 Oliver Varga 2011-06-28 02:30:58 PDT
Created attachment 98887 [details]
Speed up SVGSMILElement::findInstanceTime
Comment 8 Nikolas Zimmermann 2011-06-28 04:24:41 PDT
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.
Comment 9 Oliver Varga 2011-06-28 04:45:37 PDT
Created attachment 98900 [details]
Speed up SVGSMILElement::findInstanceTime
Comment 10 Nikolas Zimmermann 2011-06-28 05:21:12 PDT
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.
Comment 11 Dirk Schulze 2011-06-28 05:23:42 PDT
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.
Comment 12 Oliver Varga 2011-06-29 23:18:48 PDT
Created attachment 99241 [details]
Speed up SVGSMILElement::findInstanceTime
Comment 13 Nikolas Zimmermann 2011-06-30 03:15:30 PDT
Comment on attachment 99241 [details]
Speed up SVGSMILElement::findInstanceTime

Good job, r=me!
Comment 14 WebKit Review Bot 2011-06-30 03:57:01 PDT
Comment on attachment 99241 [details]
Speed up SVGSMILElement::findInstanceTime

Clearing flags on attachment: 99241

Committed r90102: <http://trac.webkit.org/changeset/90102>
Comment 15 WebKit Review Bot 2011-06-30 03:57:07 PDT
All reviewed patches have been landed.  Closing bug.
Comment 16 Adam Roben (:aroben) 2011-06-30 07:09:09 PDT
This caused lots of assertion failures, so I rolled it out. (See bug 63714 and duplicates.)
Comment 17 Renata Hodovan 2011-07-12 02:13:05 PDT
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.
Comment 18 Nikolas Zimmermann 2011-07-12 02:35:35 PDT
Comment on attachment 100452 [details]
Fix for the out of index error

Looks good, let's retry.
Comment 19 Renata Hodovan 2011-07-12 03:14:51 PDT
Committed r90811: <http://trac.webkit.org/changeset/90811>
Comment 21 Adam Roben (:aroben) 2011-07-12 05:40:10 PDT
Reverted r90811 for reason:

Several svg tests failing assertions beneath SVGSMILElement::findInstanceTime

Committed r90812: <http://trac.webkit.org/changeset/90812>
Comment 22 Dirk Schulze 2011-07-12 08:32:33 PDT
(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?
Comment 23 Adam Roben (:aroben) 2011-07-12 08:43:13 PDT
(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.
Comment 24 Dirk Schulze 2011-07-12 08:47:26 PDT
(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.
Comment 25 Renata Hodovan 2011-07-14 02:37:55 PDT
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.
Comment 26 Renata Hodovan 2011-08-09 09:05:46 PDT
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.
Comment 27 Oliver Varga 2011-08-10 05:42:26 PDT
The modified patch was tested on ubuntu-lucid-x86 environment, and it did not cause any regression.
Comment 28 Oliver Varga 2011-08-10 13:28:34 PDT
...on chromium platform.
Comment 29 Nikolas Zimmermann 2011-08-12 01:45:50 PDT
Comment on attachment 100792 [details]
Fix for the out of index error

r=me again :-)
Comment 30 Renata Hodovan 2011-08-15 04:59:39 PDT
Committed r93039: <http://trac.webkit.org/changeset/93039>