cc: Only create tiling eviction iterators as they are required.

cc/layers/picture_layer_impl.h

 // 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.
 
 #ifndef CC_LAYERS_PICTURE_LAYER_IMPL_H_
 #define CC_LAYERS_PICTURE_LAYER_IMPL_H_
 
 #include <string>
 #include <vector>
 
@@ skipping 62 matching lines @@
 
     Tile* operator*();
     const Tile* operator*() const;
     LayerEvictionTileIterator& operator++();
     operator bool() const;
 
    private:
     void AdvanceToNextIterator();
     bool IsCorrectType(
         PictureLayerTiling::TilingEvictionTileIterator* it) const;
+    void EnsureCurrentIteratorCreated();
 
     std::vector<PictureLayerTiling::TilingEvictionTileIterator> iterators_;

[reveman, 2014/07/26 00:30:49]

is there no compile time limit to the number of iterators that we have to
maintain at the same time? I'm just curious as it would be nice to remove this
vector in the future...

[vmpstr, 2014/07/28 15:06:16]

I think it might make sense to limit this at some point, but currently I don't
think there's anything there. In theory we could have as many tilings as we
want.

[reveman, 2014/07/28 16:19:33]

What if we passed that stage information to the TilingEvictionTileIterator?
Would that not eliminate the need for having more than one iterator instance
instantiated at the same time?

[vmpstr, 2014/07/28 18:15:08]

I feel that it's a bit of a misuse of the iterator interface. Yes, we could have
something along the lines of TilingEvictionTileIterator(...,
TilePriority::PriorityBin start_with_this_priority), but again I'm not sure
that's simpler.

My issue here is that it's awkward to impose this type of functionality on a
tiling iterator without knowing its implementation. To me, it's akin to having a
stl containers having ::begin(int first_element_index). It's fine to do for a
std::vector, but for std::list or std::map it's kind of awkward, since every
time you create the iterator you would have to iterate over the first
|first_element_index| elements.

The intent of this patch is to only create an iterator when it is visited for
the first time. It is possible that eliminating the vectors (both iterators_ and
the one added in this patch) is another way to optimize this. I think that it is
outside of the scope of this particular patch.

Do you believe that eliminating the iterators_ vector to begin with is a better
way to optimize the iterator than this patch? If so, then we need a different
patch instead of shoehorning it in here.

[reveman, 2014/07/28 19:06:14]

I'm rather thinking of this as different collections to iterate instead of
different start indexes. It could be different kind of iterators (ie.
Tiling{Eventually,Soon,..}EvictionTileIterator) but I assumed that would be less
convenient. The underlying data type would of course have to be adjusted to
efficiently iterate these different collections independently rather than one
large collection of tiles. Not sure what that would involve. Maybe it's very
hard..
I suspect it might be a better solution but I don't know yet. Was hoping we
could explore the option before moving forward with this patch. A separate patch
is probably better if we decide that the vectors can be eliminated.

+    std::vector<PictureLayerTiling*> tilings_;

[reveman, 2014/07/26 00:30:49]

do we really need this vector? is there some way we can just use
layer_->tilings_->tiling_at() directly instead of having to put the tiling in a
vector first?

[vmpstr, 2014/07/28 15:06:16]

It's possible, but I think this is a simpler solution. The idea is that we
process tilings in a certain order of scales and we process the same order
several times (eventually, soon, now). Right now we have that order codified in
the constructor with several loops. We can eliminate this by spreading the logic
of what is the next tiling to operator++, but it I think it will definitely add
some code complexity (and it's unclear how much savings we would get). Note that
iterators_ vector would have to stay anyway.

How about we keep it this way and possibly revisit? 

[reveman, 2014/07/28 16:19:34]

I don't like that we're building a reliance on vectors in these iterators. I'd
like to explore the possibility of removing them if possible first as I think
that would not only make the code more efficient but also easier to understand.
I assume that this is harder than I think but I'd like to understand why it's
hard before we move forward with this current approach.

[vmpstr, 2014/07/28 18:15:08]

The only real problem is that we don't know how many tilings we need to process
at compile time and that we need to process them several times (assuming we
don't have TilingEvictionTileIterators that can start an an aribtrary bin, since
I don't think that would be efficient without relying on one particular
implementation of tiling eviction)

[reveman, 2014/07/28 19:06:14]

The key as you mentioned is to have a TilingEvictionTileIterator for each bin. I
don't understand the last part of your comment. "efficient without relying on
one particular implementation", what do you mean by this?

[vmpstr, 2014/07/28 19:27:04]

I just meant that if we have a PriorityBin passed in to the tiling iterator, we
limit the implementations of that iterator (for instance, the current approach
of putting everything in a vector and sorting it doesn't work, since we'd have
to iterate each time we create an iterator for some bin in the middle).

In order to do this efficiently, the tiling would have to keep about 4 vectors
(eventually bin, soon bin, now bin with required for activation, and now bin
with no requirement for activation). So overall it would have this impact:

- No vectors in layer eviction iterators.
- More vectors in tiling.
- More involved logic in tiling eviction iterator (to iterate multiple vectors
instead of one; or would this type mean iterate _only_ this bin?).
- More involved logic in layer eviction iterator operator++ (to determine the
next tiling index).
- Savings from the fact that we won't create iterators until required (same
impact as this patch)
- Possible savings from sorting smaller vectors, although that might be offset
by the fact that we would now have to push tiles into one of four vectors
instead of one.
- Possible savings from eliminating vectors in layer eviction (not sure where,
tile manager queues?).

Is that the same impact that you predict? If so, I'll write a patch that changes
this. For the record, I'm still a bit unclear what the problem is with vectors.
Is it just the heap allocations that you want to avoid?

     size_t iterator_index_;
     TilePriority::PriorityBin iteration_stage_;
     bool required_for_activation_;
-
     PictureLayerImpl* layer_;
+    TreePriority tree_priority_;
   };
 
   static scoped_ptr<PictureLayerImpl> Create(LayerTreeImpl* tree_impl, int id) {
     return make_scoped_ptr(new PictureLayerImpl(tree_impl, id));
   }
   virtual ~PictureLayerImpl();
 
   // LayerImpl overrides.
   virtual const char* LayerTypeAsString() const OVERRIDE;
   virtual scoped_ptr<LayerImpl> CreateLayerImpl(LayerTreeImpl* tree_impl)
@@ skipping 117 matching lines @@
   gfx::Size viewport_size_for_tile_priority_;
   gfx::Transform screen_space_transform_for_tile_priority_;
 
   friend class PictureLayer;
   DISALLOW_COPY_AND_ASSIGN(PictureLayerImpl);
 };
 
 }  // namespace cc
 
 #endif  // CC_LAYERS_PICTURE_LAYER_IMPL_H_