Simple LRU class

Simple LRU class

This will be a component of the multibuffer media cache.

Media cache design doc:
https://docs.google.com/document/d/15q6LTG0iDUe30QcoMtj4XNmKCa_7W_Q2uUIPFsJhS1E/edit

BUG=514719
Committed: https://crrev.com/250775b65fb993aba5b99c9f2bd1ab924d69d1ed
Cr-Commit-Position: refs/heads/master@{#358964}

[hubbe, 2015-11-06 19:00:05]

hubbe@chromium.org changed reviewers:
+ xhwang@chromium.org

[xhwang, 2015-11-10 00:50:01]

looking good. Mostly nits and questions.

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru.h
File media/blink/lru.h (right):

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru.h#ne...
media/blink/lru.h:8: #include <list>
nit: one extra line here

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru.h#ne...
media/blink/lru.h:13: template <typename T>
OOC, what's the typical T we are gonna use? Asking because we are copying T a
lot.

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru.h#ne...
media/blink/lru.h:14: class LRU {
Add a brief comment and provide a reference for LRU cache, just for easier
readability.

Also, how performance critical will this class be? (Trying to justify the
"simple LRU class" in the CL description).

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru.h#ne...
media/blink/lru.h:42: // Returns the Least Recently Used T.
and removes it..

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru.h#ne...
media/blink/lru.h:51: T Peek() const {
Add comment.

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru.h#ne...
media/blink/lru.h:56: bool Contains(const T& x) const { return pos_.find(x) !=
pos_.end(); }
DCHECK it's not in |lru_| either?

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru.h#ne...
media/blink/lru.h:62: base::hash_map<T, typename std::list<T>::iterator> pos_;
Add a brief comment.

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru_unit...
File media/blink/lru_unittest.cc (right):

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru_unit...
media/blink/lru_unittest.cc:6: #include <string>
what is this for?

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru_unit...
media/blink/lru_unittest.cc:9: #include "base/strings/stringprintf.h"
what is this for?

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru_unit...
media/blink/lru_unittest.cc:110: }
Why not popping both LRU until empty? Then you don't need the "friend"?

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru_unit...
media/blink/lru_unittest.cc:139: }
nit: // namespace

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru_unit...
media/blink/lru_unittest.cc:209: switch (rnd_.Rand() % 3) {
value and "operation" could be correlated. Why not use two random number
generator to make this test really random?

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/test_ran...
File media/blink/test_random.h (right):

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/test_ran...
media/blink/test_random.h:1: // Copyright 2013 The Chromium Authors. All rights
reserved.
2015

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/test_ran...
media/blink/test_random.h:8: // Vastly simplified ACM random class meant to only
be used for testing.
Could you please provide more context here why methods in base/rand_util.h
aren't sufficient and we have to develop our own here. In that case, does it
make sense to add this to base/rand_util.h?

Also, it'd be nice to provide a reference to the ACM random class.

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/test_ran...
media/blink/test_random.h:14: explicit TestRandom(uint32 seed) {
nit: for new files use uint32_t as per style guide.

[hubbe, 2015-11-10 18:26:16]

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru.h
File media/blink/lru.h (right):

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru.h#newcode8
media/blink/lru.h:8: #include <list>
On 2015/11/10 00:50:01, xhwang wrote:
> nit: one extra line here

Done.

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru.h#newcode13
media/blink/lru.h:13: template <typename T>
On 2015/11/10 00:50:01, xhwang wrote:
> OOC, what's the typical T we are gonna use? Asking because we are copying T a
> lot.

We'll mostly be using a std::pair<multibuffer*, int32_t>

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru.h#newcode14
media/blink/lru.h:14: class LRU {
On 2015/11/10 00:50:01, xhwang wrote:
> Add a brief comment and provide a reference for LRU cache, just for easier
> readability.
> 
> Also, how performance critical will this class be? (Trying to justify the
> "simple LRU class" in the CL description).

Comment added. As for performance:
In our use case, we'll might have a few thousand entries in the LRU and we'll be
calling it a couple of times per block, so big-O performance is important,
absolute performance is probably not.

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru.h#newcode42
media/blink/lru.h:42: // Returns the Least Recently Used T.
On 2015/11/10 00:50:01, xhwang wrote:
> and removes it..

Done.

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru.h#newcode51
media/blink/lru.h:51: T Peek() const {
On 2015/11/10 00:50:01, xhwang wrote:
> Add comment.

Done.

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru.h#newcode56
media/blink/lru.h:56: bool Contains(const T& x) const { return pos_.find(x) !=
pos_.end(); }
On 2015/11/10 00:50:01, xhwang wrote:
> DCHECK it's not in |lru_| either?

That's a pretty expensive DCHECK() I don't think I want to put a linear search
here...

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru.h#newcode62
media/blink/lru.h:62: base::hash_map<T, typename std::list<T>::iterator> pos_;
On 2015/11/10 00:50:01, xhwang wrote:
> Add a brief comment.

Done.

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru_unittest.cc
File media/blink/lru_unittest.cc (right):

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru_unittest.cc...
media/blink/lru_unittest.cc:6: #include <string>
On 2015/11/10 00:50:01, xhwang wrote:
> what is this for?

I think it was for some code that is now gone.
(removed)

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru_unittest.cc...
media/blink/lru_unittest.cc:9: #include "base/strings/stringprintf.h"
On 2015/11/10 00:50:01, xhwang wrote:
> what is this for?

I think it was for some code that is now gone.
(removed)

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru_unittest.cc...
media/blink/lru_unittest.cc:110: }
On 2015/11/10 00:50:01, xhwang wrote:
> Why not popping both LRU until empty? Then you don't need the "friend"?

Speed?
The random test below calls this function quite a few times.

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru_unittest.cc...
media/blink/lru_unittest.cc:139: }
On 2015/11/10 00:50:01, xhwang wrote:
> nit: // namespace

Done.

https://codereview.chromium.org/1427433012/diff/1/media/blink/lru_unittest.cc...
media/blink/lru_unittest.cc:209: switch (rnd_.Rand() % 3) {
On 2015/11/10 00:50:01, xhwang wrote:
> value and "operation" could be correlated. Why not use two random number
> generator to make this test really random?

If the random number generator is that bad, we should fix it (see test_random.h)

https://codereview.chromium.org/1427433012/diff/1/media/blink/test_random.h
File media/blink/test_random.h (right):

https://codereview.chromium.org/1427433012/diff/1/media/blink/test_random.h#n...
media/blink/test_random.h:1: // Copyright 2013 The Chromium Authors. All rights
reserved.
On 2015/11/10 00:50:01, xhwang wrote:
> 2015

Done.

https://codereview.chromium.org/1427433012/diff/1/media/blink/test_random.h#n...
media/blink/test_random.h:8: // Vastly simplified ACM random class meant to only
be used for testing.
On 2015/11/10 00:50:01, xhwang wrote:
> Could you please provide more context here why methods in base/rand_util.h
> aren't sufficient and we have to develop our own here. In that case, does it
> make sense to add this to base/rand_util.h?
> 
> Also, it'd be nice to provide a reference to the ACM random class.

Done.

https://codereview.chromium.org/1427433012/diff/1/media/blink/test_random.h#n...
media/blink/test_random.h:14: explicit TestRandom(uint32 seed) {
On 2015/11/10 00:50:01, xhwang wrote:
> nit: for new files use uint32_t as per style guide.

Done.

[xhwang, 2015-11-10 19:55:14]

Some comments are in the previous PS.

LGTM % comments and nits

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru_unit...
File media/blink/lru_unittest.cc (right):

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru_unit...
media/blink/lru_unittest.cc:110: }
On 2015/11/10 18:26:15, hubbe wrote:
> On 2015/11/10 00:50:01, xhwang wrote:
> > Why not popping both LRU until empty? Then you don't need the "friend"?
> 
> Speed?
> The random test below calls this function quite a few times.

Have you actually measured the speed in that case? Just want to make sure we
don't optimize prematurely.

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru_unit...
media/blink/lru_unittest.cc:209: switch (rnd_.Rand() % 3) {
On 2015/11/10 18:26:15, hubbe wrote:
> On 2015/11/10 00:50:01, xhwang wrote:
> > value and "operation" could be correlated. Why not use two random number
> > generator to make this test really random?
> 
> If the random number generator is that bad, we should fix it (see
test_random.h)
> 

Acknowledged.

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru.h
File media/blink/lru.h (right):

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru....
media/blink/lru.h:24: //  cout << lru.Pop();  // this will print "3"
should this print 2?

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru....
media/blink/lru.h:30: void Insert(const T& x) {
Add comment why people want to use this instead of Use()? e.g. performance etc.

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru_...
File media/blink/lru_unittest.cc (right):

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru_...
media/blink/lru_unittest.cc:14: const int kTestSize = 16;
nit: TestSize is confusing. This is really the range for the integers used in
the LRU...

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru_...
media/blink/lru_unittest.cc:133: media::TestRandom rnd_;
As discussed offline, personally I'd prefer pure random tests (not
deterministic). But I don't have a strong opinion here.

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/test...
File media/blink/test_random.h (right):

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/test...
media/blink/test_random.h:9: // This class is meant to generate predictable
sequences of pseudorandom
Please also mention the "platform independent" part, which is why we can't just
use C rand().

Also, this "platform independent" feature seems generically useful. Shall we try
to add it to rand_util.h?

[xhwang, 2015-11-10 20:05:26]

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru.h
File media/blink/lru.h (right):

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru....
media/blink/lru.h:79: base::hash_map<T, typename std::list<T>::iterator> pos_;
Does it make sense to make this DISALLOW_COPY_AND_ASSIGN?

[hubbe, 2015-11-10 21:50:02]

Comments addressed, will check in later today unless there are more comments.

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru_unit...
File media/blink/lru_unittest.cc (right):

https://chromiumcodereview.appspot.com/1427433012/diff/1/media/blink/lru_unit...
media/blink/lru_unittest.cc:110: }
On 2015/11/10 19:55:13, xhwang wrote:
> On 2015/11/10 18:26:15, hubbe wrote:
> > On 2015/11/10 00:50:01, xhwang wrote:
> > > Why not popping both LRU until empty? Then you don't need the "friend"?
> > 
> > Speed?
> > The random test below calls this function quite a few times.
> 
> Have you actually measured the speed in that case? Just want to make sure we
> don't optimize prematurely.

I've done some rough speed tests.
Compare() is a pretty expensive part of the random tests.
Removing the copy here cut the random test speed in almost half though.

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru.h
File media/blink/lru.h (right):

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru....
media/blink/lru.h:24: //  cout << lru.Pop();  // this will print "3"
On 2015/11/10 19:55:13, xhwang wrote:
> should this print 2?

Yes, duh, fixed. :)

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru....
media/blink/lru.h:30: void Insert(const T& x) {
On 2015/11/10 19:55:13, xhwang wrote:
> Add comment why people want to use this instead of Use()? e.g. performance
etc.

Done.

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru....
media/blink/lru.h:79: base::hash_map<T, typename std::list<T>::iterator> pos_;
On 2015/11/10 20:05:26, xhwang wrote:
> Does it make sense to make this DISALLOW_COPY_AND_ASSIGN?

Ok, needs to friend the test class then. (As per discussion)

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru_...
File media/blink/lru_unittest.cc (right):

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru_...
media/blink/lru_unittest.cc:14: const int kTestSize = 16;
On 2015/11/10 19:55:13, xhwang wrote:
> nit: TestSize is confusing. This is really the range for the integers used in
> the LRU...

Done.

https://chromiumcodereview.appspot.com/1427433012/diff/20001/media/blink/lru_...
media/blink/lru_unittest.cc:133: media::TestRandom rnd_;
On 2015/11/10 19:55:13, xhwang wrote:
> As discussed offline, personally I'd prefer pure random tests (not
> deterministic). But I don't have a strong opinion here.

Acknowledged.

[xhwang, 2015-11-10 22:41:54]

lgtm++

[hubbe, 2015-11-10 23:48:05]

The CQ bit was checked by hubbe@chromium.org

[commit-bot: I haz the power, 2015-11-10 23:49:14]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1427433012/60001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1427433012/60001

[commit-bot: I haz the power, 2015-11-11 00:00:52]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2015-11-11 00:01:33]

Patchset 4 (id:??) landed as
https://crrev.com/250775b65fb993aba5b99c9f2bd1ab924d69d1ed
Cr-Commit-Position: refs/heads/master@{#358964}