Improve DamageTracker performance.

cc/trees/damage_tracker.cc

 // Copyright 2011 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/trees/damage_tracker.h"
 
 #include <algorithm>
 
 #include "cc/base/math_util.h"
 #include "cc/layers/heads_up_display_layer_impl.h"
 #include "cc/layers/layer_impl.h"
 #include "cc/layers/render_surface_impl.h"
 #include "cc/output/filter_operations.h"
 #include "cc/trees/layer_tree_host_common.h"
 #include "cc/trees/layer_tree_impl.h"
 
 namespace cc {
 
 scoped_ptr<DamageTracker> DamageTracker::Create() {
   return make_scoped_ptr(new DamageTracker());
 }
 
-DamageTracker::DamageTracker()
-    : current_rect_history_(new RectMap),
-      next_rect_history_(new RectMap) {}
+DamageTracker::DamageTracker() {}
 
 DamageTracker::~DamageTracker() {}
 
 static inline void ExpandRectWithFilters(
     gfx::RectF* rect, const FilterOperations& filters) {
   int top, right, bottom, left;
   filters.GetOutsets(&top, &right, &bottom, &left);
   rect->Inset(-left, -top, -right, -bottom);
 }
 
@@ skipping 62 matching lines @@
   // - If a layer/surface property changed, the old bounds and new bounds may
   //   overlap... i.e. some of the exposed region may not actually be exposing
   //   anything. But this does not artificially inflate the damage rect. If the
   //   layer changed, its entire old bounds would always need to be redrawn,
   //   regardless of how much it overlaps with the layer's new bounds, which
   //   also need to be entirely redrawn.
   //
   // - See comments in the rest of the code to see what exactly is considered a
   //   "change" in a layer/surface.
   //
   // - To correctly manage exposed rects, two RectMaps are maintained:

[shawnsingh, 2013/11/21 09:56:03]

"two RectMaps" -- this line of comment should also be updated.

[ostap, 2013/11/21 17:06:23]

Done.

   //
-  //      1. The "current" map contains all the layer bounds that contributed to
+  //      1. All existing from the previous fram regions in map history are

[shawnsingh, 2013/11/21 09:56:03]

Some typos and clarifications - let's say "All existing rects from the previous
frame are marked as not updated"

[ostap, 2013/11/21 17:06:23]

Done.

+  //         marked not updated.
+  //      2. The map contains all the layer bounds that contributed to
   //         the previous frame (even outside the previous damaged area). If a
   //         layer changes or does not exist anymore, those regions are then
   //         exposed and damage the target surface. As the algorithm progresses,
-  //         entries are removed from the map until it has only leftover layers
-  //         that no longer exist.
+  //         entries are updated in the map until only leftover layers
+  //         that no longer exist stay marked not updated.
   //
-  //      2. The "next" map starts out empty, and as the algorithm progresses,
-  //         every layer/surface that contributes to the surface is added to the
-  //         map.
-  //
-  //      3. After the damage rect is computed, the two maps are swapped, so
-  //         that the damage tracker is ready for the next frame.
+  //      3. After the damage rect is computed, the leftover not marked regions
+  //         in a map are used to compute are damaged by deleted layers and
+  //         erased from map.
   //
 
+  PrepareRectHistoryForUpdate();
   // These functions cannot be bypassed with early-exits, even if we know what
   // the damage will be for this frame, because we need to update the damage
   // tracker state to correctly track the next frame.
   gfx::RectF damage_from_active_layers =
       TrackDamageFromActiveLayers(layer_list, target_surface_layer_id);
   gfx::RectF damage_from_surface_mask =
       TrackDamageFromSurfaceMask(target_surface_mask_layer);
   gfx::RectF damage_from_leftover_rects = TrackDamageFromLeftoverRects();
 
   gfx::RectF damage_rect_for_this_update;
@@ skipping 12 matching lines @@
       // those here to limit damage.
       damage_rect_for_this_update = target_surface_content_rect;
     } else if (filters.HasFilterThatMovesPixels()) {
       ExpandRectWithFilters(&damage_rect_for_this_update, filters);
     }
   }
 
   // Damage accumulates until we are notified that we actually did draw on that
   // frame.
   current_damage_rect_.Union(damage_rect_for_this_update);
-
-  // The next history map becomes the current map for the next frame. Note this
-  // must happen every frame to correctly track changes, even if damage
-  // accumulates over multiple frames before actually being drawn.
-  swap(current_rect_history_, next_rect_history_);
 }
 
-gfx::RectF DamageTracker::RemoveRectFromCurrentFrame(int layer_id,
-                                                     bool* layer_is_new) {
-  RectMap::iterator iter = current_rect_history_->find(layer_id);
-  *layer_is_new = iter == current_rect_history_->end();
+DamageTracker::RectMapData& DamageTracker::RectDataForLayer(
+                              int layer_id, bool* layer_is_new) {
+  RectMap::iterator iter = rect_history_.find(layer_id);
+  *layer_is_new = iter == rect_history_.end();

[shawnsingh, 2013/11/21 09:56:03]

For clarity here let's use parentheses around the boolean condition.

[ostap, 2013/11/21 17:06:23]

Done.

   if (*layer_is_new)
-    return gfx::RectF();
+    return rect_history_[layer_id]; // force element creation
 
-  gfx::RectF ret = iter->second;
-  current_rect_history_->erase(iter);
-  return ret;
-}
-
-void DamageTracker::SaveRectForNextFrame(int layer_id,
-                                         const gfx::RectF& target_space_rect) {
-  // This layer should not yet exist in next frame's history.
-  DCHECK_GT(layer_id, 0);
-  DCHECK(next_rect_history_->find(layer_id) == next_rect_history_->end());
-  (*next_rect_history_)[layer_id] = target_space_rect;
+  return iter->second;
 }
 
 gfx::RectF DamageTracker::TrackDamageFromActiveLayers(
     const LayerImplList& layer_list,
     int target_surface_layer_id) {
   gfx::RectF damage_rect = gfx::RectF();
 
   for (size_t layer_index = 0; layer_index < layer_list.size(); ++layer_index) {
     // Visit layers in back-to-front order.
     LayerImpl* layer = layer_list[layer_index];
@@ skipping 26 matching lines @@
   // expected to be a common case.
   if (target_surface_mask_layer->LayerPropertyChanged() ||
       !target_surface_mask_layer->update_rect().IsEmpty()) {
     damage_rect = gfx::RectF(gfx::PointF(),
                              target_surface_mask_layer->bounds());
   }
 
   return damage_rect;
 }
 
+void DamageTracker::PrepareRectHistoryForUpdate() {

[shawnsingh, 2013/11/21 09:56:03]

Let's use an integer RectMapData::mailboxId_  instead of a boolean
RectMapData.updated_  - that way, we can avoid this entire loop that exists
simply to invalidate each rect.  Instead, incrementing the mailbox ID would be
equivalent to automatically dirtying all entries in the map.

+  for (RectMap::iterator it = rect_history_.begin();
+       it != rect_history_.end();
+       ++it) {
+    it->second.updated_ = false;
+  }
+}
+
 gfx::RectF DamageTracker::TrackDamageFromLeftoverRects() {
   // After computing damage for all active layers, any leftover items in the
   // current rect history correspond to layers/surfaces that no longer exist.
   // So, these regions are now exposed on the target surface.
 
   gfx::RectF damage_rect = gfx::RectF();
 
-  for (RectMap::iterator it = current_rect_history_->begin();
-       it != current_rect_history_->end();
-       ++it)
-    damage_rect.Union(it->second);
+  for (RectMap::iterator it = rect_history_.begin();
+       it != rect_history_.end(); ) {
 
-  current_rect_history_->clear();
+    if (it->second.updated_)

[danakj, 2013/11/21 00:13:40]

{} here, since else has them

[ostap, 2013/11/21 17:06:23]

Done.

+      ++it;
+    else {
+      damage_rect.Union(it->second.rect_);
+      RectMap::iterator erase_it = it;
+      ++it;
+      rect_history_.erase(erase_it);

[shawnsingh, 2013/11/21 09:56:03]

I don't know about base::HashMap, but for std:: containers, we cannot continue
to use an iterator after adding/removing elements of a list.  There is a good
chance we will want to change container types some time for crbug.com/230050 -
probably a std::vector, so unfortunately I think this code needs to change.

Right now I can't think of how to implement this more robustly without adding
more queries to the container.  Let's discuss ideas if you have any =)

[ostap, 2013/11/21 17:06:23]

Done.

+    }
+  }
 
   return damage_rect;
 }
 
 void DamageTracker::ExtendDamageForLayer(LayerImpl* layer,
                                          gfx::RectF* target_damage_rect) {
   // There are two ways that a layer can damage a region of the target surface:
   //   1. Property change (e.g. opacity, position, transforms):
   //        - the entire region of the layer itself damages the surface.
   //        - the old layer region also damages the surface, because this region
   //          is now exposed.
   //        - note that in many cases the old and new layer rects may overlap,
   //          which is fine.
   //
   //   2. Repaint/update: If a region of the layer that was repainted/updated,
   //      that region damages the surface.
   //
   // Property changes take priority over update rects.
   //
   // This method is called when we want to consider how a layer contributes to
   // its target RenderSurface, even if that layer owns the target RenderSurface
   // itself. To consider how a layer's target surface contributes to the
   // ancestor surface, ExtendDamageForRenderSurface() must be called instead.
 
   bool layer_is_new = false;
-  gfx::RectF old_rect_in_target_space =
-      RemoveRectFromCurrentFrame(layer->id(), &layer_is_new);
+  RectMapData& data = RectDataForLayer(layer->id(), &layer_is_new);
+  gfx::RectF old_rect_in_target_space = data.rect_;
 
   gfx::RectF rect_in_target_space = MathUtil::MapClippedRect(
       layer->draw_transform(),
       gfx::RectF(gfx::PointF(), layer->content_bounds()));
-  SaveRectForNextFrame(layer->id(), rect_in_target_space);
+  data.Update(rect_in_target_space);
 
   if (layer_is_new || layer->LayerPropertyChanged()) {
     // If a layer is new or has changed, then its entire layer rect affects the
     // target surface.
     target_damage_rect->Union(rect_in_target_space);
 
     // The layer's old region is now exposed on the target surface, too.
     // Note old_rect_in_target_space is already in target space.
     target_damage_rect->Union(old_rect_in_target_space);
   } else if (!layer->update_rect().IsEmpty()) {
@@ skipping 20 matching lines @@
   //        - just like layers, both the old surface rect and new surface rect
   //          will damage the target surface in this case.
   //
   //   2. Damage rect: This surface may have been damaged by its own layer_list
   //      as well, and that damage should propagate to the target surface.
   //
 
   RenderSurfaceImpl* render_surface = layer->render_surface();
 
   bool surface_is_new = false;
-  gfx::RectF old_surface_rect = RemoveRectFromCurrentFrame(layer->id(),
-                                                           &surface_is_new);
+  RectMapData& data = RectDataForLayer(layer->id(), &surface_is_new);
+  gfx::RectF old_surface_rect = data.rect_;
 
   // The drawableContextRect() already includes the replica if it exists.
   gfx::RectF surface_rect_in_target_space =
       render_surface->DrawableContentRect();
-  SaveRectForNextFrame(layer->id(), surface_rect_in_target_space);
+  data.Update(surface_rect_in_target_space);
 
   gfx::RectF damage_rect_in_local_space;
   if (surface_is_new || render_surface->SurfacePropertyChanged()) {
     // The entire surface contributes damage.
     damage_rect_in_local_space = render_surface->content_rect();
 
     // The surface's old region is now exposed on the target surface, too.
     target_damage_rect->Union(old_surface_rect);
   } else {
     // Only the surface's damage_rect will damage the target surface.
@@ skipping 16 matching lines @@
           replica_draw_transform, damage_rect_in_local_space));
     }
   }
 
   // If there was damage on the replica's mask, then the target surface receives
   // that damage as well.
   if (layer->replica_layer() && layer->replica_layer()->mask_layer()) {
     LayerImpl* replica_mask_layer = layer->replica_layer()->mask_layer();
 
     bool replica_is_new = false;
-    RemoveRectFromCurrentFrame(replica_mask_layer->id(), &replica_is_new);
+    RectMapData& data = RectDataForLayer(replica_mask_layer->id(),
+                              &replica_is_new);

[danakj, 2013/11/21 00:13:40]

indenting off, git cl format please

[ostap, 2013/11/21 17:06:23]

Done.

 
     const gfx::Transform& replica_draw_transform =
         render_surface->replica_draw_transform();
     gfx::RectF replica_mask_layer_rect = MathUtil::MapClippedRect(
         replica_draw_transform,
         gfx::RectF(gfx::PointF(), replica_mask_layer->bounds()));
-    SaveRectForNextFrame(replica_mask_layer->id(), replica_mask_layer_rect);
+    data.Update(replica_mask_layer_rect);
 
     // In the current implementation, a change in the replica mask damages the
     // entire replica region.
     if (replica_is_new ||
         replica_mask_layer->LayerPropertyChanged() ||
         !replica_mask_layer->update_rect().IsEmpty())
       target_damage_rect->Union(replica_mask_layer_rect);
   }
 
   // If the layer has a background filter, this may cause pixels in our surface
   // to be expanded, so we will need to expand any damage at or below this
   // layer. We expand the damage from this layer too, as we need to readback
   // those pixels from the surface with only the contents of layers below this
   // one in them. This means we need to redraw any pixels in the surface being
   // used for the blur in this layer this frame.
   if (layer->background_filters().HasFilterThatMovesPixels()) {
     ExpandDamageRectInsideRectWithFilters(target_damage_rect,
                                           surface_rect_in_target_space,
                                           layer->background_filters());
   }
 }
 
 }  // namespace cc