Bug 61025 - Speed up SVGSMILElement::findInstanceTime
: Speed up SVGSMILElement::findInstanceTime
Status: RESOLVED FIXED
: WebKit
SVG
: 528+ (Nightly build)
: All All
: P2 Normal
Assigned To:
:
:
: 63714 63719
:
  Show dependency treegraph
 
Reported: 2011-05-18 00:23 PST by
Modified: 2011-08-16 12:38 PST (History)


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


Note

You need to log in before you can comment on or make changes to this bug.


Description From 2011-05-18 00:23:00 PST
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 From 2011-06-16 03:18:18 PST -------
Created an attachment (id=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 From 2011-06-16 03:48:59 PST -------
(From update of attachment 97430 [details])
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 From 2011-06-27 05:37:35 PST -------
Created an attachment (id=98707) [details]
Speed up SVGSMILElement::findInstanceTime
------- Comment #4 From 2011-06-27 06:10:25 PST -------
(From update of attachment 98707 [details])
Attachment 98707 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/8946304
------- Comment #5 From 2011-06-27 06:59:19 PST -------
(From update of attachment 98707 [details])
Attachment 98707 [details] did not pass gtk-ews (gtk):
Output: http://queues.webkit.org/results/8944342
------- Comment #6 From 2011-06-27 08:33:54 PST -------
(From update of attachment 98707 [details])
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 From 2011-06-28 02:30:58 PST -------
Created an attachment (id=98887) [details]
Speed up SVGSMILElement::findInstanceTime
------- Comment #8 From 2011-06-28 04:24:41 PST -------
(From update of attachment 98887 [details])
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 From 2011-06-28 04:45:37 PST -------
Created an attachment (id=98900) [details]
Speed up SVGSMILElement::findInstanceTime
------- Comment #10 From 2011-06-28 05:21:12 PST -------
(From update of attachment 98900 [details])
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 From 2011-06-28 05:23:42 PST -------
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 From 2011-06-29 23:18:48 PST -------
Created an attachment (id=99241) [details]
Speed up SVGSMILElement::findInstanceTime
------- Comment #13 From 2011-06-30 03:15:30 PST -------
(From update of attachment 99241 [details])
Good job, r=me!
------- Comment #14 From 2011-06-30 03:57:01 PST -------
(From update of attachment 99241 [details])
Clearing flags on attachment: 99241

Committed r90102: <http://trac.webkit.org/changeset/90102>
------- Comment #15 From 2011-06-30 03:57:07 PST -------
All reviewed patches have been landed.  Closing bug.
------- Comment #16 From 2011-06-30 07:09:09 PST -------
This caused lots of assertion failures, so I rolled it out. (See bug 63714 and duplicates.)
------- Comment #17 From 2011-07-12 02:13:05 PST -------
Created an attachment (id=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 From 2011-07-12 02:35:35 PST -------
(From update of attachment 100452 [details])
Looks good, let's retry.
------- Comment #19 From 2011-07-12 03:14:51 PST -------
Committed r90811: <http://trac.webkit.org/changeset/90811>
------- Comment #21 From 2011-07-12 05:40:10 PST -------
Reverted r90811 for reason:

Several svg tests failing assertions beneath SVGSMILElement::findInstanceTime

Committed r90812: <http://trac.webkit.org/changeset/90812>
------- Comment #22 From 2011-07-12 08:32:33 PST -------
(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 From 2011-07-12 08:43:13 PST -------
(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 From 2011-07-12 08:47:26 PST -------
(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 From 2011-07-14 02:37:55 PST -------
Created an attachment (id=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 From 2011-08-09 09:05:46 PST -------
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 From 2011-08-10 05:42:26 PST -------
The modified patch was tested on ubuntu-lucid-x86 environment, and it did not cause any regression.
------- Comment #28 From 2011-08-10 13:28:34 PST -------
...on chromium platform.
------- Comment #29 From 2011-08-12 01:45:50 PST -------
(From update of attachment 100792 [details])
r=me again :-)
------- Comment #30 From 2011-08-15 04:59:39 PST -------
Committed r93039: <http://trac.webkit.org/changeset/93039>