Rev 4182: Shave off approx 100ms by inlining _record_access into __getitem__, in lp:///~jameinel/bzr/lru_cache_linked_lst

[John Arbash Meinel]

At lp:///~jameinel/bzr/lru_cache_linked_lst

------------------------------------------------------------
revno: 4182
revision-id: john at arbash-meinel.com-20090322191330-bbueodlalhf0onzh
parent: john at arbash-meinel.com-20090322190503-wabx7fjrgarxx9c5
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: lru_cache_linked_lst
timestamp: Sun 2009-03-22 14:13:30 -0500
message:
  Shave off approx 100ms by inlining _record_access into __getitem__,
  also, play some tricks with member access, so that we don't pay double lookup costs
  when we can avoid it.
-------------- next part --------------
=== modified file 'bzrlib/lru_cache.py'
--- a/bzrlib/lru_cache.py	2009-03-22 19:05:03 +0000
+++ b/bzrlib/lru_cache.py	2009-03-22 19:13:30 +0000
@@ -80,9 +80,29 @@
 
     def __getitem__(self, key):
         node = self._cache[key]
-        # TODO: We may want to inline _record_access, to decrease the cost of
-        #       __getitem__ calls
-        self._record_access(node)
+        # Inlined from _record_access to decrease the overhead of __getitem__
+        # We also have more knowledge about structure if __getitem__ is
+        # succeeding, then we know that self._most_recently_used must not be
+        # None, etc.
+        mru = self._most_recently_used
+        if node is mru:
+            # Nothing to do, this node is already at the head of the queue
+            return node.value
+        elif node is self._last_recently_used:
+            assert node.prev is not None
+            self._last_recently_used = node.prev
+        # Remove this node from the old location
+        node_prev = node.prev
+        node_next = node.next
+        if node_prev is not None:
+            node_prev.next = node_next
+        if node_next is not None:
+            node_next.prev = node_prev
+        # Insert this node to the front of the list
+        node.next = mru
+        mru.prev = node
+        self._most_recently_used = node
+        node.prev = None
         return node.value
 
     def __len__(self):
@@ -138,6 +158,8 @@
         node = self._cache.get(key, None)
         if node is None:
             return default
+        # XXX: We need a test for this
+        # self._record_access(node)
         return node.value
 
     def keys(self):