Reduced iterations for group-id check in MarkAnimationsForDeletions

cc: Optimize group id check in 
LayerAnimationController::MarkAnimationsForDeletion


MarkAnimationsForDeletion first checks if all the animations with the
same group ID as the current animation is finished or not. If no,
nothing is done. If yes, then in another iteration it again finds all
the animations after the current animation in the list with the same 
group ID and marks it for WaitingForDeletion.

This patch executes the MarkAnimationsForDeletion for animations with 
minimum iterations. While checking if all the animations with same ID
is finished also mark the animations which satisfy this condition. 
Later use these marked animations to reduce the iterations.

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

[shreyas.g, 2014-07-30 13:17:42]

PTAL.

[shreyas.g, 2014-07-30 13:19:20]

++Reviewers Vivek, Siva, Muven

[shreyas.g, 2014-07-30 14:24:25]

Also added data with examples and trace information to the bug 396562. PTAL.

[ajuma, 2014-07-30 15:22:47]

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

https://codereview.chromium.org/429223002/diff/20001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:762:
animation_i_will_send_or_has_received_finish_event) {
What if you just create the animations_with_same_group_id vector here rather
than above? Then you wouldn't need to have animations_with_same_id_count and
animations_with_same_group_id_reserved.

Note that this code inside this 'if' gets executed pretty rarely (in practice,
once per animation, since Blink doesn't try to group animations using group ids
right now), so it's probably not worth the added complexity of maintaining those
two additional variables.

[shreyas.g, 2014-07-30 15:53:00]

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

https://codereview.chromium.org/429223002/diff/20001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:762:
animation_i_will_send_or_has_received_finish_event) {
On 2014/07/30 15:22:47, ajuma wrote:
> What if you just create the animations_with_same_group_id vector here rather
> than above? Then you wouldn't need to have animations_with_same_id_count and
> animations_with_same_group_id_reserved.
> 
> Note that this code inside this 'if' gets executed pretty rarely (in practice,
> once per animation, since Blink doesn't try to group animations using group
ids
> right now), so it's probably not worth the added complexity of maintaining
those
> two additional variables.

Thanks Ajuma. The problem here is that, if i declare the variables after the if
condition, then it cant be shared with the condition if
(all_anims_with_same_id_are_finished) {

The best that can be done is maintain animations_with_same_group_id vector for
each animation in the main for loop (for (size_t i = 0; i < animations_.size();
i++) {), thereby the variables animations_with_same_group_id_count_ and
animations_with_same_group_id_reserved can be avoided and still be shared
between first groupid based iteration to next. Will that be ok?

[ajuma, 2014-07-30 16:00:00]

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

https://codereview.chromium.org/429223002/diff/20001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:762:
animation_i_will_send_or_has_received_finish_event) {
On 2014/07/30 15:52:59, shreyas.g wrote:
> On 2014/07/30 15:22:47, ajuma wrote:
> > What if you just create the animations_with_same_group_id vector here rather
> > than above? Then you wouldn't need to have animations_with_same_id_count and
> > animations_with_same_group_id_reserved.
> > 
> > Note that this code inside this 'if' gets executed pretty rarely (in
practice,
> > once per animation, since Blink doesn't try to group animations using group
> ids
> > right now), so it's probably not worth the added complexity of maintaining
> those
> > two additional variables.
> 
> Thanks Ajuma. The problem here is that, if i declare the variables after the
if
> condition, then it cant be shared with the condition if
> (all_anims_with_same_id_are_finished) {
> 
> The best that can be done is maintain animations_with_same_group_id vector for
> each animation in the main for loop (for (size_t i = 0; i <
animations_.size();
> i++) {), thereby the variables animations_with_same_group_id_count_ and
> animations_with_same_group_id_reserved can be avoided and still be shared
> between first groupid based iteration to next. Will that be ok?

Hmm. Creating a vector for each animation in the main loop is probably going to
be a regression, since this will happen for every animation on every iteration.
What if you leave animations_with_same_group_id where it currently is, but then
use clear() as you suggest below? Have you measured the performance of that?

[shreyas.g, 2014-08-01 08:44:05]

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

https://codereview.chromium.org/429223002/diff/20001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:762:
animation_i_will_send_or_has_received_finish_event) {
On 2014/07/30 16:00:00, ajuma wrote:
> On 2014/07/30 15:52:59, shreyas.g wrote:
> > On 2014/07/30 15:22:47, ajuma wrote:
> > > What if you just create the animations_with_same_group_id vector here
rather
> > > than above? Then you wouldn't need to have animations_with_same_id_count
and
> > > animations_with_same_group_id_reserved.
> > > 
> > > Note that this code inside this 'if' gets executed pretty rarely (in
> practice,
> > > once per animation, since Blink doesn't try to group animations using
group
> > ids
> > > right now), so it's probably not worth the added complexity of maintaining
> > those
> > > two additional variables.
> > 
> > Thanks Ajuma. The problem here is that, if i declare the variables after the
> if
> > condition, then it cant be shared with the condition if
> > (all_anims_with_same_id_are_finished) {
> > 
> > The best that can be done is maintain animations_with_same_group_id vector
for
> > each animation in the main for loop (for (size_t i = 0; i <
> animations_.size();
> > i++) {), thereby the variables animations_with_same_group_id_count_ and
> > animations_with_same_group_id_reserved can be avoided and still be shared
> > between first groupid based iteration to next. Will that be ok?
> 
> Hmm. Creating a vector for each animation in the main loop is probably going
to
> be a regression, since this will happen for every animation on every
iteration.
> What if you leave animations_with_same_group_id where it currently is, but
then
> use clear() as you suggest below? Have you measured the performance of that? 


Yes, clear is working now. I had previously tried the same but it did not show
improvement. The change that helped is to check the size before clear. I have
also added the new traces to the bug.

[ajuma, 2014-08-01 14:27:04]

On 2014/08/01 08:44:05, shreyas.g wrote:
>
https://codereview.chromium.org/429223002/diff/20001/cc/animation/layer_anima...
> File cc/animation/layer_animation_controller.cc (right):
> 
>
https://codereview.chromium.org/429223002/diff/20001/cc/animation/layer_anima...
> cc/animation/layer_animation_controller.cc:762:
> animation_i_will_send_or_has_received_finish_event) {
> On 2014/07/30 16:00:00, ajuma wrote:
> > On 2014/07/30 15:52:59, shreyas.g wrote:
> > > On 2014/07/30 15:22:47, ajuma wrote:
> > > > What if you just create the animations_with_same_group_id vector here
> rather
> > > > than above? Then you wouldn't need to have animations_with_same_id_count
> and
> > > > animations_with_same_group_id_reserved.
> > > > 
> > > > Note that this code inside this 'if' gets executed pretty rarely (in
> > practice,
> > > > once per animation, since Blink doesn't try to group animations using
> group
> > > ids
> > > > right now), so it's probably not worth the added complexity of
maintaining
> > > those
> > > > two additional variables.
> > > 
> > > Thanks Ajuma. The problem here is that, if i declare the variables after
the
> > if
> > > condition, then it cant be shared with the condition if
> > > (all_anims_with_same_id_are_finished) {
> > > 
> > > The best that can be done is maintain animations_with_same_group_id vector
> for
> > > each animation in the main for loop (for (size_t i = 0; i <
> > animations_.size();
> > > i++) {), thereby the variables animations_with_same_group_id_count_ and
> > > animations_with_same_group_id_reserved can be avoided and still be shared
> > > between first groupid based iteration to next. Will that be ok?
> > 
> > Hmm. Creating a vector for each animation in the main loop is probably going
> to
> > be a regression, since this will happen for every animation on every
> iteration.
> > What if you leave animations_with_same_group_id where it currently is, but
> then
> > use clear() as you suggest below? Have you measured the performance of that?

> 
> 
> Yes, clear is working now. I had previously tried the same but it did not show
> improvement. The change that helped is to check the size before clear. I have
> also added the new traces to the bug.

Thanks. Have you also measured the typical case (where we have a one or two
animations, and none is finished)? Since this is going to happen much more
frequently than the case where we have finished animations (e.g. for a 2 second
animation at 60 frames per second, we'll have a 119 calls where we have no
finished animation, and one call with a finished animation), a small regression
for this case could outweigh a large improvement in the case where we do have
finished animations.

[shreyas.g, 2014-08-01 14:39:05]

On 2014/08/01 14:27:04, ajuma wrote:
> On 2014/08/01 08:44:05, shreyas.g wrote:
> >
>
https://codereview.chromium.org/429223002/diff/20001/cc/animation/layer_anima...
> > File cc/animation/layer_animation_controller.cc (right):
> > 
> >
>
https://codereview.chromium.org/429223002/diff/20001/cc/animation/layer_anima...
> > cc/animation/layer_animation_controller.cc:762:
> > animation_i_will_send_or_has_received_finish_event) {
> > On 2014/07/30 16:00:00, ajuma wrote:
> > > On 2014/07/30 15:52:59, shreyas.g wrote:
> > > > On 2014/07/30 15:22:47, ajuma wrote:
> > > > > What if you just create the animations_with_same_group_id vector here
> > rather
> > > > > than above? Then you wouldn't need to have
animations_with_same_id_count
> > and
> > > > > animations_with_same_group_id_reserved.
> > > > > 
> > > > > Note that this code inside this 'if' gets executed pretty rarely (in
> > > practice,
> > > > > once per animation, since Blink doesn't try to group animations using
> > group
> > > > ids
> > > > > right now), so it's probably not worth the added complexity of
> maintaining
> > > > those
> > > > > two additional variables.
> > > > 
> > > > Thanks Ajuma. The problem here is that, if i declare the variables after
> the
> > > if
> > > > condition, then it cant be shared with the condition if
> > > > (all_anims_with_same_id_are_finished) {
> > > > 
> > > > The best that can be done is maintain animations_with_same_group_id
vector
> > for
> > > > each animation in the main for loop (for (size_t i = 0; i <
> > > animations_.size();
> > > > i++) {), thereby the variables animations_with_same_group_id_count_ and
> > > > animations_with_same_group_id_reserved can be avoided and still be
shared
> > > > between first groupid based iteration to next. Will that be ok?
> > > 
> > > Hmm. Creating a vector for each animation in the main loop is probably
going
> > to
> > > be a regression, since this will happen for every animation on every
> > iteration.
> > > What if you leave animations_with_same_group_id where it currently is, but
> > then
> > > use clear() as you suggest below? Have you measured the performance of
that?
> 
> > 
> > 
> > Yes, clear is working now. I had previously tried the same but it did not
show
> > improvement. The change that helped is to check the size before clear. I
have
> > also added the new traces to the bug.
> 
> Thanks. Have you also measured the typical case (where we have a one or two
> animations, and none is finished)? Since this is going to happen much more
> frequently than the case where we have finished animations (e.g. for a 2
second
> animation at 60 frames per second, we'll have a 119 calls where we have no
> finished animation, and one call with a finished animation), a small
regression
> for this case could outweigh a large improvement in the case where we do have
> finished animations.

Thanks Ajuma. Thats a very good point you make there. We do need to check for
cases
where the animation does not finish at all. I can modify the layeranimation test
case
in the bug to check that and add that trace.

As of now this change has 2 sections:
1. Reserving the vector (that will be done for all cases, even when not
finsihed). So 
I have to check the cost of that. Ideally it should not be huge.2

2. Clearing the vector and adding the index to vector: But I think this cost
will be 
lesser than the cost of running the for loop multiple times to check for the
group ID.

I will check and confirm regarding the same.

[ajuma, 2014-08-01 14:42:02]

On 2014/08/01 14:39:05, shreyas.g wrote:
> Thanks Ajuma. Thats a very good point you make there. We do need to check for
> cases
> where the animation does not finish at all. I can modify the layeranimation
test
> case
> in the bug to check that and add that trace.
> 
> As of now this change has 2 sections:
> 1. Reserving the vector (that will be done for all cases, even when not
> finsihed). So 
> I have to check the cost of that. Ideally it should not be huge.2
> 
> 2. Clearing the vector and adding the index to vector: But I think this cost
> will be 
> lesser than the cost of running the for loop multiple times to check for the
> group ID.
> 
> I will check and confirm regarding the same.

Right, (1) is the thing to worry about for the case of no finished animations.
When there are no finished animations, the code for (2) won't be reached.

[shreyas.g, 2014-08-01 15:13:09]

On 2014/08/01 14:39:05, shreyas.g wrote:
> On 2014/08/01 14:27:04, ajuma wrote:
> > On 2014/08/01 08:44:05, shreyas.g wrote:
> > >
> >
>
https://codereview.chromium.org/429223002/diff/20001/cc/animation/layer_anima...
> > > File cc/animation/layer_animation_controller.cc (right):
> > > 
> > >
> >
>
https://codereview.chromium.org/429223002/diff/20001/cc/animation/layer_anima...
> > > cc/animation/layer_animation_controller.cc:762:
> > > animation_i_will_send_or_has_received_finish_event) {
> > > On 2014/07/30 16:00:00, ajuma wrote:
> > > > On 2014/07/30 15:52:59, shreyas.g wrote:
> > > > > On 2014/07/30 15:22:47, ajuma wrote:
> > > > > > What if you just create the animations_with_same_group_id vector
here
> > > rather
> > > > > > than above? Then you wouldn't need to have
> animations_with_same_id_count
> > > and
> > > > > > animations_with_same_group_id_reserved.
> > > > > > 
> > > > > > Note that this code inside this 'if' gets executed pretty rarely (in
> > > > practice,
> > > > > > once per animation, since Blink doesn't try to group animations
using
> > > group
> > > > > ids
> > > > > > right now), so it's probably not worth the added complexity of
> > maintaining
> > > > > those
> > > > > > two additional variables.
> > > > > 
> > > > > Thanks Ajuma. The problem here is that, if i declare the variables
after
> > the
> > > > if
> > > > > condition, then it cant be shared with the condition if
> > > > > (all_anims_with_same_id_are_finished) {
> > > > > 
> > > > > The best that can be done is maintain animations_with_same_group_id
> vector
> > > for
> > > > > each animation in the main for loop (for (size_t i = 0; i <
> > > > animations_.size();
> > > > > i++) {), thereby the variables animations_with_same_group_id_count_
and
> > > > > animations_with_same_group_id_reserved can be avoided and still be
> shared
> > > > > between first groupid based iteration to next. Will that be ok?
> > > > 
> > > > Hmm. Creating a vector for each animation in the main loop is probably
> going
> > > to
> > > > be a regression, since this will happen for every animation on every
> > > iteration.
> > > > What if you leave animations_with_same_group_id where it currently is,
but
> > > then
> > > > use clear() as you suggest below? Have you measured the performance of
> that?
> > 
> > > 
> > > 
> > > Yes, clear is working now. I had previously tried the same but it did not
> show
> > > improvement. The change that helped is to check the size before clear. I
> have
> > > also added the new traces to the bug.
> > 
> > Thanks. Have you also measured the typical case (where we have a one or two
> > animations, and none is finished)? Since this is going to happen much more
> > frequently than the case where we have finished animations (e.g. for a 2
> second
> > animation at 60 frames per second, we'll have a 119 calls where we have no
> > finished animation, and one call with a finished animation), a small
> regression
> > for this case could outweigh a large improvement in the case where we do
have
> > finished animations.
> 
> Thanks Ajuma. Thats a very good point you make there. We do need to check for
> cases
> where the animation does not finish at all. I can modify the layeranimation
test
> case
> in the bug to check that and add that trace.
> 
> As of now this change has 2 sections:
> 1. Reserving the vector (that will be done for all cases, even when not
> finsihed). So 
> I have to check the cost of that. Ideally it should not be huge.2
> 
> 2. Clearing the vector and adding the index to vector: But I think this cost
> will be 
> lesser than the cost of running the for loop multiple times to check for the
> group ID.
> 
> I will check and confirm regarding the same.

Hi Ajuma,

I ran layeranimation example (present in the bug) by adding the infinite
condition
to all the animations. Ran it for 30 seconds where the animations are never
finished,
it just enters and exits the function. The average is 0.026 with or without the
patch.

As i mentioned only the reserving the vector could have been the regression, as
clearing
 of vector will save the for loop execution completely when we check for
animation to be
 set with waiting for deletion. Since reserving vector is not costly there is no

regression seen.

Also you requested animation which runs for 2 seconds, that is already part of
the traces
that I added previously in the bug. The layeranimation.html already has 1
animation
which runs for 2 seconds and 1 other animation which runs for 3 seconds. There
was no 
regression found as mentioned in previous traces. Please let me know your
opinion. Thanks.

[ajuma, 2014-08-01 15:26:48]

lgtm with a couple nits:

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

https://codereview.chromium.org/429223002/diff/40001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:781: // animations below will be set
to waitingForDeletion in next
Nit: WaitingForDeletion

https://codereview.chromium.org/429223002/diff/40001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:792: // just need to traverse that
list.
Nit: This additional comment isn't needed, the name
'animations_with_same_group_id' should already make this clear :)

[shreyas.g, 2014-08-01 15:43:39]

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

https://codereview.chromium.org/429223002/diff/40001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:781: // animations below will be set
to waitingForDeletion in next
On 2014/08/01 15:26:47, ajuma wrote:
> Nit: WaitingForDeletion

Done.

https://codereview.chromium.org/429223002/diff/40001/cc/animation/layer_anima...
cc/animation/layer_animation_controller.cc:792: // just need to traverse that
list.
On 2014/08/01 15:26:47, ajuma wrote:
> Nit: This additional comment isn't needed, the name
> 'animations_with_same_group_id' should already make this clear :)

Done.

[shreyas.g, 2014-08-01 15:43:46]

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

[commit-bot: I haz the power, 2014-08-01 15:45:03]

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

[commit-bot: I haz the power, 2014-08-01 22:15:27]

Change committed as 287103