cc: Added invalidation frequency for picture pile.

This patch keeps track of the invalidation frequency of each of
the picture pile grid cells. When the invalidation goes over a
certain threshold (0.75) and the grid cell is further than
specified amount of pixels from the viewport (512), then the
cell is not re-recorded. For a cell that was previously skipped,
either frequency dropping below the threshold or it coming closer
than 512 pixels will cause it to re-record again.

BUG=254320

Review URL: https://codereview.chromium.org/106393003

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@239893 0039d316-1c4b-4281-b951-d872f2087c98

8 files changed, 232 insertions, 34 deletions

diff --git a/cc/layers/picture_layer.cc b/cc/layers/picture_layer.cc
index 03bf6f2..1415c80 100644
--- a/cc/layers/picture_layer.cc
+++ b/cc/layers/picture_layer.cc
@@ -116,6 +116,7 @@ bool PictureLayer::Update(ResourceUpdateQueue* queue,
                            contents_opaque(),
                            pile_invalidation_,
                            visible_layer_rect,
+                           update_source_frame_number_,
                            rendering_stats_instrumentation());
   last_updated_visible_content_rect_ = visible_content_rect();
 
diff --git a/cc/resources/picture_pile.cc b/cc/resources/picture_pile.cc
index 99d3eff..68d75d7 100644
--- a/cc/resources/picture_pile.cc
+++ b/cc/resources/picture_pile.cc
@@ -11,6 +11,7 @@
 #include "cc/base/region.h"
 #include "cc/debug/rendering_stats_instrumentation.h"
 #include "cc/resources/picture_pile_impl.h"
+#include "cc/resources/tile_priority.h"
 
 namespace {
 // Layout pixel buffer around the visible layer rect to record.  Any base
@@ -151,6 +152,7 @@ bool PicturePile::Update(
     bool contents_opaque,
     const Region& invalidation,
     gfx::Rect visible_layer_rect,
+    int frame_number,
     RenderingStatsInstrumentation* stats_instrumentation) {
   background_color_ = background_color;
   contents_opaque_ = contents_opaque;
@@ -175,7 +177,8 @@ bool PicturePile::Update(
       if (picture_it == picture_map_.end())
         continue;
 
-      invalidated = picture_it->second.Invalidate() || invalidated;
+      // Inform the grid cell that it has been invalidated in this frame.
+      invalidated = picture_it->second.Invalidate(frame_number) || invalidated;
     }
   }
 
@@ -186,8 +189,13 @@ bool PicturePile::Update(
   for (TilingData::Iterator it(&tiling_, interest_rect);
        it; ++it) {
     const PictureMapKey& key = it.index();
-    const PictureInfo& info = picture_map_[key];
-    if (!info.picture.get()) {
+    PictureInfo& info = picture_map_[key];
+
+    gfx::Rect rect = PaddedRect(key);
+    int distance_to_visible =
+        rect.ManhattanInternalDistance(visible_layer_rect);
+
+    if (info.NeedsRecording(frame_number, distance_to_visible)) {
       gfx::Rect tile = tiling_.TileBounds(key.first, key.second);
       invalid_tiles.push_back(tile);
     }
@@ -235,7 +243,7 @@ bool PicturePile::Update(
       gfx::Rect tile = PaddedRect(key);
       if (record_rect.Contains(tile)) {
         PictureInfo& info = picture_map_[key];
-        info.picture = picture;
+        info.SetPicture(picture);
       }
     }
   }
diff --git a/cc/resources/picture_pile.h b/cc/resources/picture_pile.h
index 90fc015..7860e7f 100644
--- a/cc/resources/picture_pile.h
+++ b/cc/resources/picture_pile.h
@@ -26,6 +26,7 @@ class CC_EXPORT PicturePile : public PicturePileBase {
       bool contents_opaque,
       const Region& invalidation,
       gfx::Rect visible_layer_rect,
+      int frame_number,
       RenderingStatsInstrumentation* stats_instrumentation);
 
   void set_num_raster_threads(int num_raster_threads) {
diff --git a/cc/resources/picture_pile_base.cc b/cc/resources/picture_pile_base.cc
index 5e38c04..7d60dca 100644
--- a/cc/resources/picture_pile_base.cc
+++ b/cc/resources/picture_pile_base.cc
@@ -25,6 +25,15 @@ const bool kDefaultClearCanvasSetting = false;
 #else
 const bool kDefaultClearCanvasSetting = true;
 #endif
+
+// Invalidation frequency settings. kInvalidationFrequencyThreshold is a value
+// between 0 and 1 meaning invalidation frequency between 0% and 100% that
+// indicates when to stop invalidating offscreen regions.
+// kFrequentInvalidationDistanceThreshold defines what it means to be
+// "offscreen" in terms of distance to visible in css pixels.
+const float kInvalidationFrequencyThreshold = 0.75f;
+const int kFrequentInvalidationDistanceThreshold = 512;
+
 }  // namespace
 
 namespace cc {
@@ -165,7 +174,7 @@ void PicturePileBase::UpdateRecordedRegion() {
   for (PictureMap::const_iterator it = picture_map_.begin();
        it != picture_map_.end();
        ++it) {
-    if (it->second.picture.get()) {
+    if (it->second.GetPicture()) {
       const PictureMapKey& key = it->first;
       recorded_region_.Union(tile_bounds(key.first, key.second));
     }
@@ -176,7 +185,7 @@ bool PicturePileBase::HasRecordingAt(int x, int y) {
   PictureMap::const_iterator found = picture_map_.find(PictureMapKey(x, y));
   if (found == picture_map_.end())
     return false;
-  return !!found->second.picture.get();
+  return !!found->second.GetPicture();
 }
 
 bool PicturePileBase::CanRaster(float contents_scale, gfx::Rect content_rect) {
@@ -210,7 +219,7 @@ scoped_ptr<base::Value> PicturePileBase::AsValue() const {
     if (map_iter == picture_map_.end())
       continue;
 
-    Picture* picture = map_iter->second.picture.get();
+    Picture* picture = map_iter->second.GetPicture();
     if (picture && (appended_pictures.count(picture) == 0)) {
       appended_pictures.insert(picture);
       pictures->Append(TracedValue::CreateIDRef(picture).release());
@@ -219,23 +228,61 @@ scoped_ptr<base::Value> PicturePileBase::AsValue() const {
   return pictures.PassAs<base::Value>();
 }
 
-PicturePileBase::PictureInfo::PictureInfo() {}
+PicturePileBase::PictureInfo::PictureInfo() : last_frame_number_(0) {}
 
 PicturePileBase::PictureInfo::~PictureInfo() {}
 
-bool PicturePileBase::PictureInfo::Invalidate() {
-  if (!picture.get())
-    return false;
-  picture = NULL;
-  return true;
+void PicturePileBase::PictureInfo::AdvanceInvalidationHistory(
+    int frame_number) {
+  DCHECK_GE(frame_number, last_frame_number_);
+  if (frame_number == last_frame_number_)
+    return;
+
+  invalidation_history_ <<= (frame_number - last_frame_number_);
+  last_frame_number_ = frame_number;
+}
+
+bool PicturePileBase::PictureInfo::Invalidate(int frame_number) {
+  AdvanceInvalidationHistory(frame_number);
+  invalidation_history_.set(0);
+
+  bool did_invalidate = !!picture_;
+  picture_ = NULL;
+  return did_invalidate;
+}
+
+bool PicturePileBase::PictureInfo::NeedsRecording(int frame_number,
+                                                  int distance_to_visible) {
+  AdvanceInvalidationHistory(frame_number);
+
+  // We only need recording if we don't have a picture. Furthermore, we only
+  // need a recording if we're within frequent invalidation distance threshold
+  // or the invalidation is not frequent enough (below invalidation frequency
+  // threshold).
+  return !picture_ &&
+         ((distance_to_visible <= kFrequentInvalidationDistanceThreshold) ||
+          (GetInvalidationFrequency() < kInvalidationFrequencyThreshold));
+}
+
+void PicturePileBase::PictureInfo::SetPicture(scoped_refptr<Picture> picture) {
+  picture_ = picture;
+}
+
+Picture* PicturePileBase::PictureInfo::GetPicture() const {
+  return picture_.get();
 }
 
 PicturePileBase::PictureInfo PicturePileBase::PictureInfo::CloneForThread(
     int thread_index) const {
   PictureInfo info = *this;
-  if (picture.get())
-    info.picture = picture->GetCloneForDrawingOnThread(thread_index);
+  if (picture_.get())
+    info.picture_ = picture_->GetCloneForDrawingOnThread(thread_index);
   return info;
 }
 
+float PicturePileBase::PictureInfo::GetInvalidationFrequency() const {
+  return invalidation_history_.count() /
+         static_cast<float>(INVALIDATION_FRAMES_TRACKED);
+}
+
 }  // namespace cc
diff --git a/cc/resources/picture_pile_base.h b/cc/resources/picture_pile_base.h
index 66a26e75..274c865 100644
--- a/cc/resources/picture_pile_base.h
+++ b/cc/resources/picture_pile_base.h
@@ -5,6 +5,7 @@
 #ifndef CC_RESOURCES_PICTURE_PILE_BASE_H_
 #define CC_RESOURCES_PICTURE_PILE_BASE_H_
 
+#include <bitset>
 #include <list>
 #include <utility>
 
@@ -50,14 +51,32 @@ class CC_EXPORT PicturePileBase : public base::RefCounted<PicturePileBase> {
   scoped_ptr<base::Value> AsValue() const;
 
  protected:
-  struct CC_EXPORT PictureInfo {
+  class CC_EXPORT PictureInfo {
+   public:
+    enum {
+      INVALIDATION_FRAMES_TRACKED = 32
+    };
+
     PictureInfo();
     ~PictureInfo();
 
-    bool Invalidate();
+    bool Invalidate(int frame_number);
+    bool NeedsRecording(int frame_number, int distance_to_visible);
     PictureInfo CloneForThread(int thread_index) const;
+    void SetPicture(scoped_refptr<Picture> picture);
+    Picture* GetPicture() const;
+
+    float GetInvalidationFrequencyForTesting() const {
+      return GetInvalidationFrequency();
+    }
+
+   private:
+    void AdvanceInvalidationHistory(int frame_number);
+    float GetInvalidationFrequency() const;
 
-    scoped_refptr<Picture> picture;
+    int last_frame_number_;
+    scoped_refptr<Picture> picture_;
+    std::bitset<INVALIDATION_FRAMES_TRACKED> invalidation_history_;
   };
 
   typedef std::pair<int, int> PictureMapKey;
diff --git a/cc/resources/picture_pile_impl.cc b/cc/resources/picture_pile_impl.cc
index 44a52b8..5522186 100644
--- a/cc/resources/picture_pile_impl.cc
+++ b/cc/resources/picture_pile_impl.cc
@@ -170,7 +170,8 @@ void PicturePileImpl::CoalesceRasters(gfx::Rect canvas_rect,
     if (map_iter == picture_map_.end())
       continue;
     PictureInfo& info = map_iter->second;
-    if (!info.picture.get())
+    Picture* picture = info.GetPicture();
+    if (!picture)
       continue;
 
     // This is intentionally *enclosed* rect, so that the clip is aligned on
@@ -182,13 +183,13 @@ void PicturePileImpl::CoalesceRasters(gfx::Rect canvas_rect,
     gfx::Rect content_clip =
         gfx::ScaleToEnclosedRect(chunk_rect, contents_scale);
     DCHECK(!content_clip.IsEmpty()) << "Layer rect: "
-                                    << info.picture->LayerRect().ToString()
+                                    << picture->LayerRect().ToString()
                                     << "Contents scale: " << contents_scale;
     content_clip.Intersect(canvas_rect);
 
-    PictureRegionMap::iterator it = results->find(info.picture.get());
+    PictureRegionMap::iterator it = results->find(picture);
     if (it == results->end()) {
-      Region& region = (*results)[info.picture.get()];
+      Region& region = (*results)[picture];
       region = content_rect;
       region.Subtract(content_clip);
       continue;
@@ -365,7 +366,7 @@ void PicturePileImpl::PixelRefIterator::AdvanceToTilePictureWithPixelRefs() {
     if (it == picture_pile_->picture_map_.end())
       continue;
 
-    const Picture* picture = it->second.picture.get();
+    const Picture* picture = it->second.GetPicture();
     if (!picture || (processed_pictures_.count(picture) != 0))
       continue;
 
@@ -382,7 +383,7 @@ void PicturePileImpl::DidBeginTracing() {
   for (PictureMap::iterator it = picture_map_.begin();
        it != picture_map_.end();
        ++it) {
-    Picture* picture = it->second.picture.get();
+    Picture* picture = it->second.GetPicture();
     if (picture && (processed_pictures.count(picture) == 0)) {
       picture->EmitTraceSnapshot();
       processed_pictures.insert(picture);
diff --git a/cc/resources/picture_pile_unittest.cc b/cc/resources/picture_pile_unittest.cc
index 0c9b2e1..91ec355 100644
--- a/cc/resources/picture_pile_unittest.cc
+++ b/cc/resources/picture_pile_unittest.cc
@@ -2,6 +2,9 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include <map>
+#include <utility>
+
 #include "cc/resources/picture_pile.h"
 #include "cc/test/fake_content_layer_client.h"
 #include "cc/test/fake_rendering_stats_instrumentation.h"
@@ -46,6 +49,7 @@ TEST(PicturePileTest, SmallInvalidateInflated) {
                false,
                gfx::Rect(layer_size),
                gfx::Rect(layer_size),
+               1,
                &stats_instrumentation);
 
   // Invalidate something inside a tile.
@@ -55,6 +59,7 @@ TEST(PicturePileTest, SmallInvalidateInflated) {
                false,
                invalidate_rect,
                gfx::Rect(layer_size),
+               2,
                &stats_instrumentation);
 
   EXPECT_EQ(1, pile->tiling().num_tiles_x());
@@ -63,9 +68,9 @@ TEST(PicturePileTest, SmallInvalidateInflated) {
   TestPicturePile::PictureInfo& picture_info =
       pile->picture_map().find(TestPicturePile::PictureMapKey(0, 0))->second;
   // We should have a picture.
-  EXPECT_TRUE(!!picture_info.picture.get());
-  gfx::Rect picture_rect =
-      gfx::ScaleToEnclosedRect(picture_info.picture->LayerRect(), min_scale);
+  EXPECT_TRUE(!!picture_info.GetPicture());
+  gfx::Rect picture_rect = gfx::ScaleToEnclosedRect(
+      picture_info.GetPicture()->LayerRect(), min_scale);
 
   // The the picture should be large enough that scaling it never makes a rect
   // smaller than 1 px wide or tall.
@@ -93,6 +98,7 @@ TEST(PicturePileTest, LargeInvalidateInflated) {
                false,
                gfx::Rect(layer_size),
                gfx::Rect(layer_size),
+               1,
                &stats_instrumentation);
 
   // Invalidate something inside a tile.
@@ -102,6 +108,7 @@ TEST(PicturePileTest, LargeInvalidateInflated) {
                false,
                invalidate_rect,
                gfx::Rect(layer_size),
+               2,
                &stats_instrumentation);
 
   EXPECT_EQ(1, pile->tiling().num_tiles_x());
@@ -109,11 +116,11 @@ TEST(PicturePileTest, LargeInvalidateInflated) {
 
   TestPicturePile::PictureInfo& picture_info =
       pile->picture_map().find(TestPicturePile::PictureMapKey(0, 0))->second;
-  EXPECT_TRUE(!!picture_info.picture.get());
+  EXPECT_TRUE(!!picture_info.GetPicture());
 
   int expected_inflation = pile->buffer_pixels();
 
-  scoped_refptr<Picture> base_picture = picture_info.picture;
+  Picture* base_picture = picture_info.GetPicture();
   gfx::Rect base_picture_rect(layer_size);
   base_picture_rect.Inset(-expected_inflation, -expected_inflation);
   EXPECT_EQ(base_picture_rect.ToString(),
@@ -143,12 +150,23 @@ TEST(PicturePileTest, InvalidateOnTileBoundaryInflated) {
   EXPECT_EQ(7, pile->buffer_pixels());
   EXPECT_EQ(7, pile->tiling().border_texels());
 
-  // Update the whole layer.
+  // Update the whole layer to create initial pictures.
+  pile->Update(&client,
+               background_color,
+               false,
+               gfx::Rect(layer_size),
+               gfx::Rect(layer_size),
+               0,
+               &stats_instrumentation);
+
+  // Invalidate everything again to have a non zero invalidation
+  // frequency.
   pile->Update(&client,
                background_color,
                false,
                gfx::Rect(layer_size),
                gfx::Rect(layer_size),
+               1,
                &stats_instrumentation);
 
   // Invalidate something just over a tile boundary by a single pixel.
@@ -163,6 +181,7 @@ TEST(PicturePileTest, InvalidateOnTileBoundaryInflated) {
                false,
                invalidate_rect,
                gfx::Rect(layer_size),
+               2,
                &stats_instrumentation);
 
   for (int i = 0; i < pile->tiling().num_tiles_x(); ++i) {
@@ -171,9 +190,111 @@ TEST(PicturePileTest, InvalidateOnTileBoundaryInflated) {
           pile->picture_map().find(
               TestPicturePile::PictureMapKey(i, j))->second;
 
-      // TODO(vmpstr): Fix this to check invalidation frequency instead
-      // of the picture, since we always have one picture per tile.
-      EXPECT_TRUE(!!picture_info.picture.get());
+      // Expect (1, 1) and (1, 0) to be invalidated once more
+      // than the rest of the tiles.
+      if (i == 1 && (j == 0 || j == 1)) {
+        EXPECT_FLOAT_EQ(
+            2.0f / TestPicturePile::PictureInfo::INVALIDATION_FRAMES_TRACKED,
+            picture_info.GetInvalidationFrequencyForTesting());
+      } else {
+        EXPECT_FLOAT_EQ(
+            1.0f / TestPicturePile::PictureInfo::INVALIDATION_FRAMES_TRACKED,
+            picture_info.GetInvalidationFrequencyForTesting());
+      }
+    }
+  }
+}
+
+TEST(PicturePileTest, StopRecordingOffscreenInvalidations) {
+  FakeContentLayerClient client;
+  FakeRenderingStatsInstrumentation stats_instrumentation;
+  scoped_refptr<TestPicturePile> pile = new TestPicturePile;
+  SkColor background_color = SK_ColorBLUE;
+
+  float min_scale = 0.125;
+  gfx::Size base_picture_size = pile->tiling().max_texture_size();
+
+  gfx::Size layer_size =
+      gfx::ToFlooredSize(gfx::ScaleSize(base_picture_size, 4.f));
+  pile->Resize(layer_size);
+  pile->SetTileGridSize(gfx::Size(1000, 1000));
+  pile->SetMinContentsScale(min_scale);
+
+  gfx::Rect viewport(0, 0, layer_size.width(), 1);
+
+  // Update the whole layer until the invalidation frequency is high.
+  int frame;
+  for (frame = 0; frame < 33; ++frame) {
+    pile->Update(&client,
+                 background_color,
+                 false,
+                 gfx::Rect(layer_size),
+                 viewport,
+                 frame,
+                 &stats_instrumentation);
+  }
+
+  // Make sure we have a high invalidation frequency.
+  for (int i = 0; i < pile->tiling().num_tiles_x(); ++i) {
+    for (int j = 0; j < pile->tiling().num_tiles_y(); ++j) {
+      TestPicturePile::PictureInfo& picture_info =
+          pile->picture_map().find(
+              TestPicturePile::PictureMapKey(i, j))->second;
+      EXPECT_FLOAT_EQ(1.0f, picture_info.GetInvalidationFrequencyForTesting())
+          << "i " << i << " j " << j;
+    }
+  }
+
+  // Update once more with a small viewport 0,0 layer_width by 1
+  pile->Update(&client,
+               background_color,
+               false,
+               gfx::Rect(layer_size),
+               viewport,
+               frame,
+               &stats_instrumentation);
+
+  for (int i = 0; i < pile->tiling().num_tiles_x(); ++i) {
+    for (int j = 0; j < pile->tiling().num_tiles_y(); ++j) {
+      TestPicturePile::PictureInfo& picture_info =
+          pile->picture_map().find(
+              TestPicturePile::PictureMapKey(i, j))->second;
+      EXPECT_FLOAT_EQ(1.0f, picture_info.GetInvalidationFrequencyForTesting());
+
+      // If the y far enough away we expect to find no picture (no re-recording
+      // happened). For close y, the picture should change.
+      if (j >= 2)
+        EXPECT_FALSE(picture_info.GetPicture()) << "i " << i << " j " << j;
+      else
+        EXPECT_TRUE(picture_info.GetPicture()) << "i " << i << " j " << j;
+    }
+  }
+
+  // Now update with no invalidation and full viewport
+  pile->Update(&client,
+               background_color,
+               false,
+               gfx::Rect(),
+               gfx::Rect(layer_size),
+               frame+1,
+               &stats_instrumentation);
+
+  for (int i = 0; i < pile->tiling().num_tiles_x(); ++i) {
+    for (int j = 0; j < pile->tiling().num_tiles_y(); ++j) {
+      TestPicturePile::PictureInfo& picture_info =
+          pile->picture_map().find(
+              TestPicturePile::PictureMapKey(i, j))->second;
+      // Expect the invalidation frequency to be less than 1, since we just
+      // updated with no invalidations.
+      float expected_frequency =
+          1.0f -
+          1.0f / TestPicturePile::PictureInfo::INVALIDATION_FRAMES_TRACKED;
+
+      EXPECT_FLOAT_EQ(expected_frequency,
+                      picture_info.GetInvalidationFrequencyForTesting());
+
+      // We expect that there are pictures everywhere now.
+      EXPECT_TRUE(picture_info.GetPicture()) << "i " << i << " j " << j;
     }
   }
 }
diff --git a/cc/test/fake_picture_pile_impl.cc b/cc/test/fake_picture_pile_impl.cc
index 88c7d38..bc751ed 100644
--- a/cc/test/fake_picture_pile_impl.cc
+++ b/cc/test/fake_picture_pile_impl.cc
@@ -78,7 +78,7 @@ void FakePicturePileImpl::AddRecordingAt(int x, int y) {
   scoped_refptr<Picture> picture(Picture::Create(bounds));
   picture->Record(&client_, tile_grid_info_);
   picture->GatherPixelRefs(tile_grid_info_);
-  picture_map_[std::pair<int, int>(x, y)].picture = picture;
+  picture_map_[std::pair<int, int>(x, y)].SetPicture(picture);
   EXPECT_TRUE(HasRecordingAt(x, y));
 
   UpdateRecordedRegion();