Thinking in Animation Frames: Tuning Blink for 60 Hz

[Adam Barth]

One of our primary goals for Blink in 2014 is to improve touch-driven interactions by making the engine run smoothly at 60 Hz [1].  This document explains an approach a number of us are pursuing to make that a reality.

At a high level, our approach is to retool the rendering engine to work in terms of animation frames.  During each frame, the engine will compute style, layout, and compositing information exactly once.  Additionally, we will minimize the information recomputed in each phase by minimizing the amount of information that is invalidated from the previous frame.

== Background (Slightly Apocryphal)  ==

In a land before time, when dinosaurs roamed the earth, Blink (then called WebKit) rendered into a single backing store.  When a script mutated the DOM, we recomputed style and layout information, and then invalidated portions of the backing store.  After coalescing these invalidations, we repainted the invalidated regions and sent the backing store's bitmap to the browser process for display.

In this classical approach, Blink controls the timing of the rendering process.  When script mutates the DOM, we want to display the results of the mutation as soon as possible, but there's no external notion of "soon."  We recalculated style and layout information asynchronously, which means that "soon" was controlled by the style and layout timers, respectively.

At some point, we switched Blink's rendering model from this classical approach to using accelerated compositing.  Instead of rendering into a single backing store, we now rendering to a tree backing stores, each called a GraphicsLayer.  Instead of being blitted to the screen, the GraphicsLayers are composited on the GPU by cc, the Chromium Compositor.  To update the GraphicsLayer tree, Blink can commit new data to compositor, which will appear on screen in the next vsync after cc activates the tree.

In this more modern view, the compositor controls the timing of the rendering process.  The compositor watches the display's vsync signal and puts up a new composition of the GraphicsLayers for each vsync.  Blink is throttled to producing commits only as quickly as the compositor can consume them, which maxes out at the frequency of vsync, typically 60 Hz.

== Running at 60 Hz ==

In the classical approach, Blink might recalculate style and layout information multiple times per commit, which is wasteful.  For example, if a script mutates the DOM, calls requestAnimationFrame, and then mutates the DOM again inside the requestAnimationFrame callback, it's possible that the recalc style timer will fire in between the two DOM mutations, which means we'll recalc style twice (once when the style timer fires and again to generate the tree of GraphicsLayers to commit to the compositor).  That both wastes power and can introduce jank because recalculating style twice might cause us to miss the deadline for the current frame.

Instead, we should update Blink's rendering engine to account for the modern approach to composited graphics.  Specifically, instead of using timers to generate internal notions of time, we should request animation frames from the compositor, and use that time signal to throttle our recalculation of style and layout information.  This approach will help us recalculate style and layout information exactly once per frame.

We've already switched the style system from being driven off a timer to being driven off animation frames [2].  I'm working on switch the layout system over to using animation frames as well [3].

== A State Machine ==

Although we often refer to Blink as a rendering engine, we haven't been explicit about the state machine that drives the engine.  Instead, we've had a collection of bools scattered among several classes that indicate whether, for example, there's a pending style recalculation or whether we're in the middle of computing layout.

As part of switching the engine to be driven off animation frames instead of timers, we're making this state machine explicit in the DocumentLifecycle class.  Mutations from script will move the state machine backwards, for example invalidating layout or style information, causing the system to request an animation frame.  Once the compositor signals Blink that it's time to put up a frame, we'll drive the state machine forward towards the "Clean" state, at which point we will have reified the consequences of those DOM mutations and can commit a new tree of GraphicsLayers.

The primary advantage of moving to an explicit state machine is that we can prevent earlier phases of the state machine (e.g., style or layout) from reading information that's updated in later phases of the state machine (e.g., compositing).  Currently, we have a number of these "backwards" reads, which means we need to continually update compositing information when recalculating style and layout information.

Continually updating compositing information in this way is wasteful in the same way that recalculating style information more than once a frame is wasteful.  In some common situations, we can end up updating the same compositing information multiple times for a single animation frame.  If you'd like to help burn down these backwards reads, please consider fixing a bug on this list:

https://code.google.com/p/chromium/issues/list?q=label:CompositingChickenEgg

== Minimizing Invalidations ==

Even after removing redundant recalculation of style, layout, and compositing information, we can further reduce the amount of work the engine needs to do in order to commit the next frame by minimizing the amount of information that's invalidated by a given DOM mutation.  The less information that's invalidated in a given frame, the less the engine needs to compute to drive the state machine to Clean and commit the frame.

The style and layout systems already have elaborate systems for minimizing invalidations, but there are still a number of areas for improvement (e.g., [4] and [5]).  By contrast, the compositing update has only Document-level notions of invalidation.  We can reduce the amount of work required to update compositing information by tracking invalidates at a finer granularity, perhaps on individual RenderLayers.

One challenge with introducing fine-grained invalidations into compositing update is that one the key algorithms, the one that allocates RenderLayers to GraphicsLayers, depends on the spatial overlap between the RenderLayers.  For example, if script translates one RenderLayer, we need to recompute which other RenderLayers overlap that RenderLayer, quickly leading to a complete invalidation of all compositing information.

To address this issue, we are replacing the current algorithm for allocating RenderLayers to Graphics layers with another algorithm, squashing [6], that does not depend on spatial overlap.  This change will minimize the amount of compositing information that's invalidated when transforming a composited RenderLayer, which is a common operation to perform in response to touch input.

== Summary ==

To give web developers the tools they need to create high quality touch-driven interactions, we are retooling Blink's core rendering engine to run smoothly at 60 Hz.  Specifically:

1) We are switching the style and layout subsystems to be driven by animation frames instead of by arbitrary timers, reducing synchronization issues between these subsystems and the compositor.

2) We are making the rendering engine's state machine explicit to be more disciplined about what information can be read in which state, removing the need to continually recompute compositing state

3) We are minimizing the amount of retained state that's invalidated inside the engine in response to DOM mutations, reducing the total amount of work the engine need to perform in order to compute the next animation frame.

Thanks for reading this (absurdly long) message.  Happy hacking!

Adam

[1] https://groups.google.com/a/chromium.org/d/msg/blink-dev/Z5OzwYh3Wfk/IWooaY5FZowJ

[2] https://code.google.com/p/chromium/issues/detail?id=337617

[3] https://codereview.chromium.org/145663012/

[4] https://code.google.com/p/chromium/issues/detail?id=335247

[5] https://code.google.com/p/chromium/issues/detail?id=339729

[6] https://code.google.com/p/chromium/issues/detail?id=261605

[markb...@gmail.com]

This sounds promising but over the last few months I've seen Blink's rendering speed degrade fast.

This page is a heavyweight and I know there's plenty that can be done to improve it, yet Safari / webkit still have smooth scrolling and Chrome is jank city.
http://adioso.com/au/mel-to-syd-returning-in-2-weeks

What are the practical differences that exist now between webkit and blink that we need to know about?

[Adam Barth]

Hi Mark,

Would you be willing to file a bug about this issue?

http://crbug.com/new

If the issue is indeed a regression, it would be helpful if you could include the version prior to the regression in the bug report.

Thanks!

Adam

[Rune Lillesveen]

On Sun, Feb 2, 2014 at 10:10 AM, Adam Barth <aba...@chromium.org> wrote:

> == Minimizing Invalidations ==

> 3) We are minimizing the amount of retained state that's invalidated inside
> the engine in response to DOM mutations, reducing the total amount of work
> the engine need to perform in order to compute the next animation frame.

I think we should make the style change type argument non-default in
setNeedsStyleRecalc to make a SubtreeStyleChange a conscious choice
since it can be very expensive - potentially invalidating a forest of
sibling subtrees as well. I've uploaded a CL for it. Feel free to
review if you agree:

https://codereview.chromium.org/152623002/

The instances of SubtreeStyleChange should be looked at to see if some
could be changed to LocalStyleChange instead.

I've done SubtreeStyleChange -> LocalStyleChange for
:hover/:active/:focus (some awaiting more reviews). Those changes
takes advantage of affectedBy* vs childrenAffectedBy* to avoid a
SubtreeStyleChange. It's possible to do similar for class/id/attribute
selectors. I haven't looked at all the details of
https://codereview.chromium.org/143873016 , but it might be that it
can further optimize away SubtreeStyleChange and a tree walk in the
case where you change a class that is only present in the rightmost
subselector.

> Thanks for reading this (absurdly long) message. Happy hacking!

Thanks for posting!

--
Rune Lillesveen

[Adam Treat]

Hi Adam,

I'm still trying to process this email, but a few - perhaps naive -
questions quickly come to my mind:

*) With requestAnimationFrame being tightly tuned to vsync, what do we
do when a DOM mutation causes a style recalc/layout that we can not do
under the ~16ms threshhold? I like the idea of using an alternative
time mechanism that is tuned to vsync to reduce unnecessary
recalc/layout not in tune with vsync, but from my understand
requestAnimationFrame is a sort of contract where whatever work we key
off of it *must* be done in under ~16ms. How can we possibly guarantee
this for layout/style recalc of an arbitrarily complex page?

*) One big question I have been worrying about is how Oilpan and hence
garbage collection will introduce frame misses in our 60mhz goal. If we
have an arbitrary complex page where we are just barely coming under the
~16ms threshold and now we introduce non-deterministic garbage
collection somewhere that bumps us above ~16ms threshold ... how can
this be fixed even in principle?

In the old WebKit days each port was left up to its own devices as to
how to evolve past the "classical approach" of the update/render cycle
and take care of UI responsiveness. Apple had their own ideas and
technique for doing so. To put it way too simply, when I was working on
the blackberry port our answer was to put all UI interaction into
another thread that ran at a higher priority than the main WebKit
thread. I still don't grok the Chromium/Blink architecture well enough
to see what you are intending here, but it sounds very interesting.
Hope my questions are not too naive...

Cheers,
Adam

> To unsubscribe from this group and stop receiving emails from it, send
> an email to blink-dev+...@chromium.org.

[Adam Barth]

On Mon, Feb 3, 2014 at 6:57 AM, Adam Treat <adam....@samsung.com> wrote:

I'm still trying to process this email, but a few - perhaps naive - questions quickly come to my mind:

Please feel free to ask questions.  My intent in sending that email was to start a discussion that helps everyone get on the same page and work towards a common goal.

*) With requestAnimationFrame being tightly tuned to vsync, what do we do when a DOM mutation causes a style recalc/layout that we can not do under the ~16ms threshhold?  I like the idea of using an alternative time mechanism that is tuned to vsync to reduce unnecessary recalc/layout not in tune with vsync, but from my understand requestAnimationFrame is a sort of contract where whatever work we key off of it *must* be done in under ~16ms.  How can we possibly guarantee this for layout/style recalc of an arbitrarily complex page?

There's no contract that requestAnimationFrame callbacks need to run in under 16ms.  The compositor runs on a separate thread and doesn't ever block on the main thread.  If your requestAnimationFrame callback runs for more than 16ms, the data you commit to the compositor thread will just show up in a later vsync.  Scrolling and compositor-driven animations will continue to proceed jank-free.

It's probably more helpful to think about requestAnimationFrame as a throttle.  It makes sure you're not trying to commit data to the compositor faster than the compositor can consume it.  If the compositor is busy and can only consume data from the main thread at 30 Hz, then you'll only get 30 requestAnimationFrame callbacks per second.

This change shouldn't have much of an effect on large, complicated pages.  They're still not going to make any frame deadlines, but they're also not going to block any other parts of the system from doing useful work.  The main effect is to avoid doing extra work, e.g., recalcuating style twice in a frame.

*) One big question I have been worrying about is how Oilpan and hence garbage collection will introduce frame misses in our 60mhz goal.  If we have an arbitrary complex page where we are just barely coming under the ~16ms threshold and now we introduce non-deterministic garbage collection somewhere that bumps us above ~16ms threshold ... how can this be fixed even in principle?

That's a question we'll need to resolve before enabling Oilpan.  The experiments on the branch indicate that garbage collection, even for large pages, is extremely fast.  We have a number of smoothness benchmarks that stress the system in exactly the way you describe.  If Oilpan regresses those benchmarks in an appreciable way, we might not be able to use it.

In the old WebKit days each port was left up to its own devices as to how to evolve past the "classical approach" of the update/render cycle and take care of UI responsiveness.  Apple had their own ideas and technique for doing so.  To put it way too simply, when I was working on the blackberry port our answer was to put all UI interaction into another thread that ran at a higher priority than the main WebKit thread.  I still don't grok the Chromium/Blink architecture well enough to see what you are intending here, but it sounds very interesting.  Hope my questions are not too naive...

Those are good questions.  Thanks for asking them.

It's important to understand that Blink and WebKit are different in this respect.  There aren't any ports of Blink, and we strive for having all platforms work the same way.  Obviously, that's an ideal, and we fall short of that sometimes (e.g., we haven't enabled impl-side painting on Mac yet), but that's what we're aiming for.

Adam

To unsubscribe from this group and stop receiving emails from it, send an email to blink-dev+unsubscribe@chromium.org.

[Alexandre Elias]

On Mon, Feb 3, 2014 at 6:57 AM, Adam Treat <adam....@samsung.com> wrote:

To put it way too simply, when I was working on the blackberry port our answer was to put all UI interaction into another thread that ran at a higher priority than the main WebKit thread.

This is a very good point that cuts to the core of what we're trying to achieve with this initiative.  Like the Blackberry port (and indeed all mobile browsers that I know of), Chromium also has a higher-priority thread that can handle scroll and pinch at 60fps without involving the Blink main thread.  It's referred to as the "renderer compositor impl thread".  We introduced this thread while implementing the Android port of Chromium since like you, we found the main-thread jank problems intractable at the time.

But in the long term, this approach raises a serious problem for advanced webapps.  Webapp developers wish to perform arbitrary touch-driven interactions such as sliding side-panels, parallaxed backgrounds, etc.  As long as the main thread is jank-filled, they are powerless to implement these properly in Javascript and the burden falls on web browser implementors to add special support for each individual feature in C++ on the special jank-free thread.  No one will be very happy with this -- web browser implementors will need extra work and code complexity, while web developers will need to wait for standardization and still may not get a feature that matches exactly what they wanted.  So we decided that we need to make a push for Blink to also be able to run at 60fps, at least in the hands of a highly skilled webapp developer who knows how to avoid the expensive operations that block the main thread.

That said, this doesn't mean that when Blink can run at 60fps, we'll get rid of our high-priority compositor thread.  Some jank is unavoidable particularly during page load, and many websites out there are poorly written and won't be careful to avoid causing jank.  Basically, the plan is for the Blink thread to run at 60fps in the *best case*, while the compositor thread runs at 60fps in the *worst case*.

 

To unsubscribe from this group and stop receiving emails from it, send an email to blink-dev+unsubscribe@chromium.org.

[Adam Treat]

Alexandre,

Thanks so much for this!  Excellent explanation.  Indeed, it is great to take every opportunity to relieve the pressure on the main thread even if we have a higher priority thread for (most) user interactions.  Making style recalc and layout more efficient and just plain faster will do just that and explains Adam's motivation for working on them.

I think it would be really helpful to have some examples of properly written web apps that are not as responsive as we'd like due to excessive work on the main thread.  Where is this highly skilled JS example showing congestion on main thread even when the high priority one is smooth and thus affecting user perceived responsiveness?

Cheers,
Adam

To unsubscribe from this group and stop receiving emails from it, send an email to blink-dev+...@chromium.org.

[Adam Barth]

On Mon, Feb 3, 2014 at 12:33 PM, Adam Treat <adam....@samsung.com> wrote:

Thanks so much for this!  Excellent explanation.  Indeed, it is great to take every opportunity to relieve the pressure on the main thread even if we have a higher priority thread for (most) user interactions.  Making style recalc and layout more efficient and just plain faster will do just that and explains Adam's motivation for working on them.

I think it would be really helpful to have some examples of properly written web apps that are not as responsive as we'd like due to excessive work on the main thread.  Where is this highly skilled JS example showing congestion on main thread even when the high priority one is smooth and thus affecting user perceived responsiveness?

Yes, definitely.  That why we created the Silk page set:

http://src.chromium.org/viewvc/chrome/trunk/src/tools/perf/page_sets/key_silk_cases/

You can run those examples with the Telemetry testing framework to see how they work.  If you want to see congestion and synchronization issues, I recommend running with --profiler=trace.  For example, this command line will produce a trace of the infinite_scrolling.html page:

./tools/perf/run_measurement --browser=android-chromium-testshell smoothness tools/perf/page_sets/key_silk_cases.json --profiler=trace --page-filter=infinite_scrolling.html

[Peter Kasting]

Naive question: if updates get driven off a periodic animation timer, are we potentially introducing more latency in our quest to increase throughput?

For example, perhaps previously we had a "user presses key -> input is processed and triggers relayout -> layout occurs -> repaint displays update onscreen" pipeline that took n ms.  If changes we make result in introducing any delays in this pipeline, we could introduce an additional frame of latency before user inputs are reflected onscreen.  This would certainly matter for games, perhaps also somewhat for nice-feeling scrolling.

This question may be nonsensical due to my limited understanding of the current or proposed timing mechanisms; if so, I apologize.

PK

[Brian C. Anderson]

There are a lot of subtleties regarding input latency.

In the simple case, where you start off idle and hit a single key, delaying the update will add latency. There are some cases where delaying an update actually improves latency though, especially for content that is constantly drawing:

• A 120Hz mouse + 60Hz screen. Waiting for a second input event can reduce latency by ~8ms. If it doesn't improve latency, then we at least consume the same number of events per frame rather than potentially alternating 1 and 3 events per frame, which would show up as latency jank.
• If the Impl thread consumes input and updates immediately, without waiting for the main thread to commit, then we automatically put the main thread into a high latency mode if it is also trying to produce frames.

There are many tradeoffs and we are trying to be careful about which ones to make.

-Brian

To unsubscribe from this group and stop receiving emails from it, send an email to blink-dev+...@chromium.org.

[Nat Duca]

On the bright side, input-dev@chromium is a subteam focused on building an armory of latency benchmarking features so that we can catch any regressions/improvements this work causes: some are pure-software based, and some are camera-based.

https://codereview.chromium.org/132433004/ just got lgtm'd in fact and will start reporting the latency for scrolls on all our smoothness metrics on chromeperf.appspot.com.

Once we get scroll latency tracking well, we'll be adding keypress-to-screen latency measurement capability.

[and...@deandrade.com.br]

Please also look into adding an element.style API that let's us set the CSS 3D Matrix via arrays of numbers instead of forcing us to stringify the results to only have the browser have to reparse those floats.

At the end of the day the DOM is a system with only two data types: strings and children. This is such an inadequate type system for efficiently updating the DOM. It's doesn't have to be this way though.

 

Simply allowing developers to set CSS properties via numbers instead of forcing front end devs to usually do string conversion/concatenation to produce the string literal used in style assignment would be awesome.

This whole notion that all CSS properties need to be converted to a string is a bottleneck when you want to make many simultaneous changes on the DOM in one requestAnimationFrame loop. This is a performance improvement that is easily overlooked in benchmarks because it's a tiny part of each performance unit test. But these types of tests ignore cases when many DOM elements may be updated at once.

We really need a CSS styling interface that uses functions instead of assignment, where youcan  pass in the numbers and the units as two separate arguments. e.g. element.style.set("width", 100, "px");

[Eric Seidel]

crbug.com/324107 tracks some of what you're asking for. We looked
into this quite a bit last month and found that although strings as
the only in/out for element.style *is* definitely an issue for
authors, it doesn't appear to be the gating factor for smooth
animations.

Once we remove the other bottlenecks in Blink's rendering system we
will definitely look at creating a better CSSOM.

Thanks for the feedback!

[Tab Atkins]

On Sat, Feb 8, 2014 at 6:07 AM, Eric Seidel <ese...@chromium.org> wrote:
> On Sat, Feb 8, 2014 at 9:36 PM, <ad...@improvisu.com> wrote:
>> Please also look into adding an element.style API that let's us set the CSS
>> 3D Matrix via arrays of numbers instead of forcing us to stringify the
>> results to only have the browser have to reparse those floats.
>

> crbug.com/324107 tracks some of what you're asking for. We looked
> into this quite a bit last month and found that although strings as
> the only in/out for element.style *is* definitely an issue for
> authors, it doesn't appear to be the gating factor for smooth
> animations.
>
> Once we remove the other bottlenecks in Blink's rendering system we
> will definitely look at creating a better CSSOM.

Yup, I've got an initial proposal that met with approval in the CSSWG,
loosely documented in my blog post <http://www.xanthir.com/b4UD0>.

It'll be a while before it's implementable anyway, because part of its
performance guarantees rely on JS Value Objects, which are still in
the early spec stages. Give it a year or two before we can start
implementing it.

Using that, updating a transform would look something like:

el.css.transform = CSS.matrix3d(1, 2, 3, 4, ...);

Where the matrix3d function is an immutable block of 16 numbers, and
thus highly optimizeable.

We could also expose something even more direct, before we try and
implement this full API, such as just exposing a Float32Array on
elements that you can manipulate directly as a Typed Array.

But as Eric says, there are currently a ton of longer tent poles to
address before this really becomes something to concern ourselves with
solving. Rest assured that we're thinking of it, though!

~TJ

[Eric Seidel]

It's also worth mentioning Dan's repaint-after-layout project which is
another part of the "split into explicit phases" effort.

The goal there is to reduce the complexity of our current spew of
repaint calls throughout layout() as well as to eliminate the
over-invalidations caused by 2-pass layouts (e.g. when a table lays
out its cells those cells contents invalidate both their old and new
rects, but the first time they're laid out the new rect is wrong and
the second time the old rect is wrong).

This work is tracked via crbug.com/310398 and dependent bugs.

Please be on the look-out for under-painting bugs in the next few
weeks after Dan turns his new code on by default. Re-writing core
assumptions of the engine like this is bound to break things. :)

[and...@deandrade.com.br]

On Saturday, February 8, 2014 11:21:06 AM UTC-8, Tab Atkins wrote:

Yup, I've got an initial proposal that met with approval in the CSSWG,
loosely documented in my blog post <http://www.xanthir.com/b4UD0>.

Awesome. Will take a closer look.

 

It'll be a while before it's implementable anyway, because part of its
performance guarantees rely on JS Value Objects, which are still in
the early spec stages.  Give it a year or two before we can start
implementing it. 

 

Is there any way in which one could help to get this in sooner? i.e. where can one contribute specifically that would lay the groundwork for this to be solvable/implementable sooner.

 

Using that, updating a transform would look something like:

el.css.transform = CSS.matrix3d(1, 2, 3, 4, ...);

Where the matrix3d function is an immutable block of 16 numbers, and
thus highly optimizeable.

We could also expose something even more direct, before we try and
implement this full API, such as just exposing a Float32Array on
elements that you can manipulate directly as a Typed Array.

This would be awesome. More direct is better IMHO, especially if it can be implemented sooner than later. At the end of the day, those most interested in performing these kinds of operations are going to want the most direct/efficient solution possible. 

 

But as Eric says, there are currently a ton of longer tent poles to
address before this really becomes something to concern ourselves with
solving.  Rest assured that we're thinking of it, though!

Cool beans.

 

~TJ

[PhistucK]

JavaScript Value Objects depend on ECMAScript, which means it depends on some consensus and a new edition of the ECMAScript standard as a result of that consensus. This takes a while...

☆PhistucK

To unsubscribe from this group and stop receiving emails from it, send an email to blink-dev+...@chromium.org.