Reduced iterations for group-id check in MarkAnimationsForDeletions

cc/animation/layer_animation_controller.cc

Index: cc/animation/layer_animation_controller.cc
diff --git a/cc/animation/layer_animation_controller.cc b/cc/animation/layer_animation_controller.cc
index c942b02f9fd06de8a4ed81fac7dbe78f32cfcdd7..8c0b0683c9f47b2461ba85dff1adba29c1568e1c 100644
--- a/cc/animation/layer_animation_controller.cc
+++ b/cc/animation/layer_animation_controller.cc
@@ -724,6 +724,9 @@ void LayerAnimationController::MarkAnimationsForDeletion(
     base::TimeTicks monotonic_time,
     AnimationEventsVector* events) {
   bool marked_animations_for_deletions = false;
+  std::vector<size_t> animations_with_same_group_id;
+  size_t animations_with_same_group_id_count_;
+  bool animations_with_same_group_id_reserved = false;
 
   // Non-aborted animations are marked for deletion after a corresponding
   // AnimationEvent::Finished event is sent or received. This means that if
@@ -757,41 +760,65 @@ void LayerAnimationController::MarkAnimationsForDeletion(
     // find out if all other animations in the same group are also finished.
     if (animations_[i]->run_state() == Animation::Finished &&
         animation_i_will_send_or_has_received_finish_event) {

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

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:52:59]

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]

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:04]

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. 

+      // Reset the count of marked animations in animations_with_same_group_id.
+      // This is done to avoid the usage of vector.clear() method
+      // which is a costly operation.
+      animations_with_same_group_id_count_ = 0;
       all_anims_with_same_id_are_finished = true;
       for (size_t j = 0; j < animations_.size(); ++j) {
         bool animation_j_will_send_or_has_received_finish_event =
             events || animations_[j]->received_finished_event();
-        if (group_id == animations_[j]->group() &&
-            (!animations_[j]->is_finished() ||
-             (animations_[j]->run_state() == Animation::Finished &&
-              !animation_j_will_send_or_has_received_finish_event))) {
-          all_anims_with_same_id_are_finished = false;
-          break;
+        if (group_id == animations_[j]->group()) {
+          if (!animations_[j]->is_finished() ||
+              (animations_[j]->run_state() == Animation::Finished &&
+               !animation_j_will_send_or_has_received_finish_event)) {
+            all_anims_with_same_id_are_finished = false;
+            break;
+          } else if (j >= i &&
+                     animations_[j]->run_state() != Animation::Aborted) {
+            // Mark down the animations which belong to the same group
+            // and is not yet aborted. If this current iteration finds that all
+            // animations with same ID are finished, then the marked
+            // animations below will be set to waitingForDeletion in next
+            // iteration.
+            animations_with_same_group_id.push_back(j);
+            animations_with_same_group_id_count_++;
+            // The animation list belonging to same group needs to be only
+            // reserved in case atleast one other animation has the same ID
+            // and is not aborted yet. Once reserved, it can be used till the
+            // function exits. This avoids reserving in cases no other animation
+            // is marked in current iteration.
+            if (!animations_with_same_group_id_reserved) {
+              animations_with_same_group_id_reserved = true;
+              animations_with_same_group_id.reserve(animations_.size());
+            }
+          }
         }
       }
     }
     if (all_anims_with_same_id_are_finished) {
       // We now need to remove all animations with the same group id as
       // group_id (and send along animation finished notifications, if
-      // necessary).
-      for (size_t j = i; j < animations_.size(); j++) {
-        if (animations_[j]->group() == group_id &&
-            animations_[j]->run_state() != Animation::Aborted) {
+      // necessary). Since the list is already maintained in anims_same_group
+      // just need to traverse that list.
+      for (size_t j = 0; j < animations_with_same_group_id_count_; j++) {
+        size_t animation_index = animations_with_same_group_id[j];
           if (events) {
-            AnimationEvent finished_event(AnimationEvent::Finished,
-                                          id_,
-                                          animations_[j]->group(),
-                                          animations_[j]->target_property(),
-                                          monotonic_time);
-            finished_event.is_impl_only = animations_[j]->is_impl_only();
+            AnimationEvent finished_event(
+                AnimationEvent::Finished,
+                id_,
+                animations_[animation_index]->group(),
+                animations_[animation_index]->target_property(),
+                monotonic_time);
+            finished_event.is_impl_only =
+                animations_[animation_index]->is_impl_only();
             if (finished_event.is_impl_only)
               NotifyAnimationFinished(finished_event);
             else
               events->push_back(finished_event);
           }
-          animations_[j]->SetRunState(Animation::WaitingForDeletion,
-                                      monotonic_time);
-        }
+          animations_[animation_index]->SetRunState(
+              Animation::WaitingForDeletion, monotonic_time);
       }
       marked_animations_for_deletions = true;
     }