|
|
Patch Set 1 #
Total comments: 13
Patch Set 2 : Address responses #
Total comments: 2
Patch Set 3 : Update in reponse to Alasdair's comments #
Total comments: 18
Patch Set 4 : Responses to chris' comments #
Total comments: 9
Patch Set 5 : Responses to Chris' comments #
Total messages: 9
|
cykoo1
|
16 years, 3 months ago (2009年10月08日 01:33:07 UTC) #1 | ||||||||||||||||||||||||||||||||||||||
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?
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.
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
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.
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?
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).
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
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.