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

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

Since we potentially evict tiles from all tilings, we need to ensure
that we don't create all of the tiling iterators if that is not
required. This is because tiling eviction tile iterators are not
cheap to create.

The idea is to keep a full ordering of _tilings_ instead of tiling
iterators and only create the iterator as we visit a tiling for which
an iterator has not yet been created.

Performance data:
Before:
layer_eviction_tile_iterator_construct:
0_0_100x100= 13791.8828125 runs/s
5000_0_100x100= 12871.0869140625 runs/s
9999_0_100x100= 13924.6796875 runs/s

layer_eviction_tile_iterator_construct_and_iterate:
32_100x100= 13579.04296875 runs/s
32_500x500= 13694.36328125 runs/s
64_100x100= 13655.9853515625 runs/s
64_500x500= 13705.3330078125 runs/s

After:
layer_eviction_tile_iterator_construct:
0_0_100x100= 50127.99609375 runs/s (+260%)
5000_0_100x100= 28462.0546875 runs/s (+121%)
9999_0_100x100= 30606.740234375 runs/s (+120%)

layer_eviction_tile_iterator_construct_and_iterate:
32_100x100= 47513.9296875 runs/s (+250%)
32_500x500= 48186.38671875 runs/s (+252%)
64_100x100= 46927.79296875 runs/s (+244%)
64_500x500= 46660.77734375 runs/s (+240%)

R=reveman

[vmpstr, 2014-07-25 23:52:02]

PTAL. Note that a similar change to the raster tile iterator makes little
difference in perf (tiling raster tile iterators are much cheaper to create).

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

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl.h
File cc/layers/picture_layer_impl.h (right):

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl.h:85:
std::vector<PictureLayerTiling::TilingEvictionTileIterator> iterators_;
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...

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl.h:86: std::vector<PictureLayerTiling*> tilings_;
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]

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl.h
File cc/layers/picture_layer_impl.h (right):

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl.h:85:
std::vector<PictureLayerTiling::TilingEvictionTileIterator> iterators_;
On 2014/07/26 00:30:49, reveman wrote:
> 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...

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.

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl.h:86: std::vector<PictureLayerTiling*> tilings_;
On 2014/07/26 00:30:49, reveman wrote:
> 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?

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]

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl.h
File cc/layers/picture_layer_impl.h (right):

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl.h:85:
std::vector<PictureLayerTiling::TilingEvictionTileIterator> iterators_;
On 2014/07/28 15:06:16, vmpstr wrote:
> On 2014/07/26 00:30:49, reveman wrote:
> > 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...
> 
> 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.

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?

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl.h:86: std::vector<PictureLayerTiling*> tilings_;
On 2014/07/28 15:06:16, vmpstr wrote:
> On 2014/07/26 00:30:49, reveman wrote:
> > 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?
> 
> 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? 

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:09]

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl.h
File cc/layers/picture_layer_impl.h (right):

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl.h:85:
std::vector<PictureLayerTiling::TilingEvictionTileIterator> iterators_;
On 2014/07/28 16:19:33, reveman wrote:
> On 2014/07/28 15:06:16, vmpstr wrote:
> > On 2014/07/26 00:30:49, reveman wrote:
> > > 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...
> > 
> > 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.
> 
> 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?

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.

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl.h:86: std::vector<PictureLayerTiling*> tilings_;
On 2014/07/28 16:19:34, reveman wrote:
> On 2014/07/28 15:06:16, vmpstr wrote:
> > On 2014/07/26 00:30:49, reveman wrote:
> > > 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?
> > 
> > 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? 
> 
> 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.

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]

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl.h
File cc/layers/picture_layer_impl.h (right):

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl.h:85:
std::vector<PictureLayerTiling::TilingEvictionTileIterator> iterators_;
On 2014/07/28 18:15:08, vmpstr wrote:
> On 2014/07/28 16:19:33, reveman wrote:
> > On 2014/07/28 15:06:16, vmpstr wrote:
> > > On 2014/07/26 00:30:49, reveman wrote:
> > > > 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...
> > > 
> > > 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.
> > 
> > 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?
> 
> 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.

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..

> 
> 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.

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.

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl.h:86: std::vector<PictureLayerTiling*> tilings_;
On 2014/07/28 18:15:08, vmpstr wrote:
> On 2014/07/28 16:19:34, reveman wrote:
> > On 2014/07/28 15:06:16, vmpstr wrote:
> > > On 2014/07/26 00:30:49, reveman wrote:
> > > > 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?
> > > 
> > > 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? 
> > 
> > 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.
> 
> 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)

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:05]

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl.h
File cc/layers/picture_layer_impl.h (right):

https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl.h:86: std::vector<PictureLayerTiling*> tilings_;
On 2014/07/28 19:06:14, reveman wrote:
> On 2014/07/28 18:15:08, vmpstr wrote:
> > On 2014/07/28 16:19:34, reveman wrote:
> > > On 2014/07/28 15:06:16, vmpstr wrote:
> > > > On 2014/07/26 00:30:49, reveman wrote:
> > > > > 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?
> > > > 
> > > > 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? 
> > > 
> > > 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.
> > 
> > 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)
> 
> 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?

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?

[reveman, 2014-07-28 20:03:57]

On 2014/07/28 19:27:05, vmpstr wrote:
>
https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl.h
> File cc/layers/picture_layer_impl.h (right):
> 
>
https://codereview.chromium.org/416403007/diff/1/cc/layers/picture_layer_impl...
> cc/layers/picture_layer_impl.h:86: std::vector<PictureLayerTiling*> tilings_;
> On 2014/07/28 19:06:14, reveman wrote:
> > On 2014/07/28 18:15:08, vmpstr wrote:
> > > On 2014/07/28 16:19:34, reveman wrote:
> > > > On 2014/07/28 15:06:16, vmpstr wrote:
> > > > > On 2014/07/26 00:30:49, reveman wrote:
> > > > > > 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?
> > > > > 
> > > > > 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? 
> > > > 
> > > > 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.
> > > 
> > > 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)
> > 
> > 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?
> 
> 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.

But smaller vectors, right? Which would also mean more efficient sorting.

> - More involved logic in tiling eviction iterator (to iterate multiple vectors
> instead of one; or would this type mean iterate _only_ this bin?).

We'd create an iterator only for a specific bin. I don't think there should be
any added logic.

> - More involved logic in layer eviction iterator operator++ (to determine the
> next tiling index).

Would the logic really be more involved? Is it not just about moving it from the
ctor in form of building a vector to the operator++ in form of instantiating a
new tiling iterator.

> - Savings from the fact that we won't create iterators until required (same
> impact as this patch)

Correct.

> - 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.

Not convinced that pushing tiles into 4 different vectors has any additional
cost. Btw, 4 different vectors would potentially allow you to lazy update them
separately instead of all at the same time..

> - 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?

I think avoiding heap allocations and reducing the space complexity of these
iterators are worthwhile on its own. However, the primary reason would be that I
find it a cleaner way to achieve the optimization your looking for. If you don't
agree, let's chat offline and try to figure out what the best solution is.

[vmpstr, 2014-07-28 20:25:01]

> > - No vectors in layer eviction iterators.
> > - More vectors in tiling.
> 
> But smaller vectors, right? Which would also mean more efficient sorting.

Yeah, the sum of all the elements in the four vectors would equal to the current
size of the one vector.

> 
> > - More involved logic in tiling eviction iterator (to iterate multiple
vectors
> > instead of one; or would this type mean iterate _only_ this bin?).
> 
> We'd create an iterator only for a specific bin. I don't think there should be
> any added logic.

If it's just one bin, then I agree. The comment was for if we want to iterate
starting from a bin onward.

> 
> > - More involved logic in layer eviction iterator operator++ (to determine
the
> > next tiling index).
> 
> Would the logic really be more involved? Is it not just about moving it from
the
> ctor in form of building a vector to the operator++ in form of instantiating a
> new tiling iterator.

Finding the next tiling would add some complexity... Right now we have a couple
of for loops in the constructor, namely:

  // Higher resolution non-ideal goes first.
  for (size_t i = 0; i < high_res_tiling_index; ++i) 
    tilings_.push_back(layer_->tilings_->tiling_at(i));

  // 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;

    tilings_.push_back(tiling);
  }

  // Now, put the low res tiling if we have one.
  if (low_res_tiling_index < layer_->tilings_->num_tilings())
    tilings_.push_back(layer_->tilings_->tiling_at(low_res_tiling_index));

  // Finally, put the high res tiling if we have one.
  if (high_res_tiling_index < layer_->tilings_->num_tilings())
    tilings_.push_back(layer_->tilings_->tiling_at(high_res_tiling_index));

with operator++ being something along the lines of:

index = (index + 1) % tilings_.size();
next_tiling = tilings_[index];

but lacking "yield", the code would end up being something along the lines of
the following:

operator++:
 next_index = GetNextIndex();
 next_tiling = tiling_->tilings_->tiling_at(next_index);

GetNextIndex:
 while true:
  switch(which_way_are_we_going)
   case HIGHER_THAN_HIGH_RES:
     ++next_index;
   case LOWER_THAN_HIGH_RES:
     --next_index;
     // Skip low res in this mode.
     if (next_index == low_res_index)
       --next_index;
   case LOW_RES:
     next_index = low_res_index;
   case HIGH_RES: 
     next_index = high_res_index;
  if (next_index is outside of [0, num_tilings))
    which_way_are_we_going = (which_way_are_we_going + 1) %
number_of_ways_to_go;
    // Reset next_index so that all modes start from here.
    next_index = high_res;
  break;
return next_index;
 
Granted, that's just what's floating in my head right now, so the actual code
might end up looking nicer/different. But out of the two options, vector seems
cleaner to me.

> 
> > - Savings from the fact that we won't create iterators until required (same
> > impact as this patch)
> 
> Correct.
> 
> > - 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.
> 
> Not convinced that pushing tiles into 4 different vectors has any additional
> cost. Btw, 4 different vectors would potentially allow you to lazy update them
> separately instead of all at the same time..

Yes this would provide the same benefits as prioritized tile set in terms of
lazy sort/smaller vectors. My main concern is that this cements the fact that
we're going to be using vectors and sorting them as a way of getting eviction
tiles. It might not be a bad thing, but the fact that we're picking an
implementation and optimizing it at this point seems premature.

> 
> > - 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?
> 
> I think avoiding heap allocations and reducing the space complexity of these
> iterators are worthwhile on its own. However, the primary reason would be that
I
> find it a cleaner way to achieve the optimization your looking for. If you
don't
> agree, let's chat offline and try to figure out what the best solution is.

We can chat offline if you'd prefer. I have a doctor's appointment soon so
tomorrow might work best.

[reveman, 2014-07-28 20:48:50]

On 2014/07/28 20:25:01, vmpstr wrote:
> > > - No vectors in layer eviction iterators.
> > > - More vectors in tiling.
> > 
> > But smaller vectors, right? Which would also mean more efficient sorting.
> 
> Yeah, the sum of all the elements in the four vectors would equal to the
current
> size of the one vector.
> 
> > 
> > > - More involved logic in tiling eviction iterator (to iterate multiple
> vectors
> > > instead of one; or would this type mean iterate _only_ this bin?).
> > 
> > We'd create an iterator only for a specific bin. I don't think there should
be
> > any added logic.
> 
> If it's just one bin, then I agree. The comment was for if we want to iterate
> starting from a bin onward.
> 
> > 
> > > - More involved logic in layer eviction iterator operator++ (to determine
> the
> > > next tiling index).
> > 
> > Would the logic really be more involved? Is it not just about moving it from
> the
> > ctor in form of building a vector to the operator++ in form of instantiating
a
> > new tiling iterator.
> 
> Finding the next tiling would add some complexity... Right now we have a
couple
> of for loops in the constructor, namely:
> 
>   // Higher resolution non-ideal goes first.
>   for (size_t i = 0; i < high_res_tiling_index; ++i) 
>     tilings_.push_back(layer_->tilings_->tiling_at(i));
> 
>   // 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;
> 
>     tilings_.push_back(tiling);
>   }
> 
>   // Now, put the low res tiling if we have one.
>   if (low_res_tiling_index < layer_->tilings_->num_tilings())
>     tilings_.push_back(layer_->tilings_->tiling_at(low_res_tiling_index));
> 
>   // Finally, put the high res tiling if we have one.
>   if (high_res_tiling_index < layer_->tilings_->num_tilings())
>     tilings_.push_back(layer_->tilings_->tiling_at(high_res_tiling_index));
> 
> with operator++ being something along the lines of:
> 
> index = (index + 1) % tilings_.size();
> next_tiling = tilings_[index];
> 
> but lacking "yield", the code would end up being something along the lines of
> the following:
> 
> operator++:
>  next_index = GetNextIndex();
>  next_tiling = tiling_->tilings_->tiling_at(next_index);
> 
> GetNextIndex:
>  while true:
>   switch(which_way_are_we_going)
>    case HIGHER_THAN_HIGH_RES:
>      ++next_index;
>    case LOWER_THAN_HIGH_RES:
>      --next_index;
>      // Skip low res in this mode.
>      if (next_index == low_res_index)
>        --next_index;
>    case LOW_RES:
>      next_index = low_res_index;
>    case HIGH_RES: 
>      next_index = high_res_index;
>   if (next_index is outside of [0, num_tilings))
>     which_way_are_we_going = (which_way_are_we_going + 1) %
> number_of_ways_to_go;
>     // Reset next_index so that all modes start from here.
>     next_index = high_res;
>   break;
> return next_index;
>  
> Granted, that's just what's floating in my head right now, so the actual code
> might end up looking nicer/different. But out of the two options, vector seems
> cleaner to me.

Ok, let's see what it looks like and if we can't make nice and easy to
understand. If it's too ugly the vectors might still be the way to go for now.

> 
> > 
> > > - Savings from the fact that we won't create iterators until required
(same
> > > impact as this patch)
> > 
> > Correct.
> > 
> > > - 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.
> > 
> > Not convinced that pushing tiles into 4 different vectors has any additional
> > cost. Btw, 4 different vectors would potentially allow you to lazy update
them
> > separately instead of all at the same time..
> 
> Yes this would provide the same benefits as prioritized tile set in terms of
> lazy sort/smaller vectors. My main concern is that this cements the fact that
> we're going to be using vectors and sorting them as a way of getting eviction
> tiles. It might not be a bad thing, but the fact that we're picking an
> implementation and optimizing it at this point seems premature.

I don't think it does. At least not any more than the current code. We're just
asking to iterate smaller collections of tiles from of the tiling.

> 
> > 
> > > - 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?
> > 
> > I think avoiding heap allocations and reducing the space complexity of these
> > iterators are worthwhile on its own. However, the primary reason would be
that
> I
> > find it a cleaner way to achieve the optimization your looking for. If you
> don't
> > agree, let's chat offline and try to figure out what the best solution is.
> 
> We can chat offline if you'd prefer. I have a doctor's appointment soon so
> tomorrow might work best.

Sounds good. Just let me know when is a good time.

[vmpstr, 2014-07-28 23:35:46]

This is kind of what I ended up with: https://codereview.chromium.org/428533008/
Note that I wouldn't be comfortable landing that, since I find that code more
unreadable. Let me know if there's some fundamental thing that I might have
misunderstood about what you meant. What I mean to say that we can change some
loops to do {} whiles, do some cosmetic changes, etc, but if the overall code
for determining which tiling is next to evict is remains this complicated, then
I'm not sure I can land it.