StartAnimation: Optimized the search for Animations which is waiting for TargetAvailability

cc: Optimize search in LayerAnimationController::StartAnimations


During StartAnimation first it does a search for all animations which are
running and starting. After that it again searches the entire animation
list for animations waiting for target availability.

This patch reduces this search (for loops) by keeping track of the
animations waiting for target availability in the first search itself.


BUG=396562
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=285561

[shreyas.g, 2014-07-21 11:01:57]

PTAL. Thanks

[shreyas.g, 2014-07-21 12:04:23]

ajuma@chromium.org: Please review the changes. Thanks

[vivekg, 2014-07-21 12:39:33]

https://codereview.chromium.org/408833002/diff/1/cc/animation/layer_animation...
File cc/animation/layer_animation_controller.cc (right):

https://codereview.chromium.org/408833002/diff/1/cc/animation/layer_animation...
cc/animation/layer_animation_controller.cc:605: AnimationMap
waitingfor_target_animations_;
nit: waitingfor_target_animations_ => animations_waiting_for_target

https://codereview.chromium.org/408833002/diff/1/cc/animation/layer_animation...
File cc/animation/layer_animation_controller.h (right):

https://codereview.chromium.org/408833002/diff/1/cc/animation/layer_animation...
cc/animation/layer_animation_controller.h:214: typedef base::hash_map<int,
Animation*> AnimationMap;
nit: change "int => unsigned" as size_t is non-negative.

[shreyas.g, 2014-07-21 13:00:37]

Made changes based on Viveks comments. Thanks.

https://codereview.chromium.org/408833002/diff/1/cc/animation/layer_animation...
File cc/animation/layer_animation_controller.cc (right):

https://codereview.chromium.org/408833002/diff/1/cc/animation/layer_animation...
cc/animation/layer_animation_controller.cc:605: AnimationMap
waitingfor_target_animations_;
On 2014/07/21 12:39:32, vivekg_ wrote:
> nit: waitingfor_target_animations_ => animations_waiting_for_target

Done.

https://codereview.chromium.org/408833002/diff/1/cc/animation/layer_animation...
File cc/animation/layer_animation_controller.h (right):

https://codereview.chromium.org/408833002/diff/1/cc/animation/layer_animation...
cc/animation/layer_animation_controller.h:214: typedef base::hash_map<int,
Animation*> AnimationMap;
On 2014/07/21 12:39:32, vivekg_ wrote:
> nit: change "int => unsigned" as size_t is non-negative.

Done.

[kishorags_, 2014-07-21 13:53:39]

A bug capturing the data on improvement can be helpful for reviewers. Thanks

[ajuma, 2014-07-21 14:22:19]

Thanks for looking into this.

On 2014/07/21 13:53:39, kishorags_ wrote:
> A bug capturing the data on improvement can be helpful for reviewers. Thanks

Yes, I'm interested in any performance data you have. Note that the typical size
of |animations_| (when non-zero) is 1 or 2, and the |needs_to_start_animations|
logic means we only call StartAnimations when at least one animation is waiting
for target availability. So the approach in this CL means that in the second for
loop, we might iterate over 0 or 1 fewer animations in the typical case. But the
cost is constructing a hash_map, and iterating over a hash_map rather than over
a vector in the second for loop.

[shreyas.g, 2014-07-21 14:46:22]

On 2014/07/21 14:22:19, ajuma wrote:
> Thanks for looking into this.
> 
> On 2014/07/21 13:53:39, kishorags_ wrote:
> > A bug capturing the data on improvement can be helpful for reviewers. Thanks
> 
> Yes, I'm interested in any performance data you have. Note that the typical
size
> of |animations_| (when non-zero) is 1 or 2, and the
|needs_to_start_animations|
> logic means we only call StartAnimations when at least one animation is
waiting
> for target availability. So the approach in this CL means that in the second
for
> loop, we might iterate over 0 or 1 fewer animations in the typical case. But
the
> cost is constructing a hash_map, and iterating over a hash_map rather than
over
> a vector in the second for loop.

Thank you so much Gandhi and Ajuma to look into this patch.

Yes I agree that hashmap might not be the right way. I have added another patch
by 
replacing the same with vector.

And regarding the data, I analyzed the given layout test cases itself. Like you 
mentioned most of the times the total animations range from 1-5, but the target 
animations is hardly 0, 1, 2. 

Maybe with the above vector based patch, the cost of hash map can be reduced.

[ajuma, 2014-07-21 15:09:06]

On 2014/07/21 14:46:22, shreyas.g wrote:
> On 2014/07/21 14:22:19, ajuma wrote:
> > Thanks for looking into this.
> > 
> > On 2014/07/21 13:53:39, kishorags_ wrote:
> > > A bug capturing the data on improvement can be helpful for reviewers.
Thanks
> > 
> > Yes, I'm interested in any performance data you have. Note that the typical
> size
> > of |animations_| (when non-zero) is 1 or 2, and the
> |needs_to_start_animations|
> > logic means we only call StartAnimations when at least one animation is
> waiting
> > for target availability. So the approach in this CL means that in the second
> for
> > loop, we might iterate over 0 or 1 fewer animations in the typical case. But
> the
> > cost is constructing a hash_map, and iterating over a hash_map rather than
> over
> > a vector in the second for loop.
> 
> Thank you so much Gandhi and Ajuma to look into this patch.
> 
> Yes I agree that hashmap might not be the right way. I have added another
patch
> by 
> replacing the same with vector.
> 
> And regarding the data, I analyzed the given layout test cases itself. Like
you 
> mentioned most of the times the total animations range from 1-5, but the
target 
> animations is hardly 0, 1, 2. 

Note that there's one layer animation controller per layer, not per page. Since
the only properties we accelerate are opacity, transform, and filter, it seems
pretty unlikely that we'd have 5 animations at any time in practice (it's not
entirely impossible, e.g. we could have some animations waiting for deletion,
and some new ones, but still, the typical case when non-zero is going to be 1 or
2). Is there a specific test case where you're seeing something different?

> Maybe with the above vector based patch, the cost of hash map can be reduced.

This version does seem like an improvement over the hash map version. It would
still be good to have some data though. Can you construct an example page where
there's a performance improvement (that is, where the time spent in
StartAnimations is reduced)? Also, can you measure that in the typical case
where StartAnimations gets called (where all or almost all animations are
waiting), there's no performance loss?

[shreyas.g, 2014-07-23 05:33:41]

On 2014/07/21 15:09:06, ajuma wrote:
> On 2014/07/21 14:46:22, shreyas.g wrote:
> > On 2014/07/21 14:22:19, ajuma wrote:
> > > Thanks for looking into this.
> > > 
> > > On 2014/07/21 13:53:39, kishorags_ wrote:
> > > > A bug capturing the data on improvement can be helpful for reviewers.
> Thanks
> > > 
> > > Yes, I'm interested in any performance data you have. Note that the
typical
> > size
> > > of |animations_| (when non-zero) is 1 or 2, and the
> > |needs_to_start_animations|
> > > logic means we only call StartAnimations when at least one animation is
> > waiting
> > > for target availability. So the approach in this CL means that in the
second
> > for
> > > loop, we might iterate over 0 or 1 fewer animations in the typical case.
But
> > the
> > > cost is constructing a hash_map, and iterating over a hash_map rather than
> > over
> > > a vector in the second for loop.
> > 
> > Thank you so much Gandhi and Ajuma to look into this patch.
> > 
> > Yes I agree that hashmap might not be the right way. I have added another
> patch
> > by 
> > replacing the same with vector.
> > 
> > And regarding the data, I analyzed the given layout test cases itself. Like
> you 
> > mentioned most of the times the total animations range from 1-5, but the
> target 
> > animations is hardly 0, 1, 2. 
> 
> Note that there's one layer animation controller per layer, not per page.
Since
> the only properties we accelerate are opacity, transform, and filter, it seems
> pretty unlikely that we'd have 5 animations at any time in practice (it's not
> entirely impossible, e.g. we could have some animations waiting for deletion,
> and some new ones, but still, the typical case when non-zero is going to be 1
or
> 2). Is there a specific test case where you're seeing something different?
> 
> > Maybe with the above vector based patch, the cost of hash map can be
reduced.
> 
> This version does seem like an improvement over the hash map version. It would
> still be good to have some data though. Can you construct an example page
where
> there's a performance improvement (that is, where the time spent in
> StartAnimations is reduced)? Also, can you measure that in the typical case
> where StartAnimations gets called (where all or almost all animations are
> waiting), there's no performance loss?

Yes you are right. In real world examples most of the test cases dont have high
number
of animations running or waiting to be run. Moreover the waiting animations are
equal to
the animations added. But in the unit test cases which allows the tester to be
liberal with
the addition many cases, the waiting animations are less compared to total
animations.
Moreover the content developer can in the future write content which might
create the 
issue mentioned in this bug.

To tackle this above scenario, first the patch should ensure that real world
scenarios 
there is no degradation (like you said in cases where all or almost all
animations are
 waiting). I am working on a patch wherein I have optimized the vector pair of
animation
/index to just the index. And also since this index vector is of fixed size (it
cant go 
beyond the animations list), I can resize and just place the index instead of
using 
push_back which is costly operation. 

With this above patch when i used trace most of the real world scenarios it is
showing same 
time consumption (actually slightly better values) as compared to current code
and it skips many 
unwanted for loops specially in the unit test case. I will work more on it and
update.

[shreyas.g, 2014-07-23 09:43:53]

Please take a look at site http://codepen.io/keithclark/pen/dlhJm?editors=010

In this there is a queing of animations and when I added a log the 
startAnimation always has one waiting for target and the total animations are 
3. The for loop is executed in this case 3 times even though there is only one
animation waiting for target.

[shreyas.g, 2014-07-23 13:01:46]

PTAL at patchset 4.
With this I see improvement in cases where all animations are waiting 
for target and also in cases when the waiting animations are lesser
than total number of animations.

I have added traces and other information in BUG=396562.
Please note that the improvement is in microseconds and add to that the
function is now more optimized and will handle future such cases (if 
number of animation properties increase).

[ajuma, 2014-07-23 16:02:18]

Thanks for the investigation, this is looking much improved.

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
File cc/animation/layer_animation_controller.cc (right):

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:605: std::vector<size_t>
animations_waiting_for_target_index_;
Calling this |animations_waiting_for_target| seems easier to read.

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:608:
animations_waiting_for_target_index_.resize(animations_.size());
How about using reserve instead of resize, and then just using push_back to
insert? Then you don't need |index| anymore.

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:626: for (size_t i = 0; i < index;
++i) {
With the above suggestion to use |reserve| instead of |resize|, you can use
animations_waiting_for_target.size() here.

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:629: size_t animIndex =
animations_waiting_for_target_index_[i];
nit: animation_index

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:630: Animation*
animation_waiting_for_target = animations_[animIndex];
You still need to check if this animation is actually waiting for target
availability. See the code below that changes run state
(animations_[j]->SetRunState...). It'd be helpful to add a (short) comment
explaining why this re-check is needed.

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:631: TargetProperties
enqueued_properties;
Nit: indentation needs to be fixed (just run 'git cl format').

[shreyas.g, 2014-07-24 10:03:35]

Thanks Ajuma for doing the review and providing inputs.
PTAL at patchset 5

I have incorportated all the changes.
The reserve change was added instead of resize (along with additional 
check for waiting inside the second for loop) and I took trace
for all the examples, there was no degradation. Infact the performance was
slightly better than previous patchset which used resize.

[shreyas.g, 2014-07-24 10:03:50]

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
File cc/animation/layer_animation_controller.cc (right):

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:605: std::vector<size_t>
animations_waiting_for_target_index_;
On 2014/07/23 16:02:18, ajuma wrote:
> Calling this |animations_waiting_for_target| seems easier to read.

Done.

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:608:
animations_waiting_for_target_index_.resize(animations_.size());
On 2014/07/23 16:02:18, ajuma wrote:
> How about using reserve instead of resize, and then just using push_back to
> insert? Then you don't need |index| anymore.

Done.

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:626: for (size_t i = 0; i < index;
++i) {
On 2014/07/23 16:02:18, ajuma wrote:
> With the above suggestion to use |reserve| instead of |resize|, you can use
> animations_waiting_for_target.size() here.

Done.

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:629: size_t animIndex =
animations_waiting_for_target_index_[i];
On 2014/07/23 16:02:18, ajuma wrote:
> nit: animation_index

Done.

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:630: Animation*
animation_waiting_for_target = animations_[animIndex];
On 2014/07/23 16:02:18, ajuma wrote:
> You still need to check if this animation is actually waiting for target
> availability. See the code below that changes run state
> (animations_[j]->SetRunState...). It'd be helpful to add a (short) comment
> explaining why this re-check is needed.

Done.

https://codereview.chromium.org/408833002/diff/60001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:631: TargetProperties
enqueued_properties;
On 2014/07/23 16:02:18, ajuma wrote:
> Nit: indentation needs to be fixed (just run 'git cl format').

Done.

[ajuma, 2014-07-24 14:51:07]

Please update the description so the first line is a short summary (e.g. "cc:
Optimize search in LayerAnimationController::StartAnimations").

Also one very minor nit below:

https://codereview.chromium.org/408833002/diff/80001/cc/animation/layer_anima...
File cc/animation/layer_animation_controller.cc (right):

https://codereview.chromium.org/408833002/diff/80001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:632: // previous animation in this
loop (if they belong to same group)
Nit: missing period at the end of the sentence

[shreyas.g, 2014-07-24 15:08:16]

Added description and small nit change

https://codereview.chromium.org/408833002/diff/80001/cc/animation/layer_anima...
File cc/animation/layer_animation_controller.cc (right):

https://codereview.chromium.org/408833002/diff/80001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:632: // previous animation in this
loop (if they belong to same group)
On 2014/07/24 14:51:07, ajuma wrote:
> Nit: missing period at the end of the sentence

Done.

[ajuma, 2014-07-24 15:09:29]

Thanks, lgtm.

[shreyas.g, 2014-07-25 06:37:00]

The CQ bit was checked by shreyas.g@samsung.com

[shreyas.g, 2014-07-25 06:37:14]

The CQ bit was unchecked by shreyas.g@samsung.com

[shreyas.g, 2014-07-25 06:37:19]

The CQ bit was checked by shreyas.g@samsung.com

[shreyas.g, 2014-07-25 06:37:19]

The CQ bit was unchecked by shreyas.g@samsung.com

[shreyas.g, 2014-07-25 06:37:20]

The CQ bit was checked by shreyas.g@samsung.com

[commit-bot: I haz the power, 2014-07-25 06:39:13]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/shreyas.g@samsung.com/408833002/100001

[commit-bot: I haz the power, 2014-07-25 10:54:54]

Change committed as 285561