Add some basic functions for LRU cache.

[ChrisM, 2009-10-16 16:02:12]

Looks pretty good in general, though I have a few questions.

http://codereview.appspot.com/130044/diff/1/3
File include/lru_cache.h (right):

http://codereview.appspot.com/130044/diff/1/3#newcode2
Line 2: #define LRU_CACHE_
I am not sure what the standard style is like, but I think it would be useful to
have a class comment up here describing the algorithm in some detail (including
how the list is used and whatnot).

http://codereview.appspot.com/130044/diff/1/3#newcode6
Line 6: // TODO: makes this class thread-safe and adds corresponding data-race
test.
Yes, this is a good todo. ;)

http://codereview.appspot.com/130044/diff/1/3#newcode18
Line 18: template <class Key, class T>
why class here and typename for the struct? can't you just use typename in both
places?

http://codereview.appspot.com/130044/diff/1/3#newcode22
Line 22: typedef Key key_type;
this also seems a little unnecessary. you already have the types defined above,
right? is this just to make the names more descriptive?

http://codereview.appspot.com/130044/diff/1/3#newcode26
Line 26: typedef tr1::unordered_map<key_type, lru_list_node*> cache_map;
cache_contents?

http://codereview.appspot.com/130044/diff/1/3#newcode70
Line 70: void erase(const key_type& k) {
minor point, but you could have erase return a bool to indicate if anything was
erased?

http://codereview.appspot.com/130044/diff/1/3#newcode110
Line 110: void remove_node_from_list(lru_list_node* node) {
what if the node is the last one in the list?
dont you need to set head to null in that case?

[cykoo1, 2009-10-29 01:20:59]

Sorry for the late response. Here are the updates.

http://codereview.appspot.com/130044/diff/1/3
File include/lru_cache.h (right):

http://codereview.appspot.com/130044/diff/1/3#newcode2
Line 2: #define LRU_CACHE_
On 2009/10/16 16:02:12, ccmysen wrote:
> I am not sure what the standard style is like, but I think it would be useful
to
> have a class comment up here describing the algorithm in some detail
(including
> how the list is used and whatnot).

Done.

http://codereview.appspot.com/130044/diff/1/3#newcode18
Line 18: template <class Key, class T>
On 2009/10/16 16:02:12, ccmysen wrote:
> why class here and typename for the struct? can't you just use typename in
both
> places?

Done.

http://codereview.appspot.com/130044/diff/1/3#newcode22
Line 22: typedef Key key_type;
On 2009/10/16 16:02:12, ccmysen wrote:
> this also seems a little unnecessary. you already have the types defined
above,
> right? is this just to make the names more descriptive?

I am not entirely sure about the standard style, but it seems like the c++0x
standard draft (n2914.pdf e.g. section 27.5.4) is doing something similar.

http://codereview.appspot.com/130044/diff/1/3#newcode26
Line 26: typedef tr1::unordered_map<key_type, lru_list_node*> cache_map;
On 2009/10/16 16:02:12, ccmysen wrote:
> cache_contents?

Done.

http://codereview.appspot.com/130044/diff/1/3#newcode70
Line 70: void erase(const key_type& k) {
On 2009/10/16 16:02:12, ccmysen wrote:
> minor point, but you could have erase return a bool to indicate if anything
was
> erased?

Done.

http://codereview.appspot.com/130044/diff/1/3#newcode110
Line 110: void remove_node_from_list(lru_list_node* node) {
On 2009/10/16 16:02:12, ccmysen wrote:
> what if the node is the last one in the list?
> dont you need to set head to null in that case?

The head points to itself if there is no element in the cache, it's a circular
doubly linked list.

[Alasdair, 2009-10-30 18:58:05]

http://codereview.appspot.com/130044/diff/3001/3003
File include/lru_cache.h (right):

http://codereview.appspot.com/130044/diff/3001/3003#newcode126
Line 126: int max_size_;
Should probably be size_t for max and current size

[cykoo1, 2009-11-02 18:54:21]

http://codereview.appspot.com/130044/diff/3001/3003
File include/lru_cache.h (right):

http://codereview.appspot.com/130044/diff/3001/3003#newcode126
Line 126: int max_size_;
On 2009/10/30 18:58:05, Alasdair wrote:
> Should probably be size_t for max and current size

Done.

[ChrisM, 2009-11-05 19:29:54]

http://codereview.appspot.com/130044/diff/4003/3008
File include/lru_cache.h (right):

http://codereview.appspot.com/130044/diff/4003/3008#newcode16
Line 16: // TODO: makes this class thread-safe and adds corresponding data-race
test.
are the plans to check this in without the thread-safety modifications/tests?

http://codereview.appspot.com/130044/diff/4003/3008#newcode62
Line 62: if (current_size_ > max_size_) {
there should probably also be tests that the size capping is working properly.

http://codereview.appspot.com/130044/diff/4003/3008#newcode62
Line 62: if (current_size_ > max_size_) {
you should probably call size() for this?

http://codereview.appspot.com/130044/diff/4003/3008#newcode104
Line 104: lru_list_head_.next = &lru_list_head_;
and probably tests (somehow) that the list/map are kept in sync (sizes don't
start to mismatch).

http://codereview.appspot.com/130044/diff/4003/3010
File testing/lru_test.cc (right):

http://codereview.appspot.com/130044/diff/4003/3010#newcode9
Line 9: // TODO: adds test cases for lru_cache<shared_ptr, shared_prt>(?)
probably a good idea?

[cykoo1, 2009-12-04 01:27:56]

I've also run the test under thread sanitizer
(http://code.google.com/p/google-concurrency-library/wiki/RaceDetectionTools).

http://codereview.appspot.com/130044/diff/4003/3008
File include/lru_cache.h (right):

http://codereview.appspot.com/130044/diff/4003/3008#newcode16
include/lru_cache.h:16: // TODO: makes this class thread-safe and adds
corresponding data-race test.
On 2009/11/05 19:29:54, ccmysen wrote:
> are the plans to check this in without the thread-safety modifications/tests?

Done.

http://codereview.appspot.com/130044/diff/4003/3008#newcode62
include/lru_cache.h:62: if (current_size_ > max_size_) {
On 2009/11/05 19:29:54, ccmysen wrote:
> there should probably also be tests that the size capping is working properly.

Done.

http://codereview.appspot.com/130044/diff/4003/3008#newcode62
include/lru_cache.h:62: if (current_size_ > max_size_) {
On 2009/11/05 19:29:54, ccmysen wrote:
> there should probably also be tests that the size capping is working properly.

Done.

http://codereview.appspot.com/130044/diff/4003/3008#newcode104
include/lru_cache.h:104: lru_list_head_.next = &lru_list_head_;
On 2009/11/05 19:29:54, ccmysen wrote:
> and probably tests (somehow) that the list/map are kept in sync (sizes don't
> start to mismatch).

Done.

http://codereview.appspot.com/130044/diff/4003/3010
File testing/lru_test.cc (right):

http://codereview.appspot.com/130044/diff/4003/3010#newcode9
testing/lru_test.cc:9: // TODO: adds test cases for lru_cache<shared_ptr,
shared_prt>(?)
On 2009/11/05 19:29:54, ccmysen wrote:
> probably a good idea?

Adds a test for lru_cache<int, shared_ptr>. (Note that the underlying hashmap
implementation requires the key to be hashable, hence we couldn't pass the key
as a shared pointer).

[ChrisM, 2009-12-10 16:41:03]

Sorry i was a little slow on getting to this.
It's pretty good now, though.

http://codereview.appspot.com/130044/diff/4003/3008
File include/lru_cache.h (right):

http://codereview.appspot.com/130044/diff/4003/3008#newcode63
include/lru_cache.h:63: erase(lru_list_head_.prev->key);
minor question, but do you think we should modify this so that you do
while(size() > max_size_) {} so that if someone else inserts, we could clean up
for that thread? There is a concurrency issue there, but just thought I'd ask.

http://codereview.appspot.com/130044/diff/4003/3008#newcode67
include/lru_cache.h:67: bool lookup(const key_type& k, value_type& v) {
is the expectation that these functions generally go uncommented? otherwise it
might be nice to have a couple function level comments mentioning what is being
done.

http://codereview.appspot.com/130044/diff/4003/3008#newcode81
include/lru_cache.h:81: bool erase(const key_type& k) {
so, often erase() is for iterators, do you think we should make it clear that we
erase keys?

http://codereview.appspot.com/130044/diff/4003/3008#newcode100
include/lru_cache.h:100: while (node != &lru_list_head_) {
i know your lru_list struct is just data, but you could move the deletion logic
into the list (have it delete itself?).

http://codereview.appspot.com/130044/diff/4003/3008#newcode122
include/lru_cache.h:122: void remove_node_from_list(lru_list_node* node) {
this could go into the list struct as well (and the previous one).

http://codereview.appspot.com/130044/diff/9001/10002#newcode21
include/lru_cache.h:21: struct lru_list_element {
or better yet, can you use an existing doubly linked list for this with a value
with pair<Key, T>?

http://codereview.appspot.com/130044/diff/9001/10002#newcode47
include/lru_cache.h:47: // Remove existing entry (if any).
can you explain somewhere why you need a recursive mutex for this code?

http://codereview.appspot.com/130044/diff/9001/10004
File testing/lru_test.cc (right):

http://codereview.appspot.com/130044/diff/9001/10004#newcode62
testing/lru_test.cc:62: // Make sure that the cache still works after being
cleared.
const int kOffset = 5;

insert(kOffset + i*2, kOffset + i*2 + 1)?

http://codereview.appspot.com/130044/diff/9001/10004#newcode77
testing/lru_test.cc:77: // A small test for shared pointer.
small test that shared pointers work properly?

http://codereview.appspot.com/130044/diff/9001/10004#newcode132
testing/lru_test.cc:132: lru_cache<int, int> cache(size);
cool

[cykoo1, 2009-12-17 02:06:46]

http://codereview.appspot.com/130044/diff/4003/3008
File include/lru_cache.h (right):

http://codereview.appspot.com/130044/diff/4003/3008#newcode63
include/lru_cache.h:63: erase(lru_list_head_.prev->key);
On 2009/12/10 16:41:04, ccmysen wrote:
> minor question, but do you think we should modify this so that you do
> while(size() > max_size_) {} so that if someone else inserts, we could clean
up
> for that thread? There is a concurrency issue there, but just thought I'd ask.

The current API only allows adding 1 element at a time. It's not clear to me why
we need a while loop().

http://codereview.appspot.com/130044/diff/4003/3008#newcode67
include/lru_cache.h:67: bool lookup(const key_type& k, value_type& v) {
On 2009/12/10 16:41:04, ccmysen wrote:
> is the expectation that these functions generally go uncommented? otherwise it
> might be nice to have a couple function level comments mentioning what is
being
> done.
done.

http://codereview.appspot.com/130044/diff/4003/3008#newcode81
include/lru_cache.h:81: bool erase(const key_type& k) {
On 2009/12/10 16:41:04, ccmysen wrote:
> so, often erase() is for iterators, do you think we should make it clear that
we
> erase keys?

I looked a bit over the c++0x standard draft (n2914.pdf). and notice that
erase() isn't only for iterators , e.g. in map, it has something like size_type
erase(const key_type& k)

http://codereview.appspot.com/130044/diff/9001/10002#newcode21
include/lru_cache.h:21: struct lru_list_element {
On 2009/12/10 16:41:04, ccmysen wrote:
> or better yet, can you use an existing doubly linked list for this with a
value
> with pair<Key, T>?

Actually I thought about that too (using stl implementation or put the linked
list into a separate class). The main reason is that the current implementations
assume quite a lot of knowledge about the implementation of the linked list.

For instance, an existing doubly linked list would identify an element via
iterator. But that doesn't quite fit here: the hash map will need to store
pointers to elements in the linked list - the position of an element would
change over time due to insert/erase etc.

http://codereview.appspot.com/130044/diff/9001/10002#newcode47
include/lru_cache.h:47: // Remove existing entry (if any).
On 2009/12/10 16:41:04, ccmysen wrote:
> can you explain somewhere why you need a recursive mutex for this code?

Because I would need to remove an old entry first. The cleanest way is to call
erase(). But it will end up in deadlock unless mutex is recursive.

http://codereview.appspot.com/130044/diff/9001/10004
File testing/lru_test.cc (right):

http://codereview.appspot.com/130044/diff/9001/10004#newcode62
testing/lru_test.cc:62: // Make sure that the cache still works after being
cleared.
On 2009/12/10 16:41:04, ccmysen wrote:
> const int kOffset = 5;
> 
> insert(kOffset + i*2, kOffset + i*2 + 1)?

Done.

http://codereview.appspot.com/130044/diff/9001/10004#newcode77
testing/lru_test.cc:77: // A small test for shared pointer.
On 2009/12/10 16:41:04, ccmysen wrote:
> small test that shared pointers work properly?

Done.