Issue #14373: Added C implementation of functools.lru_cache(). Based on

patches by Matt Joiner and Alexey Kachayev.

1 files changed, 108 insertions, 99 deletions

diff --git a/Lib/functools.py b/Lib/functools.py
index 19c25e1c05..09df068020 100644
--- a/Lib/functools.py
+++ b/Lib/functools.py
@@ -419,120 +419,129 @@ def lru_cache(maxsize=128, typed=False):
     if maxsize is not None and not isinstance(maxsize, int):
         raise TypeError('Expected maxsize to be an integer or None')
 
+    def decorating_function(user_function):
+        wrapper = _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo)
+        return update_wrapper(wrapper, user_function)
+
+    return decorating_function
+
+def _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo):
     # Constants shared by all lru cache instances:
     sentinel = object()          # unique object used to signal cache misses
     make_key = _make_key         # build a key from the function arguments
     PREV, NEXT, KEY, RESULT = 0, 1, 2, 3   # names for the link fields
 
-    def decorating_function(user_function):
-        cache = {}
-        hits = misses = 0
-        full = False
-        cache_get = cache.get    # bound method to lookup a key or return None
-        lock = RLock()           # because linkedlist updates aren't threadsafe
-        root = []                # root of the circular doubly linked list
-        root[:] = [root, root, None, None]     # initialize by pointing to self
-
-        if maxsize == 0:
-
-            def wrapper(*args, **kwds):
-                # No caching -- just a statistics update after a successful call
-                nonlocal misses
-                result = user_function(*args, **kwds)
-                misses += 1
+    cache = {}
+    hits = misses = 0
+    full = False
+    cache_get = cache.get    # bound method to lookup a key or return None
+    lock = RLock()           # because linkedlist updates aren't threadsafe
+    root = []                # root of the circular doubly linked list
+    root[:] = [root, root, None, None]     # initialize by pointing to self
+
+    if maxsize == 0:
+
+        def wrapper(*args, **kwds):
+            # No caching -- just a statistics update after a successful call
+            nonlocal misses
+            result = user_function(*args, **kwds)
+            misses += 1
+            return result
+
+    elif maxsize is None:
+
+        def wrapper(*args, **kwds):
+            # Simple caching without ordering or size limit
+            nonlocal hits, misses
+            key = make_key(args, kwds, typed)
+            result = cache_get(key, sentinel)
+            if result is not sentinel:
+                hits += 1
                 return result
+            result = user_function(*args, **kwds)
+            cache[key] = result
+            misses += 1
+            return result
 
-        elif maxsize is None:
+    else:
 
-            def wrapper(*args, **kwds):
-                # Simple caching without ordering or size limit
-                nonlocal hits, misses
-                key = make_key(args, kwds, typed)
-                result = cache_get(key, sentinel)
-                if result is not sentinel:
+        def wrapper(*args, **kwds):
+            # Size limited caching that tracks accesses by recency
+            nonlocal root, hits, misses, full
+            key = make_key(args, kwds, typed)
+            with lock:
+                link = cache_get(key)
+                if link is not None:
+                    # Move the link to the front of the circular queue
+                    link_prev, link_next, _key, result = link
+                    link_prev[NEXT] = link_next
+                    link_next[PREV] = link_prev
+                    last = root[PREV]
+                    last[NEXT] = root[PREV] = link
+                    link[PREV] = last
+                    link[NEXT] = root
                     hits += 1
                     return result
-                result = user_function(*args, **kwds)
-                cache[key] = result
+            result = user_function(*args, **kwds)
+            with lock:
+                if key in cache:
+                    # Getting here means that this same key was added to the
+                    # cache while the lock was released.  Since the link
+                    # update is already done, we need only return the
+                    # computed result and update the count of misses.
+                    pass
+                elif full:
+                    # Use the old root to store the new key and result.
+                    oldroot = root
+                    oldroot[KEY] = key
+                    oldroot[RESULT] = result
+                    # Empty the oldest link and make it the new root.
+                    # Keep a reference to the old key and old result to
+                    # prevent their ref counts from going to zero during the
+                    # update. That will prevent potentially arbitrary object
+                    # clean-up code (i.e. __del__) from running while we're
+                    # still adjusting the links.
+                    root = oldroot[NEXT]
+                    oldkey = root[KEY]
+                    oldresult = root[RESULT]
+                    root[KEY] = root[RESULT] = None
+                    # Now update the cache dictionary.
+                    del cache[oldkey]
+                    # Save the potentially reentrant cache[key] assignment
+                    # for last, after the root and links have been put in
+                    # a consistent state.
+                    cache[key] = oldroot
+                else:
+                    # Put result in a new link at the front of the queue.
+                    last = root[PREV]
+                    link = [last, root, key, result]
+                    last[NEXT] = root[PREV] = cache[key] = link
+                    full = (len(cache) >= maxsize)
                 misses += 1
-                return result
-
-        else:
-
-            def wrapper(*args, **kwds):
-                # Size limited caching that tracks accesses by recency
-                nonlocal root, hits, misses, full
-                key = make_key(args, kwds, typed)
-                with lock:
-                    link = cache_get(key)
-                    if link is not None:
-                        # Move the link to the front of the circular queue
-                        link_prev, link_next, _key, result = link
-                        link_prev[NEXT] = link_next
-                        link_next[PREV] = link_prev
-                        last = root[PREV]
-                        last[NEXT] = root[PREV] = link
-                        link[PREV] = last
-                        link[NEXT] = root
-                        hits += 1
-                        return result
-                result = user_function(*args, **kwds)
-                with lock:
-                    if key in cache:
-                        # Getting here means that this same key was added to the
-                        # cache while the lock was released.  Since the link
-                        # update is already done, we need only return the
-                        # computed result and update the count of misses.
-                        pass
-                    elif full:
-                        # Use the old root to store the new key and result.
-                        oldroot = root
-                        oldroot[KEY] = key
-                        oldroot[RESULT] = result
-                        # Empty the oldest link and make it the new root.
-                        # Keep a reference to the old key and old result to
-                        # prevent their ref counts from going to zero during the
-                        # update. That will prevent potentially arbitrary object
-                        # clean-up code (i.e. __del__) from running while we're
-                        # still adjusting the links.
-                        root = oldroot[NEXT]
-                        oldkey = root[KEY]
-                        oldresult = root[RESULT]
-                        root[KEY] = root[RESULT] = None
-                        # Now update the cache dictionary.
-                        del cache[oldkey]
-                        # Save the potentially reentrant cache[key] assignment
-                        # for last, after the root and links have been put in
-                        # a consistent state.
-                        cache[key] = oldroot
-                    else:
-                        # Put result in a new link at the front of the queue.
-                        last = root[PREV]
-                        link = [last, root, key, result]
-                        last[NEXT] = root[PREV] = cache[key] = link
-                        full = (len(cache) >= maxsize)
-                    misses += 1
-                return result
+            return result
 
-        def cache_info():
-            """Report cache statistics"""
-            with lock:
-                return _CacheInfo(hits, misses, maxsize, len(cache))
+    def cache_info():
+        """Report cache statistics"""
+        with lock:
+            return _CacheInfo(hits, misses, maxsize, len(cache))
 
-        def cache_clear():
-            """Clear the cache and cache statistics"""
-            nonlocal hits, misses, full
-            with lock:
-                cache.clear()
-                root[:] = [root, root, None, None]
-                hits = misses = 0
-                full = False
+    def cache_clear():
+        """Clear the cache and cache statistics"""
+        nonlocal hits, misses, full
+        with lock:
+            cache.clear()
+            root[:] = [root, root, None, None]
+            hits = misses = 0
+            full = False
 
-        wrapper.cache_info = cache_info
-        wrapper.cache_clear = cache_clear
-        return update_wrapper(wrapper, user_function)
+    wrapper.cache_info = cache_info
+    wrapper.cache_clear = cache_clear
+    return update_wrapper(wrapper, user_function)
 
-    return decorating_function
+try:
+    from _functools import _lru_cache_wrapper
+except ImportError:
+    pass
 
 
 ################################################################################