Repository: seung-lab/cloud-volume
Pull request #328 (2020-04-19 04:28:28)

refactor: drop pylru for custom version
Noticed pylru is GPL and am trying to keep CV BSD. This cures the license issue.

I looked around and all the other implementations either are not as convenient for some reason or don't have the right license, so I wrote my own. 

As a bonus, the new `LRU` class includes a `resize(N)` method, so it's easy to customize after the fact without losing your cache.


codecov-io: # [Codecov](https://codecov.io/gh/seung-lab/cloud-volume/pull/328?src=pr&el=h1) Report
> Merging [#328](https://codecov.io/gh/seung-lab/cloud-volume/pull/328?src=pr&el=desc) into [master](https://codecov.io/gh/seung-lab/cloud-volume/commit/f7fda866240c589f786eb843c96ec4f22a7a1b42&el=desc) will **decrease** coverage by `0.14%`.
> The diff coverage is `72.67%`.

[![Impacted file tree graph](https://codecov.io/gh/seung-lab/cloud-volume/pull/328/graphs/tree.svg?width=650&height=150&src=pr&token=7WwqdI3qkW)](https://codecov.io/gh/seung-lab/cloud-volume/pull/328?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master     #328      +/-   ##
==========================================
- Coverage   79.30%   79.16%   -0.15%     
==========================================
  Files          73       75       +2     
  Lines        8757     8937     +180     
==========================================
+ Hits         6945     7075     +130     
- Misses       1812     1862      +50     
```


| [Impacted Files](https://codecov.io/gh/seung-lab/cloud-volume/pull/328?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [cloudvolume/lru.py](https://codecov.io/gh/seung-lab/cloud-volume/pull/328/diff?src=pr&el=tree#diff-Y2xvdWR2b2x1bWUvbHJ1LnB5) | `68.75% <68.75%> (ø)` | |
| [cloudvolume/datasource/precomputed/sharding.py](https://codecov.io/gh/seung-lab/cloud-volume/pull/328/diff?src=pr&el=tree#diff-Y2xvdWR2b2x1bWUvZGF0YXNvdXJjZS9wcmVjb21wdXRlZC9zaGFyZGluZy5weQ==) | `78.96% <100.00%> (ø)` | |
| [test/test\_lru.py](https://codecov.io/gh/seung-lab/cloud-volume/pull/328/diff?src=pr&el=tree#diff-dGVzdC90ZXN0X2xydS5weQ==) | `100.00% <100.00%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/seung-lab/cloud-volume/pull/328?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/seung-lab/cloud-volume/pull/328?src=pr&el=footer). Last update [f7fda86...9e1bcdb](https://codecov.io/gh/seung-lab/cloud-volume/pull/328?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/cloudvolume/datasource/precomputed/sharding.py b/cloudvolume/datasource/precomputed/sharding.py
index 34b9ce0..7196148 100644
--- a/cloudvolume/datasource/precomputed/sharding.py
+++ b/cloudvolume/datasource/precomputed/sharding.py
@@ -6,12 +6,12 @@ import json
 import struct
 
 import numpy as np
-import pylru
 from tqdm import tqdm
 
 from . import mmh3
 from ... import compression
 from ...lib import jsonify, toiter
+from ...lru import LRU
 from ...exceptions import SpecViolation
 from ...storage import SimpleStorage
 
@@ -232,8 +232,8 @@ class ShardReader(object):
     self.cache = cache
     self.spec = spec
 
-    self.shard_index_cache = pylru.lrucache(shard_index_cache_size)
-    self.minishard_index_cache = pylru.lrucache(minishard_index_cache_size)
+    self.shard_index_cache = LRU(shard_index_cache_size)
+    self.minishard_index_cache = LRU(minishard_index_cache_size)
 
   def get_filename(self, label):
     return self.compute_shard_location(label)[0]
diff --git a/cloudvolume/lru.py b/cloudvolume/lru.py
new file mode 100644
index 0000000..0d55e33
--- /dev/null
+++ b/cloudvolume/lru.py
@@ -0,0 +1,221 @@
+class DoublyLinkedListIterator(object):
+  def __init__(self, node, reverse=False):
+    self.node = ListNode(None, node, node)
+    self.reverse = reverse
+  def next(self):
+    return self.__next__()
+  def __next__(self):
+    if self.reverse:
+      if self.node.prev is not None:
+        self.node = self.node.prev
+        return self.node
+    else:
+      if self.node.next is not None:
+        self.node = self.node.next
+        return self.node
+    raise StopIteration()
+  def __reversed__(self):
+    return DoublyLinkedListIterator(self.node, not self.reverse)
+
+class ListNode(object):
+  def __init__(self, val, next, prev):
+    self.val = val
+    self.next = next
+    self.prev = prev 
+
+  def __iter__(self):
+    return DoublyLinkedListIterator(self)
+
+  def __reversed__(self):
+    return DoublyLinkedListIterator(self, reverse=True)
+
+  def __str__(self):
+    return "ListNode({},{},{})".format(
+      self.val, 
+      self.next.val if self.next is not None else None,
+      self.prev.val if self.prev is not None else None
+    )
+
+  def clone(self):
+    return ListNode(self.val, self.next, self.prev)
+
+class DoublyLinkedList(object):
+  def __init__(self):
+    self.head = None
+    self.tail = None
+    self.size = 0
+
+  @classmethod
+  def create(cls, lst):
+    lst = iter(lst)
+
+    dll = DoublyLinkedList()
+    for val in lst:
+      dll.append(val)
+
+    return dll
+
+  def __len__(self):
+    return self.size
+
+  def __iter__(self):
+    return DoublyLinkedListIterator(self.head)
+
+  def __reversed__(self):
+    return DoublyLinkedListIterator(self.tail, reverse=True)
+
+  def tolist(self):
+    return [ x.val for x in self ]
+
+  def is_empty(self):
+    return self.head is None and self.tail is None
+
+  def peek_head(self):
+    if self.head is None:
+      return None
+    return self.head.val
+
+  def peek_tail(self):
+    if self.tail is None:
+      return None
+    return self.tail.val
+
+  def promote_to_head(self, node):
+    self.delete(node)
+
+    if self.head is None:
+      self.head = node
+      node.next = None 
+      node.prev = None
+      self.tail = node
+    else:
+      head = self.head
+      head.prev = node
+      self.head = node
+      node.prev = None 
+      node.next = head
+
+    self.size += 1
+
+  def delete(self, node):
+    nxt, prev = node.next, node.prev
+
+    if prev is not None:
+      prev.next = nxt
+
+    if nxt is not None:
+      nxt.prev = prev
+
+    self.size -= 1
+
+    return node
+
+  def delete_tail(self):
+    if self.tail is None:
+      return None
+    elif self.tail == self.head:
+      val = self.tail.val
+      self.tail = None
+      self.head = None
+      self.size = 0
+      return val
+
+    node = self.tail
+    self.tail = node.prev
+    self.tail.next = None
+
+    self.size -= 1
+
+    return node.val
+
+  def prepend(self, val):
+    if self.head is None and self.tail is None:
+      self.head = ListNode(val, None, None)
+      self.tail = self.head
+    elif self.head is None:
+      self.head = ListNode(val, self.tail, None)
+      self.tail.prev = self.head
+    else:
+      self.head = ListNode(val, self.head, None)
+      self.head.next.prev = self.head
+
+    self.size += 1
+
+    return self
+
+  def append(self, val):
+    if self.head is None and self.tail is None:
+      self.head = ListNode(val, None, None)
+      self.tail = self.head
+    elif self.tail is None:
+      self.tail = ListNode(val, None, self.head)
+      self.head.next = self.tail
+    else:
+      self.tail = ListNode(val, None, self.tail)
+      self.tail.prev.next = self.tail
+
+    self.size += 1
+
+    return self
+
+  def __str__(self):
+    return str([ n.val for n in self ])
+
+class LRU(object):
+  def __init__(self, size=100):
+    self.size = size
+    self.queue = DoublyLinkedList()
+    self.hash = {}
+
+  def __len__(self):
+    return self.queue.size
+
+  def resize(self, new_size):
+    if new_size < 0:
+      raise ValueError("The LRU limit must be a positive number. Got: " + str(new_size))
+
+    if new_size == 0:
+      self.queue = DoublyLinkedList()
+      self.hash = {}
+      return
+
+    if new_size >= self.size:
+      self.size = new_size
+      return 
+
+    while len(self.queue) > new_size:
+      (key,val) = self.queue.delete_tail()
+      del self.hash[key]
+
+  def __contains__(self, key):
+    return key in self.hash
+
+  def __getitem__(self, key):
+    if key not in self.hash:
+      raise KeyError("{} not in cache.".format(key))
+
+    node = self.hash[key]
+    self.queue.promote_to_head(node)
+
+    return node.val[1]
+
+  def __setitem__(self, key, val):
+    pair = (key,val)
+    if key in self.hash:
+      node = self.hash[key]
+      node.val = pair
+      self.queue.promote_to_head(node)
+      return
+
+    self.queue.prepend(pair)
+    self.hash[key] = self.queue.head
+
+    while len(self.queue) > self.size:
+      (tkey,tval) = self.queue.delete_tail()
+      del self.hash[tkey]      
+
+  def __str__(self):
+    return str(self.queue)
+
+
+
diff --git a/requirements.txt b/requirements.txt
index b4d6a09..d6e3145 100644
--- a/requirements.txt
+++ b/requirements.txt
@@ -13,7 +13,6 @@ numpy>=1.13.3
 python-jsonschema-objects>=0.3.3
 Pillow>=4.2.1
 protobuf>=3.3.0
-pylru
 python-dateutil
 requests>=2.22.0
 six>=1.10.0


Test patch:
diff --git a/test/test_lru.py b/test/test_lru.py
new file mode 100644
index 0000000..b5601f8
--- /dev/null
+++ b/test/test_lru.py
@@ -0,0 +1,36 @@
+from cloudvolume.lru import LRU
+
+def test_lru():
+  lru = LRU(5)
+
+  assert len(lru) == 0
+  for i in range(5):
+    lru[i] = i
+  assert len(lru) == 5
+
+  for i in range(5):
+    lru[i] = i
+
+  for i in range(100):
+    lru[i] = i
+
+  assert len(lru) == 5
+
+  lru.resize(10)
+  for i in range(5):
+    lru[i] = i
+
+  assert lru.queue.tolist() == [ 
+    (4,4), (3,3), (2,2), (1,1), (0,0),
+    (99,99), (98,98), (97,97), (96,96), (95,95)
+  ]
+
+  lru.resize(5)
+  assert lru.queue.tolist() == [ 
+    (4,4), (3,3), (2,2), (1,1), (0,0)
+  ]
+
+  assert lru[0] == 0
+  assert lru.queue.tolist() == [ 
+    (0,0), (4,4), (3,3), (2,2), (1,1)
+  ]