Bug 38025 - Every call to RenderObject::setAnimatableStyle() iterates through all m_compositeAnimations: potentially O(N^2)
Summary: Every call to RenderObject::setAnimatableStyle() iterates through all m_compo...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: All OS X 10.5
: P2 Normal
Assignee: Igor Trindade Oliveira
URL:
Keywords:
Depends on: 80676
Blocks:
  Show dependency treegraph
 
Reported: 2010-04-22 19:56 PDT by Simon Fraser (smfr)
Modified: 2012-05-08 16:34 PDT (History)
5 users (show)

See Also:


Attachments
Patch (3.64 KB, patch)
2012-02-22 18:53 PST, Igor Trindade Oliveira
no flags Details | Formatted Diff | Diff
Test case (1.84 KB, text/html)
2012-03-16 09:46 PDT, Igor Trindade Oliveira
no flags Details
Patch (8.20 KB, patch)
2012-03-19 19:12 PDT, Igor Trindade Oliveira
dino: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Simon Fraser (smfr) 2010-04-22 19:56:40 PDT
RenderObject::setAnimatableStyle() calls animation()->updateAnimations(). This in turn calls m_data->updateAnimationTimer(), which loops through all m_compositeAnimations().

This means that for every RenderObject doing any kind of transition or keyframe animation, we iterate through all other CompositeAnimations in the page. This seems bad.
Comment 1 Igor Trindade Oliveira 2012-02-22 18:53:08 PST
Created attachment 128366 [details]
Patch

Proposed Patch. For the worst case, this patch has the same amount of iterations of the code without the patch.
Comment 2 Simon Fraser (smfr) 2012-02-22 22:46:43 PST
Comment on attachment 128366 [details]
Patch

Did you measure any performance gain?
Comment 3 WebKit Review Bot 2012-02-22 23:36:24 PST
Comment on attachment 128366 [details]
Patch

Clearing flags on attachment: 128366

Committed r108616: <http://trac.webkit.org/changeset/108616>
Comment 4 WebKit Review Bot 2012-02-22 23:36:30 PST
All reviewed patches have been landed.  Closing bug.
Comment 5 Igor Trindade Oliveira 2012-02-23 06:50:20 PST
Yeah, in some cases the patch reduced the number of iterations in 20%.

(In reply to comment #2)
> (From update of attachment 128366 [details])
> Did you measure any performance gain?
Comment 6 Simon Fraser (smfr) 2012-03-08 21:41:55 PST
This broke the animation on http://www.apple.com/safari/welcome/ and was rolled out via bug 80676.
Comment 7 Igor Trindade Oliveira 2012-03-08 22:22:12 PST
Investigating.

(In reply to comment #6)
> This broke the animation on http://www.apple.com/safari/welcome/ and was rolled out via bug 80676.
Comment 8 Igor Trindade Oliveira 2012-03-16 09:46:53 PDT
Created attachment 132302 [details]
Test case

Safari Welcome page reduced test.
Comment 9 Igor Trindade Oliveira 2012-03-19 19:12:17 PDT
Created attachment 132744 [details]
Patch

Patch.
Comment 10 Igor Trindade Oliveira 2012-03-19 19:29:59 PDT
The bug happened because every time that we had an active timer, the patch stopped the timer and called timer.startOneShot, now we are checking if the new timer is bigger than the active timer, if not, we stop the active timer and started a new one shot timer.

(In reply to comment #6)
> This broke the animation on http://www.apple.com/safari/welcome/ and was rolled out via bug 80676.
Comment 11 Dean Jackson 2012-03-20 12:32:34 PDT
Comment on attachment 132744 [details]
Patch

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

> LayoutTests/animations/animation-welcome-safari.html:124
> +        document.body.className = "go"

semicolon missing

> Source/WebCore/ChangeLog:7
> +        This patchs implements updateAnimationTimerForRenderer, it just checks the timeToNextService for
> +        the current RenderObject reducing the amount of iterations.

Typo "patchs". I also suggest:

Implement updateAnimationTimerForRender. This reduces unnecessary animation steps on the current RenderObject by checking the value of timeToNextService before starting a new timer.
Comment 12 Igor Trindade Oliveira 2012-03-22 08:53:40 PDT
committed r111639: http://trac.webkit.org/changeset/111639
Comment 13 Simon Fraser (smfr) 2012-05-08 16:34:50 PDT
This caused bug 85929.