cc: Remove vectors from tiling eviction tile iterator.

cc/layers/picture_layer_impl.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/layers/picture_layer_impl.h"
 
 #include <algorithm>
 #include <limits>
 
 #include "base/time/time.h"
@@ skipping 1538 matching lines @@
   DCHECK(*this);
 
   IteratorType index = stages_[current_stage_].iterator_type;
   DCHECK(iterators_[index]);
   DCHECK(iterators_[index].get_type() == stages_[current_stage_].tile_type);
 
   return *iterators_[index];
 }
 
 PictureLayerImpl::LayerEvictionTileIterator::LayerEvictionTileIterator()
-    : iterator_index_(0),
+    : tiling_index_(0),
       iteration_stage_(TilePriority::EVENTUALLY),
+      range_index_(0),
       required_for_activation_(false),
-      layer_(NULL) {}
+      tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
+      layer_(NULL) {
+}
 
 PictureLayerImpl::LayerEvictionTileIterator::LayerEvictionTileIterator(
     PictureLayerImpl* layer,
     TreePriority tree_priority)
-    : iterator_index_(0),
+    : tiling_index_(0),
       iteration_stage_(TilePriority::EVENTUALLY),
+      range_index_(0),
       required_for_activation_(false),
+      tree_priority_(tree_priority),
       layer_(layer) {
   // Early out if the layer has no tilings.
   // TODO(vmpstr): Once tile priorities are determined by the iterators, ensure
   // that layers that don't have valid tile priorities have lowest priorities so
   // they evict their tiles first (crbug.com/381704)
   if (!layer_->tilings_ || !layer_->tilings_->num_tilings())
     return;
 
+  ConstructRanges();
+  if (!CurrentTilingIndexInRange())
+    AdvanceRange();
+
+  // There must be at least one valid range.
+  DCHECK(CurrentTilingIndexInRange());
+
+  iterator_ = PictureLayerTiling::TilingEvictionTileIterator(
+      layer_->tilings_->tiling_at(tiling_index_),
+      tree_priority,
+      iteration_stage_,
+      required_for_activation_);
+
+  if (!iterator_)
+    AdvanceToNextIterator();
+}
+
+PictureLayerImpl::LayerEvictionTileIterator::~LayerEvictionTileIterator() {
+}
+
+Tile* PictureLayerImpl::LayerEvictionTileIterator::operator*() {
+  DCHECK(*this);
+  return *iterator_;
+}
+
+const Tile* PictureLayerImpl::LayerEvictionTileIterator::operator*() const {
+  DCHECK(*this);
+  return *iterator_;
+}
+
+PictureLayerImpl::LayerEvictionTileIterator&
+PictureLayerImpl::LayerEvictionTileIterator::
+operator++() {
+  DCHECK(*this);
+  ++iterator_;
+
+  if (!iterator_)
+    AdvanceToNextIterator();
+  return *this;
+}
+
+void PictureLayerImpl::LayerEvictionTileIterator::ConstructRanges() {
+  // TODO(vmpstr): See if these can be looked up from the tiling set.
   size_t high_res_tiling_index = layer_->tilings_->num_tilings();
   size_t low_res_tiling_index = layer_->tilings_->num_tilings();
   for (size_t i = 0; i < layer_->tilings_->num_tilings(); ++i) {
     PictureLayerTiling* tiling = layer_->tilings_->tiling_at(i);
     if (tiling->resolution() == HIGH_RESOLUTION)
       high_res_tiling_index = i;
     else if (tiling->resolution() == LOW_RESOLUTION)
       low_res_tiling_index = i;
   }
 
-  iterators_.reserve(layer_->tilings_->num_tilings());
+  DCHECK_LT(high_res_tiling_index, layer_->tilings_->num_tilings());
 
-  // Higher resolution non-ideal goes first.
-  for (size_t i = 0; i < high_res_tiling_index; ++i) {
-    iterators_.push_back(PictureLayerTiling::TilingEvictionTileIterator(
-        layer_->tilings_->tiling_at(i), tree_priority));
+  // First iterate from highest resolution to the HIGH_RES tiling.
+  ranges_[HIGHER_THAN_HIGH_RES].start_index = 0;
+  ranges_[HIGHER_THAN_HIGH_RES].one_past_end_index = high_res_tiling_index;
+
+  // Next, iterate from the lowest resolution to the LOW_RES tiling. Note that
+  // if we don't have a low res tiling, then the start index will be the same as
+  // one past the end, which means it is an empty range.
+  ranges_[LOWER_THAN_LOW_RES].start_index = layer_->tilings_->num_tilings() - 1;
+  ranges_[LOWER_THAN_LOW_RES].one_past_end_index = low_res_tiling_index;
+
+  // Next, iterate from just after the LOW_RES tiling to the HIGH_RES tiling.
+  // Note that if there is no low res tiling, then start index will be the last
+  // tiling.
+  ranges_[BETWEEN_HIGH_AND_LOW_RES].start_index = low_res_tiling_index - 1;
+  ranges_[BETWEEN_HIGH_AND_LOW_RES].one_past_end_index = high_res_tiling_index;
+
+  if (low_res_tiling_index < layer_->tilings_->num_tilings()) {
+    // Next, iterate a range of one element: LOW_RES tiling.
+    ranges_[LOW_RES].start_index = low_res_tiling_index;
+    ranges_[LOW_RES].one_past_end_index = low_res_tiling_index + 1;
+  } else {
+    // If there is no LOW_RES tiling, then set an empty range.
+    ranges_[LOW_RES].start_index = 0;
+    ranges_[LOW_RES].one_past_end_index = 0;
   }
 
-  // Lower resolution non-ideal goes next.
-  for (size_t i = layer_->tilings_->num_tilings() - 1;
-       i > high_res_tiling_index;
-       --i) {
-    PictureLayerTiling* tiling = layer_->tilings_->tiling_at(i);
-    if (tiling->resolution() == LOW_RESOLUTION)
-      continue;
+  // Finally, iterate a range of one element: HIGH_RES tiling.
+  ranges_[HIGH_RES].start_index = high_res_tiling_index;
+  ranges_[HIGH_RES].one_past_end_index = high_res_tiling_index + 1;
 
-    iterators_.push_back(
-        PictureLayerTiling::TilingEvictionTileIterator(tiling, tree_priority));
+  range_index_ = HIGHER_THAN_HIGH_RES;
+  tiling_index_ = ranges_[range_index_].start_index;
+}
+
+bool PictureLayerImpl::LayerEvictionTileIterator::CurrentTilingIndexInRange() {
+  TilingIterationRange& range = ranges_[range_index_];
+  if (range.start_index < range.one_past_end_index) {
+    return tiling_index_ >= range.start_index &&
+           tiling_index_ < range.one_past_end_index;
+  } else if (range.start_index > range.one_past_end_index) {
+    return tiling_index_ <= range.start_index &&
+           tiling_index_ > range.one_past_end_index;
   }
+  // Empty range means we're not in range.
+  return false;
+}

[reveman, 2014/07/29 21:41:32]

I think I'd like to see this function removed and the check always be as simple
as "current_tiling_ < current_tiling_range_.count".

[vmpstr, 2014/07/30 00:18:51]

I'm still a little bit confused about how we would represent reverse ranges. As
well, I think accessing the tiling is far more clear if we use "tiling_index_"
as the index instead of "tiling_index_ + current_range_.start_index".

[reveman, 2014/07/30 16:06:47]

See my comment about RangeOffsetToTilingSetIndex below.

[vmpstr, 2014/07/30 20:06:39]

Acknowledged.

 
-  // Now, put the low res tiling if we have one.
-  if (low_res_tiling_index < layer_->tilings_->num_tilings()) {
-    iterators_.push_back(PictureLayerTiling::TilingEvictionTileIterator(
-        layer_->tilings_->tiling_at(low_res_tiling_index), tree_priority));
-  }
+void PictureLayerImpl::LayerEvictionTileIterator::AdvanceToNextIterator() {
+  DCHECK(!iterator_);
+  while (!iterator_) {
+    bool success = AdvanceTiling();
+    if (!success)
+      success = AdvanceRange();
+    if (!success)
+      success = AdvanceStage();
+    if (!success)
+      break;

[reveman, 2014/07/29 21:41:32]

hm, doesn't this need to be a nested loop? ie. we need to keep advancing the
range until we find one with tilings and same for advancing the stage..

[vmpstr, 2014/07/30 00:18:51]

AdvanceTiling will advance to the next tiling if one is available and return
false otherwise
AdvanceRange will advance to the next non empty range (always) and return false
if it looped around to the beginning. False here kind of means that it "failed"
to find a non-empty range and had to look through the ranges again.
AdvanceStage will advance the stage if one is available and return false
otherwise.

So if we get below this line, we can get a new iterator for a new spot that we
haven't been before. If that iterator doesn't produce any tiles we start again.

[reveman, 2014/07/31 15:32:47]

AdvanceTiling doesn't advance until it finds non-empty iterator. To be
consistent, AdvanceRange should not advance until it finds a non-empty range.

[vmpstr, 2014/08/01 06:04:48]

Well, this is kind of a weird one. Here's my reasoning:

Advance tiling advances to the next valid tiling (ie tiling exists, no mention
of iterators). When it can no longer do that, it returns false.

Stage is similar, it advances to the next valid stage (no mention of iterators).
When it can no longer do that, it returns false.

Advance range advances to the next valid range (ie, range exists.. in this case
ranges that are empty don't exist). When it can no longer do that.. oh wait, it
can always find a range because it loops back, so we return false if it looped
back.

Yes, the semantics of advance range are subtly different from stage and tiling,
but I think making it only advance once as you suggest and treat empty ranges
etc makes this function more awkward. For instance, we can return false to
indicate that we went to an empty range or that we looped around. Suppose we
return false when we enter an empty range, then we don't really know when to
advance the stage (ie we don't know when we loop).

The other case is less awkward and ends up with the following:

bool success;
...
// handle tilings

// handle ranges
if (!success) {
  do {
    success = AdvanceRange();
  } while (success && CurrentRange().IsEmpty());
}

// handle stages
if (!success)
  ...

or something similar to that.

That's OK, I guess. If you insist I can make it that, but please consider the
current solution as I prefer it.

[reveman, 2014/08/01 17:54:46]

I feel like there's a lack of uniformity in current patch. To make it easier to
understand what these AdvanceToNext*() functions do, I'd like to be able to
define the behavior of AdvanceToNext*() in a way that is independent of what's
being advanced. ie. "bool AdvanceToNextX()"; Advance X and return false when X
cannot be advanced any further. AdvanceToNextX() might have to call
AdvanceToNextY() but that's a detail that the caller of AdvanceToNextX() should
not have to be aware of. This is basically how it would work if iterators were
used.

I was thinking we could do something similar to this:

opertor++() {
  ++current_iterator;
  while (!current_iterator) {
    if (!AdvanceToNextTiling())
      break;

    current_iterator = Iterator(...);
  }
}

bool AdvanceToNextTiling() {
  ++current_tiling_;
  while (current_tiling_ == current_tiling_range().end) {
    if (!AdvanceToNextTilingRangeType())
      return false;

    current_tiling_ = current_tiling_range().start;
  }
  return true;
}

bool AdvanceToNextTilingRangeType() {
  switch (current_tiling_range_type_) {
    case HIGHER_THAN_HIGH_RES:
    case HIGH_RES:
    case BETWEEN_HIGH_AND_LOW_RES:
    case LOW_RES:
      current_tiling_range_type_ = static_cast<TilingRangeType>(
          current_tiling_range_type_ + 1);
      return true;
    case LOWER_THAN_LOW_RES:
      if (!AdvanceToNextStage())
        return false;

      current_tiling_range_type_ = HIGHER_THAN_HIGH_RES;
      return true;
  }
  NOTREACHED();
  return false;
}

bool AdvanceToNextStage() {
  switch (current_stage_) {
    case EVENTUALLY:
    case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
    case SOON:
    case SOON_AND_REQUIRED_FOR_ACTIVATION:
    case NOW:
      current_stage_ = static_cast<Stage>(current_stage_ + 1);
      return true;
    case NOW_AND_REQUIRED_FOR_ACTIVATION:
      return false;
  }
  NOTREACHED();
  return false;
}

and ctor could then be reduced to something like this:

current_stage_ = EVENTUALLY;
current_tiling_range_type_ = HIGHER_THAN_HIGH_RES;
current_tiling_ = current_tiling_range().start - 1;
do {
  if (!AdvanceToNextTiling())
    break;

  current_iterator = Iterator(...);
} while (!current_iterator);

Wdyt?

[vmpstr, 2014/08/01 19:39:50]

Done.

 
-  // Finally, put the high res tiling if we have one.
-  if (high_res_tiling_index < layer_->tilings_->num_tilings()) {
-    iterators_.push_back(PictureLayerTiling::TilingEvictionTileIterator(
-        layer_->tilings_->tiling_at(high_res_tiling_index), tree_priority));
-  }
-
-  DCHECK_GT(iterators_.size(), 0u);
-
-  if (!iterators_[iterator_index_] ||
-      !IsCorrectType(&iterators_[iterator_index_])) {
-    AdvanceToNextIterator();
+    iterator_ = PictureLayerTiling::TilingEvictionTileIterator(
+        layer_->tilings_->tiling_at(tiling_index_),
+        tree_priority_,
+        iteration_stage_,
+        required_for_activation_);
   }
 }
 
-PictureLayerImpl::LayerEvictionTileIterator::~LayerEvictionTileIterator() {}
+bool PictureLayerImpl::LayerEvictionTileIterator::AdvanceTiling() {
+  // We can't advance the tiling if we're already not in range.
+  if (!CurrentTilingIndexInRange())

[reveman, 2014/07/29 21:41:33]

Seems odd that we check this both before and after we increment the index. Would
setting the current_range_ to { 0, 0 } and current_tiling_ to -1 in the ctor
help?

[vmpstr, 2014/07/30 00:18:52]

I don't think this was required. I replaced it with a DCHECK.

[reveman, 2014/07/31 15:32:47]

Acknowledged.

+    return false;
 
-Tile* PictureLayerImpl::LayerEvictionTileIterator::operator*() {
-  DCHECK(*this);
-  return *iterators_[iterator_index_];
+  int direction = ranges_[range_index_].start_index <
+                          ranges_[range_index_].one_past_end_index
+                      ? 1
+                      : -1;

[reveman, 2014/07/29 21:41:32]

I think it would be cleaner to adjust the index based on direction using an
utility function with a switch statement right before calling
layer_->tilings_->tiling_at(). ie.
layer_->tilings_->tiling_at(RangeOffsetToTilingSetIndex(current_tiling_,
current_range_))

[vmpstr, 2014/07/30 00:18:52]

I'm not sure I understand what you mean. Would RangeOffsetToTilingSetIndex
update the index? Is that instead of this function? Can you elaborate a little
bit more?

[reveman, 2014/07/30 16:06:48]

RangeOffsetToTilingSetIndex would simply take an offset in the current range and
a range type and return a tiling set index. All the logic needed to handle
reverse direction would be easy to implement in that function. All other code
can ignore the detail that iterating through a range can be done in different
directions. We'd always start at 0 and increment the offset until we reach
range.count. This would eliminate the need for CurrentTilingIndexInRange() as
that would always be as simple as "current_offset_in_range < range_.count". And
RangeOffsetToTilingSetIndex would look something like this:

{
  switch (type) {
   case HIGHER_THAN_HIGH_RES:
   case LOW_RES:
   case HIGH_RES:
     return range_.offset + offset_in_range;
   case BETWEEN_HIGH_AND_LOW_RES:
   case LOWER_THAN_LOW_RES:
     // Note: walk these tilings in reverse order.
     // From low res to hi res.
     return range_.offset + (range_.count - offset_in_range - 1);
  }
  NOTREACHED();
  return 0;
}

[vmpstr, 2014/07/30 20:06:38]

I've done this. To be honest, I find this more confusing the previous patch set.
Maybe your patch to move this into tiling set will make this better.

[reveman, 2014/07/31 15:32:47]

Let's see what it looks like after rebase onto my patch.

[vmpstr, 2014/08/01 06:04:48]

Done.

+  tiling_index_ += direction;
+
+  return CurrentTilingIndexInRange();
 }
 
-const Tile* PictureLayerImpl::LayerEvictionTileIterator::operator*() const {
-  DCHECK(*this);
-  return *iterators_[iterator_index_];
+bool PictureLayerImpl::LayerEvictionTileIterator::AdvanceRange() {
+  DCHECK(!CurrentTilingIndexInRange());
+  bool wrapped_around = false;

[reveman, 2014/07/29 21:41:32]

I think this function would be a bit cleaner with a switch statement.

[vmpstr, 2014/07/30 00:18:52]

switch (range_index_) {
 case HIGHER_THAN_HIGH_RES:
   range_index_ = LOWER_THAN_LOW_RES;
   break;
 case LOWER_THAN_LOW_RES:
   range_index_ = BETWEEN_HIGH_AND_LOW_RES;
   break;
 ...
}

Is that what you mean? I changed it to that since I agree that we shouldn't rely
on the enum ordering.

[reveman, 2014/07/31 15:32:47]

Yup, thanks!

+  while (!CurrentTilingIndexInRange()) {
+    range_index_ = static_cast<RangeType>((range_index_ + 1) % NUM_RANGE_TYPES);
+    tiling_index_ = ranges_[range_index_].start_index;
+    if (range_index_ == 0)
+      wrapped_around = true;
+  }
+  // If we wrapped around the ranges, we need to indicate that we should advance
+  // the stage.
+  return !wrapped_around;
 }
 
-PictureLayerImpl::LayerEvictionTileIterator&
-PictureLayerImpl::LayerEvictionTileIterator::
-operator++() {
-  DCHECK(*this);
-  ++iterators_[iterator_index_];
-  if (!iterators_[iterator_index_] ||
-      !IsCorrectType(&iterators_[iterator_index_])) {
-    AdvanceToNextIterator();
+bool PictureLayerImpl::LayerEvictionTileIterator::AdvanceStage() {

[reveman, 2014/07/29 21:41:33]

Think this function would also be cleaner with a switch statement. It's hard to
understand the different stages we go through as it is now.

[vmpstr, 2014/07/30 00:18:52]

switch over bins? That would end up looking like this:

switch (bin) {
 case EVENTUALLY:
   if (!required_for_activation) {
     required_for_activation = true;
   } else {
     bin = SOON;
     required_for_activation = false;
   }
   break;
 case SOON:
   if (!required_for_activation) {
     required_for_activation = true;
   } else {
     bin = NOW;
     required_for_activation = false;
   }
   break;
   if (!required_for_activation) {
     required_for_activation = true;
   } else {
     return false;
   }
   break;
}
return true;

To me, that's less clear. It's basically repeating exactly the same thing I have
except iteration_stage_ = ... line is more explicit (and it's not immediately
obvious that it's the only difference between each case). Would it be better to
put a comment over the line saying that it goes through bins in EVENTUALLY,
SOON, NOW order? Alternatively, I can put a comment right at the start of the
function enumerating the order of all the stages. Wdyt?

[reveman, 2014/07/30 16:06:47]

Why don't we add an enum for all stages? ie. EVENTUALLY,
EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION, SOON...

[vmpstr, 2014/07/30 20:06:38]

I don't like that. Either this enum would have to live on the tiling iterator,
or we would need a couple of functions to extract activation vs bin back. I
added a comment here to describe the stages, and I added a switch for the bin
advancement. Let me know if this is acceptable.

[reveman, 2014/07/31 15:32:47]

Enum living here and two utility functions that return tile-type and
required-for-activation when passed this enum sgtm. It would remove all the need
for comments in this function.

[vmpstr, 2014/08/01 06:04:48]

Done.

+  // If we're NOW and required_for_activation, then this was the last pass
+  // through the iterators.
+  if (iteration_stage_ == TilePriority::NOW && required_for_activation_)
+    return false;
+
+  if (!required_for_activation_) {
+    required_for_activation_ = true;
+  } else {
+    required_for_activation_ = false;
+    iteration_stage_ =
+        static_cast<TilePriority::PriorityBin>(iteration_stage_ - 1);
   }
-  return *this;
-}
-
-void PictureLayerImpl::LayerEvictionTileIterator::AdvanceToNextIterator() {
-  ++iterator_index_;
-
-  while (true) {
-    while (iterator_index_ < iterators_.size()) {
-      if (iterators_[iterator_index_] &&
-          IsCorrectType(&iterators_[iterator_index_])) {
-        return;
-      }
-      ++iterator_index_;
-    }
-
-    // If we're NOW and required_for_activation, then this was the last pass
-    // through the iterators.
-    if (iteration_stage_ == TilePriority::NOW && required_for_activation_)
-      break;
-
-    if (!required_for_activation_) {
-      required_for_activation_ = true;
-    } else {
-      required_for_activation_ = false;
-      iteration_stage_ =
-          static_cast<TilePriority::PriorityBin>(iteration_stage_ - 1);
-    }
-    iterator_index_ = 0;
-  }
+  return true;
 }
 
 PictureLayerImpl::LayerEvictionTileIterator::operator bool() const {
-  return iterator_index_ < iterators_.size();
-}
-
-bool PictureLayerImpl::LayerEvictionTileIterator::IsCorrectType(
-    PictureLayerTiling::TilingEvictionTileIterator* it) const {
-  return it->get_type() == iteration_stage_ &&
-         (**it)->required_for_activation() == required_for_activation_;
+  return iterator_;

[reveman, 2014/07/29 21:41:32]

!!iterator_?

[vmpstr, 2014/07/30 00:18:51]

Done.

 }
 
 }  // namespace cc