[Python-checkins] cpython: No need to create and destroy links when updating a fixed-sized circular queue.

[raymond.hettinger]

http://hg.python.org/cpython/rev/476f641a0455
changeset:   76002:476f641a0455
parent:      76000:7ad1728691b2
user:        Raymond Hettinger <python at rcn.com>
date:        Fri Mar 30 19:15:18 2012 -0700
summary:
  No need to create and destroy links when updating a fixed-sized circular queue.

files:
  Lib/functools.py |  27 ++++++++++++++++-----------
  1 files changed, 16 insertions(+), 11 deletions(-)


diff --git a/Lib/functools.py b/Lib/functools.py
--- a/Lib/functools.py
+++ b/Lib/functools.py
@@ -219,7 +219,7 @@
 
             def wrapper(*args, **kwds):
                 # size limited caching that tracks accesses by recency
-                nonlocal hits, misses
+                nonlocal root, hits, misses
                 key = make_key(args, kwds, typed) if kwds or typed else args
                 with lock:
                     link = cache_get(key)
@@ -236,16 +236,21 @@
                         return result
                 result = user_function(*args, **kwds)
                 with lock:
-                    # put result in a new link at the front of the list
-                    last = root[PREV]
-                    link = [last, root, key, result]
-                    cache[key] = last[NEXT] = root[PREV] = link
-                    if _len(cache) > maxsize:
-                        # purge the least recently used cache entry
-                        old_prev, old_next, old_key, old_result = root[NEXT]
-                        root[NEXT] = old_next
-                        old_next[PREV] = root
-                        del cache[old_key]
+                    if _len(cache) < maxsize:
+                        # put result in a new link at the front of the list
+                        last = root[PREV]
+                        link = [last, root, key, result]
+                        cache[key] = last[NEXT] = root[PREV] = link
+                    else:
+                        # use root to store the new key and result
+                        root[KEY] = key
+                        root[RESULT] = result
+                        cache[key] = root
+                        # empty the oldest link and make it the new root
+                        root = root[NEXT]
+                        del cache[root[KEY]]
+                        root[KEY] = None
+                        root[RESULT] = None
                     misses += 1
                 return result
 

-- 
Repository URL: http://hg.python.org/cpython