multibuffer: Evict lower blocks first after inserting multiple blocks

multibuffer: Evict lower blocks first after inserting multiple blocks

When seeking, the change in reader position can cause multiple "present" blocks
to transition from pinned to unpinned state, and thus enter the LRU all at
once.  These blocks should then be evicted (by Pop()) in the
lowest-position-first order.  Issuing the Insert() calls in this order
guarantees that.

For implementation convenience, this also reverses the order of Remove()
calls.  It is assumed Remove() order is not relevant for performance as
these calls end up erasing from an std::list and std::map anyway.

BUG=650201
TEST=media_blink_unittests --gtest_filter=MultiBuffer*:Multibuffer*

[wdzierzanowski, 2016-09-23 07:35:02]

wdzierzanowski@opera.com changed reviewers:
+ hubbe@chromium.org

[wdzierzanowski, 2016-09-23 07:35:03]

hubbe, found this when working on the integration of the multibuffer in Opera. I
think it could benefit you guys too, PTAL.

[hubbe, 2016-09-23 17:24:45]

On 2016/09/23 07:35:03, wdzierzanowski wrote:
> hubbe, found this when working on the integration of the multibuffer in Opera.
I
> think it could benefit you guys too, PTAL.

I'd like to understand the implications better.

I originally did the move-to-LRU in reverse intentionally so that seeking to the
beginning would remain fast, however, I did not do any research into alternative
strategies to see if they would be more efficient. Partially because I it was an
initial implementation and pretty much guaranteed to be better than the old
buffering code, and partially because the blocks I really care about are
supposed to be pinned. This is also why I decided to use an LRU, which is a
pretty terrible caching strategy. If we really want to optimize the order in
which blocks are freed, the right thing to do is probably to get rid of the LRU
completely and replace it with something that understands the access pattern and
frees blocks based on how likely they are to be used again.

Perhaps we should be doing something like:

if (behind all readers AND not first range of blocks) {
  free from front to back
} else {
  free from back to front
}

Basically we need some sort of benchmark that we can optimize against to figure
these things out.

[wdzierzanowski, 2016-09-23 21:34:43]

On 2016/09/23 17:24:45, hubbe wrote:
> On 2016/09/23 07:35:03, wdzierzanowski wrote:
> > hubbe, found this when working on the integration of the multibuffer in
Opera.
> I
> > think it could benefit you guys too, PTAL.
> 
> I'd like to understand the implications better.
> 

OK, let me try to shed some light with the help of some images. Imagine playing
a file for a while and then seeking forwards.

This shows the current eviction order (the green bars are the "present" blocks):
http://pasteboard.co/6H74RxXQq.png

This is how it looks like with this CL: http://pasteboard.co/6H83AjEie.png

Notice how in the former case the blocks are evicted in the MRU order. I assumed
this wasn't intentional in a cache with the LRU strategy. But you're saying this
assumption was wrong?

> I originally did the move-to-LRU in reverse intentionally so that seeking to
the
> beginning would remain fast, however, I did not do any research into
alternative
> strategies to see if they would be more efficient. Partially because I it was
an
> initial implementation and pretty much guaranteed to be better than the old
> buffering code, and partially because the blocks I really care about are
> supposed to be pinned. This is also why I decided to use an LRU, which is a
> pretty terrible caching strategy. If we really want to optimize the order in
> which blocks are freed, the right thing to do is probably to get rid of the
LRU
> completely and replace it with something that understands the access pattern
and
> frees blocks based on how likely they are to be used again.
>
> Perhaps we should be doing something like:
> 
> if (behind all readers AND not first range of blocks) {
>   free from front to back
> } else {
>   free from back to front
> }
> 
> Basically we need some sort of benchmark that we can optimize against to
figure
> these things out.

I'm afraid coming up with a replacement of the LRU is beyond the amount of
effort I am able to put into this right now. My intention was to fix something I
perceived as an inconsistency in the eviction strategy and thus make the LRU to
be "more LRU". As you know, the motivation for this came from the work on the
integration of the multibuffer in Opera. But if you think it's not generally
beneficial then I'm fine with dropping this CL.

[hubbe, 2016-09-23 22:15:22]

On 2016/09/23 21:34:43, wdzierzanowski wrote:
> On 2016/09/23 17:24:45, hubbe wrote:
> > On 2016/09/23 07:35:03, wdzierzanowski wrote:
> > > hubbe, found this when working on the integration of the multibuffer in
> Opera.
> > I
> > > think it could benefit you guys too, PTAL.
> > 
> > I'd like to understand the implications better.
> > 
> 
> OK, let me try to shed some light with the help of some images. Imagine
playing
> a file for a while and then seeking forwards.
> 
> This shows the current eviction order (the green bars are the "present"
blocks):
> http://pasteboard.co/6H74RxXQq.png
> 
> This is how it looks like with this CL: http://pasteboard.co/6H83AjEie.png
> 
> Notice how in the former case the blocks are evicted in the MRU order. I
assumed
> this wasn't intentional in a cache with the LRU strategy. But you're saying
this
> assumption was wrong?
> 
> > I originally did the move-to-LRU in reverse intentionally so that seeking to
> the
> > beginning would remain fast, however, I did not do any research into
> alternative
> > strategies to see if they would be more efficient. Partially because I it
was
> an
> > initial implementation and pretty much guaranteed to be better than the old
> > buffering code, and partially because the blocks I really care about are
> > supposed to be pinned. This is also why I decided to use an LRU, which is a
> > pretty terrible caching strategy. If we really want to optimize the order in
> > which blocks are freed, the right thing to do is probably to get rid of the
> LRU
> > completely and replace it with something that understands the access pattern
> and
> > frees blocks based on how likely they are to be used again.
> >
> > Perhaps we should be doing something like:
> > 
> > if (behind all readers AND not first range of blocks) {
> >   free from front to back
> > } else {
> >   free from back to front
> > }
> > 
> > Basically we need some sort of benchmark that we can optimize against to
> figure
> > these things out.
> 
> I'm afraid coming up with a replacement of the LRU is beyond the amount of
> effort I am able to put into this right now. My intention was to fix something
I
> perceived as an inconsistency in the eviction strategy and thus make the LRU
to
> be "more LRU". As you know, the motivation for this came from the work on the
> integration of the multibuffer in Opera. But if you think it's not generally
> beneficial then I'm fine with dropping this CL.

Unfortunately I have no idea which of these two patterns are actually *better*.
One seems to optimize for "seeking back to where I was before seeking" while the
other optimizes for "seeking to the beginning of the file". Not sure which of
those
is actually more common in real life.

While it's terribly unfair, the bar for improving this code went from "I think
this is better"
to "I have data that shows this is better" once it shipped in a stable chrome
build.
(The unfair part being that I didn't do any of that when I wrote the code...)

Btw, I love the graphs you created, they are excellent for visualizing what's
going on
in the cache. I don't suppose you could share the code and/or scripts to used to
create those?

[wdzierzanowski, 2016-09-26 09:23:47]

Description was changed from

==========
multibuffer: Evict lower blocks first after inserting multiple blocks

When seeking, the change in reader position can cause multiple "present" blocks
to transition from pinned to unpinned state, and thus enter the LRU all at
once.  These blocks should then be evicted (by Pop()) in the
lowest-position-first order.  Issuing the Insert() calls in this order
guarantees that.

For implementation convenience, this also reverses the order of Remove()
calls.  It is assumed Remove() order is not relevant for performance as
these calls end up erasing from an std::list and std::map anyway.

TEST=media_blink_unittests --gtest_filter=MultiBuffer*:Multibuffer*
==========

to

==========
multibuffer: Evict lower blocks first after inserting multiple blocks

When seeking, the change in reader position can cause multiple "present" blocks
to transition from pinned to unpinned state, and thus enter the LRU all at
once.  These blocks should then be evicted (by Pop()) in the
lowest-position-first order.  Issuing the Insert() calls in this order
guarantees that.

For implementation convenience, this also reverses the order of Remove()
calls.  It is assumed Remove() order is not relevant for performance as
these calls end up erasing from an std::list and std::map anyway.

BUG=650201
TEST=media_blink_unittests --gtest_filter=MultiBuffer*:Multibuffer*
==========

[wdzierzanowski, 2016-09-26 09:24:39]

I've created crbug.com/650201, can we move the discussion there please? It
should make it easier to talk about pictures and stuff thanks to attachments :)