Reduced iterations for group-id check in MarkAnimationsForDeletions

cc/animation/layer_animation_controller.cc

 // Copyright 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "cc/animation/layer_animation_controller.h"
 
 #include <algorithm>
 
 #include "cc/animation/animation.h"
 #include "cc/animation/animation_delegate.h"
@@ skipping 706 matching lines @@
         animations_[i]->run_state() != Animation::Aborted &&
         animations_[i]->run_state() != Animation::WaitingForDeletion)
       animations_[i]->SetRunState(Animation::Finished, monotonic_time);
   }
 }
 
 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
   // we don't have an events vector, we must ensure that non-aborted animations
   // have received a finished event before marking them for deletion.
   for (size_t i = 0; i < animations_.size(); i++) {
     int group_id = animations_[i]->group();
     if (animations_[i]->run_state() == Animation::Aborted) {
       if (events && !animations_[i]->is_impl_only()) {
         AnimationEvent aborted_event(AnimationEvent::Aborted,
@@ skipping 12 matching lines @@
     bool all_anims_with_same_id_are_finished = false;
 
     // Since deleting an animation on the main thread leads to its deletion
     // on the impl thread, we only mark a Finished main thread animation for
     // deletion once it has received a Finished event from the impl thread.
     bool animation_i_will_send_or_has_received_finish_event =
         events || animations_[i]->received_finished_event();
     // If an animation is finished, and not already marked for deletion,
     // 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;
     }
   }
   if (marked_animations_for_deletions)
     NotifyObserversAnimationWaitingForDeletion();
 }
 
 static bool IsWaitingForDeletion(Animation* animation) {
   return animation->run_state() == Animation::WaitingForDeletion;
@@ skipping 180 matching lines @@
         value_observers_);
     LayerAnimationValueObserver* obs;
     while ((obs = it.GetNext()) != NULL)
       if (obs->IsActive())
         return true;
   }
   return false;
 }
 
 }  // namespace cc