Bug 67823

Created attachment 107297 [details] Patch

Comment on attachment 107297 [details] Patch Ai-san, thank you for the patch. View in context: https://bugs.webkit.org/attachment.cgi?id=107297&action=review > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:1 > +#!/usr/bin/env python I think this file should move to webkitpy/common/ or webkitpy/common/system directory. And lru_cache.py might be better file name than lru.py > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:28 > +class Node(): It might be better that Node class should have 'value' member in addition to 'prev' and 'next'. That would make the implementation of LRU class simpler because we don't have to have a tuple (value, Node(...)). > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:36 > + L36-L37: One blank line instead of two blank lines. > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:40 > + def __init__(self, size): Could you add a blank line between Line39 and Line40? > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:44 > + self._size = size What if size <= 0? Could you assert the value of |size| here? assert size > 0 > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:49 > + self.first = key I think self.first and self.last should point to the first Node and the last Node directly. def __setitem__(self, key, value): if not self.first: node = Node(value, ,,,) self._dict[key] = node self.first = node self.last = node self.last_key = key // I am not sure, but I guess we should keep track of the last_key to delete the last Node from the self_dict. And Node class's |prev| and |next| also point to other Nodes directly, instead of having |key|. That might make the implementation of this LRU class more natural. That'd be nice if you could try to rewrite this class as I suggested. > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:114 > + def pop(self, key): Do we need this |pop| method? To look up a value by a key, 'lru[key]' is good enough because this class defines __getitems__(..) method. > Tools/Scripts/webkitpy/layout_tests/reftests/lru_unittest.py:28 > +import lru We should use absolute path in import. like: from webkipy.common.xxx import lru

Created attachment 107322 [details] Patch

I addressed your comment.(In reply to comment #2) > (From update of attachment 107297 [details]) > Ai-san, thank you for the patch. > > View in context: https://bugs.webkit.org/attachment.cgi?id=107297&action=review > > > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:1 > > +#!/usr/bin/env python > > I think this file should move to webkitpy/common/ or webkitpy/common/system directory. > And lru_cache.py might be better file name than lru.py > > > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:28 > > +class Node(): > > It might be better that Node class should have 'value' member in addition to 'prev' and 'next'. > That would make the implementation of LRU class simpler because we don't have to have a tuple (value, Node(...)). > > > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:36 > > + > > L36-L37: One blank line instead of two blank lines. > > > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:40 > > + def __init__(self, size): > > Could you add a blank line between Line39 and Line40? > > > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:44 > > + self._size = size > > What if size <= 0? Could you assert the value of |size| here? > assert size > 0 > > > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:49 > > + self.first = key > > I think self.first and self.last should point to the first Node and the last Node directly. > > def __setitem__(self, key, value): > if not self.first: > node = Node(value, ,,,) > self._dict[key] = node > self.first = node > self.last = node > self.last_key = key // I am not sure, but I guess we should keep track of the last_key to delete the last Node from the self_dict. > > And Node class's |prev| and |next| also point to other Nodes directly, instead of having |key|. > That might make the implementation of this LRU class more natural. > > That'd be nice if you could try to rewrite this class as I suggested. > > > Tools/Scripts/webkitpy/layout_tests/reftests/lru.py:114 > > + def pop(self, key): > > Do we need this |pop| method? > To look up a value by a key, 'lru[key]' is good enough because this class defines __getitems__(..) method. > > > Tools/Scripts/webkitpy/layout_tests/reftests/lru_unittest.py:28 > > +import lru > > We should use absolute path in import. > like: > from webkipy.common.xxx import lru

Comment on attachment 107322 [details] Patch Thank you! The patch looks good! I think there are still some corner cases we must handle carefully. View in context: https://bugs.webkit.org/attachment.cgi?id=107322&action=review > Tools/Scripts/webkitpy/common/lru_cache.py:39 > + size: a cache memory size 'capacity' might be a better name than 'size' in this context. > Tools/Scripts/webkitpy/common/lru_cache.py:42 > + assert size > 0, "You should set the LRUCache size to not less than zero." You might want to include the actual value of |capacity| in the assertion message. like: assert capacity > 0, "capacity (%s) must be greater than zero." % capacity > Tools/Scripts/webkitpy/common/lru_cache.py:43 > + self.first = None if you don't want to expose |first| and |last|, that should be named like |_first| and |_last|. > Tools/Scripts/webkitpy/common/lru_cache.py:49 > + if self.first == None: I think if not self.first: is more pythonic than if self.first == None: At least it should be 'self.first is None' instead of 'self.first == None'. > Tools/Scripts/webkitpy/common/lru_cache.py:65 > + node = Node(key, value, self.first) When _one_node is called, self.first is always None, isn't it? Therefore this should be: node = Node(key, value, None) > Tools/Scripts/webkitpy/common/lru_cache.py:71 > + if self.first.key == key: If self.first is None, this will fail. > Tools/Scripts/webkitpy/common/lru_cache.py:99 > + self.first = node.prev If LRUCache contains one item, (k, v) and del[k] is called, it seems self.first will become 'None' here. So the following self.first.next will fail. Could you add a testcase for this? And if self.first and self.last point to the same node, it seems we also have to set self.last = None here.

Created attachment 107494 [details] Patch

I addressed your comment. (In reply to comment #5) > (From update of attachment 107322 [details]) > Thank you! The patch looks good! > I think there are still some corner cases we must handle carefully. > > View in context: https://bugs.webkit.org/attachment.cgi?id=107322&action=review > > > Tools/Scripts/webkitpy/common/lru_cache.py:39 > > + size: a cache memory size > > 'capacity' might be a better name than 'size' in this context. > > > Tools/Scripts/webkitpy/common/lru_cache.py:42 > > + assert size > 0, "You should set the LRUCache size to not less than zero." > > You might want to include the actual value of |capacity| in the assertion message. > like: > assert capacity > 0, "capacity (%s) must be greater than zero." % capacity > > > Tools/Scripts/webkitpy/common/lru_cache.py:43 > > + self.first = None > > if you don't want to expose |first| and |last|, that should be named like |_first| and |_last|. > > > Tools/Scripts/webkitpy/common/lru_cache.py:49 > > + if self.first == None: > > I think > if not self.first: > is more pythonic than > if self.first == None: > > At least it should be 'self.first is None' instead of 'self.first == None'. > > > Tools/Scripts/webkitpy/common/lru_cache.py:65 > > + node = Node(key, value, self.first) > > When _one_node is called, self.first is always None, isn't it? > Therefore this should be: > node = Node(key, value, None) > > > Tools/Scripts/webkitpy/common/lru_cache.py:71 > > + if self.first.key == key: > > If self.first is None, this will fail. > > > Tools/Scripts/webkitpy/common/lru_cache.py:99 > > + self.first = node.prev > > If LRUCache contains one item, (k, v) and del[k] is called, it seems self.first will become 'None' here. So the following self.first.next will fail. Could you add a testcase for this? > > And if self.first and self.last point to the same node, it seems we also have to set self.last = None here.

Created attachment 107582 [details] Patch

Comment on attachment 107582 [details] Patch Thank you for addressing my comments! I added some comments. Sorry for the back and forth again. I hope you will enjoy your last day of the internship. :) View in context: https://bugs.webkit.org/attachment.cgi?id=107582&action=review > Tools/Scripts/webkitpy/common/lru_cache.py:59 > + node = Node(key, value, self._first) I think if self._dict already contains the key, we have to delete the node with the key from the doubly linked list. Without that, we are likely to have two nodes with the same key in the doubly liked list. > Tools/Scripts/webkitpy/common/lru_cache.py:77 > + next__last = self._last.next Nit: Two underscores '__'. You meant |next_last|, |next_first|? > Tools/Scripts/webkitpy/common/lru_cache.py:88 > + key_next = self._dict[key].next You might use |node| here. key_next = node.next key_prev = node.prev Or You might rewrite L88-L91 with the following two lines: node.next.prev = node.prev node.prev.next = node.next > Tools/Scripts/webkitpy/common/lru_cache.py:99 > + if self._first == self._last: It seems that this should be 'self._first is self._last'. > Tools/Scripts/webkitpy/common/lru_cache.py:102 > + del self._dict[key] It seems that if the key is not found here, a lru_cache will become inconsistant state (self._dict has one item, but self._first is None). It might be better to call 'node = self._dict[key]' at the beginning of the function. e.g. def __delitem__(self, key): node = self._dict[key] del self._dict[key] if self._first is self._last: self._first = None self._last = None return if self._first is node: self._first = node.prev self._first.next = None return if self._last is node: self._last = node.next self._last.prev = None return node.next.prev = node.prev node.prev.next = node.next I've not tested this. I guess your existing unittests (or new tests) will find any bugs in this code :)

Created attachment 107604 [details] Patch

I addressed your comment. (In reply to comment #9) > (From update of attachment 107582 [details]) > Thank you for addressing my comments! I added some comments. Sorry for the back and forth again. > I hope you will enjoy your last day of the internship. :) > > View in context: https://bugs.webkit.org/attachment.cgi?id=107582&action=review > > > Tools/Scripts/webkitpy/common/lru_cache.py:59 > > + node = Node(key, value, self._first) > > I think if self._dict already contains the key, we have to delete the node with the key from the doubly linked list. > Without that, we are likely to have two nodes with the same key in the doubly liked list. > > > Tools/Scripts/webkitpy/common/lru_cache.py:77 > > + next__last = self._last.next > > Nit: Two underscores '__'. > You meant |next_last|, |next_first|? > > > Tools/Scripts/webkitpy/common/lru_cache.py:88 > > + key_next = self._dict[key].next > > You might use |node| here. > key_next = node.next > key_prev = node.prev > > Or You might rewrite L88-L91 with the following two lines: > node.next.prev = node.prev > node.prev.next = node.next > > > Tools/Scripts/webkitpy/common/lru_cache.py:99 > > + if self._first == self._last: > > It seems that this should be 'self._first is self._last'. > > > Tools/Scripts/webkitpy/common/lru_cache.py:102 > > + del self._dict[key] > > It seems that if the key is not found here, a lru_cache will become inconsistant state (self._dict has one item, but self._first is None). > > It might be better to call 'node = self._dict[key]' at the beginning of the function. > e.g. > > def __delitem__(self, key): > node = self._dict[key] > del self._dict[key] > if self._first is self._last: > self._first = None > self._last = None > return > if self._first is node: > self._first = node.prev > self._first.next = None > return > if self._last is node: > self._last = node.next > self._last.prev = None > return > node.next.prev = node.prev > node.prev.next = node.next > > I've not tested this. I guess your existing unittests (or new tests) will find any bugs in this code :)

Comment on attachment 107604 [details] Patch Thank you for updating the patch! I gave you one comment! View in context: https://bugs.webkit.org/attachment.cgi?id=107604&action=review > Tools/Scripts/webkitpy/common/lru_cache.py:60 > + if key in self._dict: I think L60-61 lines should move at the beginning of this function. If self._dict has one item and L61 deletes that item, self._first becomes None, so L62 fails...:(

Created attachment 107615 [details] Patch

I addressed your comment. (In reply to comment #12) > (From update of attachment 107604 [details]) > Thank you for updating the patch! I gave you one comment! > > View in context: https://bugs.webkit.org/attachment.cgi?id=107604&action=review > > > Tools/Scripts/webkitpy/common/lru_cache.py:60 > > + if key in self._dict: > > I think L60-61 lines should move at the beginning of this function. > If self._dict has one item and L61 deletes that item, self._first becomes None, so L62 fails...:(

Looks good to me. Thank you!

Comment on attachment 107615 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=107615&action=review FWIW, I think this would be less confusing if you just kept a list of keys rather than the linked list. As long as the capacity is small (maybe less than 20 entries), it'll still be plenty fast to update. But this approach is fine too if you fix the memory leak I mentioned. > Tools/Scripts/webkitpy/common/lru_cache.py:39 > + Args: > + capacity: a cache memory capacity Nit: This should be in the docstring for __init__. > Tools/Scripts/webkitpy/common/lru_cache.py:57 > + if self._capacity == 1: > + self._one_node(key, value) I think you need to clear self._first here or the new node will point to the old value. If the capacity is 1, we leak all the old objects because we hold a ref to them.

Hi Tony, thank you for the review. Since Ai-san, the author of the patch, has already left Google, I'll update the patch later, addressing your comment. (In reply to comment #16) > (From update of attachment 107615 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=107615&action=review > > FWIW, I think this would be less confusing if you just kept a list of keys rather than the linked list. As long as the capacity is small (maybe less than 20 entries), it'll still be plenty fast to update. But this approach is fine too if you fix the memory leak I mentioned. > > > Tools/Scripts/webkitpy/common/lru_cache.py:39 > > + Args: > > + capacity: a cache memory capacity > > Nit: This should be in the docstring for __init__. > > > Tools/Scripts/webkitpy/common/lru_cache.py:57 > > + if self._capacity == 1: > > + self._one_node(key, value) > > I think you need to clear self._first here or the new node will point to the old value. If the capacity is 1, we leak all the old objects because we hold a ref to them.

Created attachment 108278 [details] fix_leak

Comment on attachment 107615 [details] Patch I've addressed your comments. Could you take another look? View in context: https://bugs.webkit.org/attachment.cgi?id=107615&action=review >>> Tools/Scripts/webkitpy/common/lru_cache.py:39 >>> + capacity: a cache memory capacity >> >> Nit: This should be in the docstring for __init__. > > Done >> Tools/Scripts/webkitpy/common/lru_cache.py:57 >> + self._one_node(key, value) > > I think you need to clear self._first here or the new node will point to the old value. If the capacity is 1, we leak all the old objects because we hold a ref to them. Nice catch. Instead of clearing self._first here, I've changed Node's __init__ method so that it doesn't receive |prev| and |next| parameters, which looks better to me.

Comment on attachment 108278 [details] fix_leak View in context: https://bugs.webkit.org/attachment.cgi?id=108278&action=review > Tools/Scripts/webkitpy/common/lru_cache.py:32 > +class Node(): > + def __init__(self, key, value): > + self.key = key > + self.value = value > + self.prev = None > + self.next = None Nit: You can save a bit of memory by making prev and next class variables. E.g.: class Node(): prev = None next = None def __init__(self, key, value): self.key = key self.value = value

Thank you for the review. I am going to land that. (In reply to comment #20) > (From update of attachment 108278 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=108278&action=review > > > Tools/Scripts/webkitpy/common/lru_cache.py:32 > > +class Node(): > > + def __init__(self, key, value): > > + self.key = key > > + self.value = value > > + self.prev = None > > + self.next = None > > Nit: You can save a bit of memory by making prev and next class variables. E.g.: > class Node(): > prev = None > next = None > def __init__(self, key, value): > self.key = key > self.value = value Nice tips, but in each lru_cache instance, there are at most two nodes, _first and _last, whose next (or prev) value is None. Therefore it might not be worth making these class variables.

Committed r95928: <http://trac.webkit.org/changeset/95928>