Changeset 661 for branches

Timestamp:

05/25/13 11:01:42 (3 years ago)

Author:

mmckerns

Message:

merged all the new cache functions into a single file;
added simple _test_hits to check cache effectiveness

Location:

branches/decorate

Files:

• INF_cache.py (deleted)
• LFU_cache.py (deleted)
• MRU_cache.py (deleted)
• NO_cache.py (deleted)
• RR_cache.py (deleted)
• cache.py (moved) (moved from branches/decorate/LRU_cache.py) (2 diffs)

branches/decorate/cache.py

@@ +1 @@
+# 
+
 import collections
+from random import choice #XXX: biased?
+from heapq import nsmallest
+from operator import itemgetter
+from itertools import ifilterfalse
 from functools import update_wrapper
 from threading import RLock
-from itertools import ifilterfalse
 from cache_helper import _CacheInfo, Counter, hashmap as _keymap
 from INF_cache import inf_cache
 from NO_cache import no_cache
+
+
+def no_cache(*arg, **kwd):
+    '''empty cache decorator.
+
+    View the cache statistics named tuple (hits, misses, maxsize, currsize) with
+    f.info().  Clear the cache and statistics with f.clear().  Access the
+    underlying function with f.__wrapped__.  This function does not cache, but
+    is a dummy that collects statistics and conforms to the caching interface.
+
+    '''
+    maxsize = 0
+    cache = dict() #XXX: tuple, None, ...?
+
+    def decorating_function(user_function):
+        stats = [0, 0]                  # make statistics updateable non-locally
+        HITS, MISSES = 0, 1             # names for the stats fields
+        _len = len                      # localize the global len() function
+       #lock = RLock()                  # linkedlist updates aren't threadsafe
+
+        def wrapper(*args, **kwds):
+            # compute
+            result = user_function(*args, **kwds)
+            stats[MISSES] += 1
+            return result
+
+        def clear():
+            """Clear the cache and statistics"""
+            stats[:] = [0, 0]
+
+        def info():
+            """Report cache statistics"""
+            return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache))
+
+        # interface
+        wrapper.__wrapped__ = user_function
+        wrapper.info = info
+        wrapper.clear = clear
+       #wrapper._cache = None  #XXX
+       #wrapper._queue = None  #XXX
+        return update_wrapper(wrapper, user_function)
+
+    return decorating_function
+
+
+def inf_cache(*arg, **kwd):
+    '''Infinitely-growing cache decorator.
+
+    If *typed* is True, arguments of different types will be cached separately.
+    For example, f(3.0) and f(3) will be treated as distinct calls with
+    distinct results.  Cache typing has a memory penalty, and may also may be
+    ignored by some 'keymaps'.
+
+    If *keymap* is given, it will replace the hashing algorithm for generating
+    cache keys.  For example, see the other hashing algorithms available in
+    'cache_helper.py'. With the default keymap, arguments to the cached
+    function must be hashable.
+
+    View the cache statistics named tuple (hits, misses, maxsize, currsize) with
+    f.info().  Clear the cache and statistics with f.clear().  Access the
+    underlying function with f.__wrapped__.  This cache will grow without bound.
+
+    '''
+    maxsize = None
+    make_key = kwd.get('keymap', _keymap)
+    typed = kwd.get('typed', False)
+
+    def decorating_function(user_function):
+        cache = dict()                  # mapping of args to results
+        stats = [0, 0]                  # make statistics updateable non-locally
+        HITS, MISSES = 0, 1             # names for the stats fields
+       #_len = len                      # localize the global len() function
+       #lock = RLock()                  # linkedlist updates aren't threadsafe
+
+        def wrapper(*args, **kwds):
+            key = make_key(args, kwds, typed)
+
+            # get cache entry or compute if not found
+            try:
+                result = cache[key]
+                stats[HITS] += 1
+            except KeyError:
+                result = user_function(*args, **kwds)
+                cache[key] = result
+                stats[MISSES] += 1
+            return result
+
+        def clear():
+            """Clear the cache and statistics"""
+            cache.clear()
+            stats[:] = [0, 0]
+
+        def info():
+            """Report cache statistics"""
+            return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache))
+
+        # interface
+        wrapper.__wrapped__ = user_function
+        wrapper.info = info
+        wrapper.clear = clear
+       #wrapper._cache = cache #XXX
+       #wrapper._queue = None  #XXX
+        return update_wrapper(wrapper, user_function)
+
+    return decorating_function
+
+
+def lfu_cache(maxsize=100, keymap=None, typed=False):
+    '''Least-frequenty-used cache decorator.
+
+    If *maxsize* is None, the LFU algorithm will be supressed and this cache
+    will grow without bound.
+
+    If *typed* is True, arguments of different types will be cached separately.
+    For example, f(3.0) and f(3) will be treated as distinct calls with
+    distinct results.  Cache typing has a memory penalty, and may also may be
+    ignored by some 'keymaps'.
+
+    If *keymap* is given, it will replace the hashing algorithm for generating
+    cache keys.  For example, see the other hashing algorithms available in
+    'cache_helper.py'. With the default keymap, arguments to the cached
+    function must be hashable.
+
+    View the cache statistics named tuple (hits, misses, maxsize, currsize) with
+    f.info().  Clear the cache and statistics with f.clear().  Access the
+    underlying function with f.__wrapped__.
+
+    See: http://en.wikipedia.org/wiki/Cache_algorithms#Least_Frequently_Used
+
+    '''
+    if maxsize == 0: return no_cache()
+    if keymap is None: make_key = _keymap
+    else: make_key = keymap
+    if maxsize is None: return inf_cache(keymap=make_key, typed=typed)
+    
+    def decorating_function(user_function):
+        cache = dict()                  # mapping of args to results
+        use_count = Counter()           # times each key has been accessed
+        stats = [0, 0]                  # make statistics updateable non-locally
+        HITS, MISSES = 0, 1             # names for the stats fields
+        _len = len                      # localize the global len() function
+       #lock = RLock()                  # linkedlist updates aren't threadsafe
+
+        def wrapper(*args, **kwds):
+            key = make_key(args, kwds, typed)
+
+            # get cache entry or compute if not found
+            try:
+                result = cache[key]
+                use_count[key] += 1
+                stats[HITS] += 1
+            except KeyError:
+                cache[key] = user_function(*args, **kwds)
+                # need to add something to the cache, make room if necessary
+                if _len(cache) == maxsize:
+                    for k, _ in nsmallest(maxsize // 10 or 1,
+                                          use_count.iteritems(),
+                                          key=itemgetter(1)):
+                        del cache[k], use_count[k]
+                result = cache[key]
+                use_count[key] += 1
+                stats[MISSES] += 1
+            return result
+
+        def clear():
+            """Clear the cache and statistics"""
+            cache.clear()
+            use_count.clear()
+            stats[:] = [0, 0]
+
+        def info():
+            """Report cache statistics"""
+            return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache))
+
+        # interface
+        wrapper.__wrapped__ = user_function
+        wrapper.info = info
+        wrapper.clear = clear
+       #wrapper._cache = cache #XXX
+       #wrapper._queue = use_count #XXX
+        return update_wrapper(wrapper, user_function)
+
+    return decorating_function
+
 
 def lru_cache(maxsize=100, keymap=None, typed=False):
@@ -110 +299 @@
 
 
-if __name__ == '__main__':
-
-    @lru_cache(maxsize=20, typed=True)
+def mru_cache(maxsize=100, keymap=None, typed=False):
+    '''Most-recently-used cache decorator.
+
+    If *maxsize* is None, the MRU algorithm will be supressed and this cache
+    will grow without bound.
+
+    If *typed* is True, arguments of different types will be cached separately.
+    For example, f(3.0) and f(3) will be treated as distinct calls with
+    distinct results.  Cache typing has a memory penalty, and may also may be
+    ignored by some 'keymaps'.
+
+    If *keymap* is given, it will replace the hashing algorithm for generating
+    cache keys.  For example, see the other hashing algorithms available in
+    'cache_helper.py'. With the default keymap, arguments to the cached
+    function must be hashable.
+
+    View the cache statistics named tuple (hits, misses, maxsize, currsize) with
+    f.info().  Clear the cache and statistics with f.clear().  Access the
+    underlying function with f.__wrapped__.
+
+    See: http://en.wikipedia.org/wiki/Cache_algorithms#Most_Recently_Used
+
+    '''
+    if maxsize == 0: return no_cache()
+    if keymap is None: make_key = _keymap
+    else: make_key = keymap
+    if maxsize is None: return inf_cache(keymap=make_key, typed=typed)
+
+    def decorating_function(user_function):
+        cache = dict()                  # mapping of args to results
+        queue = collections.deque()     # order that keys have been used
+        stats = [0, 0]                  # make statistics updateable non-locally
+        HITS, MISSES = 0, 1             # names for the stats fields
+        _len = len                      # localize the global len() function
+       #lock = RLock()                  # linkedlist updates aren't threadsafe
+
+        # lookup optimizations (ugly but fast)
+        queue_append, queue_popleft = queue.append, queue.popleft
+        queue_appendleft, queue_pop = queue.appendleft, queue.pop
+
+        def wrapper(*args, **kwds):
+            key = make_key(args, kwds, typed)
+
+            # get cache entry or compute if not found
+            try:
+                result = cache[key]
+                queue.remove(key)
+                stats[HITS] += 1
+            except KeyError:
+                result = user_function(*args, **kwds)
+                cache[key] = result
+                stats[MISSES] += 1
+
+                # purge most recently used cache entry
+                if _len(cache) > maxsize:
+                    del cache[queue_pop()]
+
+            # record recent use of this key
+            queue_append(key)
+            return result
+
+        def clear():
+            """Clear the cache and statistics"""
+            cache.clear()
+            queue.clear()
+            stats[:] = [0, 0]
+
+        def info():
+            """Report cache statistics"""
+            return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache))
+
+        # interface
+        wrapper.__wrapped__ = user_function
+        wrapper.info = info
+        wrapper.clear = clear
+       #wrapper._cache = cache #XXX
+       #wrapper._queue = queue #XXX
+        return update_wrapper(wrapper, user_function)
+
+    return decorating_function
+
+
+def rr_cache(maxsize=100, keymap=None, typed=False):
+    '''random-replacement cache decorator.
+
+    If *maxsize* is None, the RR algorithm will be supressed and this cache
+    will grow without bound.
+
+    If *typed* is True, arguments of different types will be cached separately.
+    For example, f(3.0) and f(3) will be treated as distinct calls with
+    distinct results.  Cache typing has a memory penalty, and may also may be
+    ignored by some 'keymaps'.
+
+    If *keymap* is given, it will replace the hashing algorithm for generating
+    cache keys.  For example, see the other hashing algorithms available in
+    'cache_helper.py'. With the default keymap, arguments to the cached
+    function must be hashable.
+
+    View the cache statistics named tuple (hits, misses, maxsize, currsize) with
+    f.info().  Clear the cache and statistics with f.clear().  Access the
+    underlying function with f.__wrapped__.
+
+    http://en.wikipedia.org/wiki/Cache_algorithms#Random_Replacement
+
+    '''
+    if maxsize == 0: return no_cache()
+    if keymap is None: make_key = _keymap
+    else: make_key = keymap
+    if maxsize is None: return inf_cache(keymap=make_key, typed=typed)
+
+    def decorating_function(user_function):
+        cache = dict()                  # mapping of args to results
+        stats = [0, 0]                  # make statistics updateable non-locally
+        HITS, MISSES = 0, 1             # names for the stats fields
+        _len = len                      # localize the global len() function
+       #lock = RLock()                  # linkedlist updates aren't threadsafe
+
+        def wrapper(*args, **kwds):
+            key = make_key(args, kwds, typed)
+
+            # get cache entry or compute if not found
+            try:
+                result = cache[key]
+                stats[HITS] += 1
+            except KeyError:
+                result = user_function(*args, **kwds)
+                cache[key] = result
+                stats[MISSES] += 1
+
+                # purge random cache entry
+                if _len(cache) > maxsize:
+                    del cache[choice(cache.keys())]
+            return result
+
+        def clear():
+            """Clear the cache and statistics"""
+            cache.clear()
+            stats[:] = [0, 0]
+
+        def info():
+            """Report cache statistics"""
+            return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache))
+
+        # interface
+        wrapper.__wrapped__ = user_function
+        wrapper.info = info
+        wrapper.clear = clear
+       #wrapper._cache = cache #XXX
+       #wrapper._queue = None  #XXX
+        return update_wrapper(wrapper, user_function)
+
+    return decorating_function
+
+
+def _test_hits(algorithm, maxsize=20, typed=False, rangelimit=5, tries=1000):
+
+    @algorithm(maxsize=maxsize, typed=typed)
     def f(x, y):
         return 3*x+y
 
-    domain = range(5)
+    domain = range(rangelimit)
     domain += [float(i) for i in domain]
     from random import choice
-    for i in range(1000):
+    for i in range(tries):
         r = f(choice(domain), choice(domain))
 
     print (f.info())
 
+
+if __name__ == '__main__':
+
+    for cache in [rr_cache, mru_cache, lru_cache, lfu_cache, inf_cache]:
+        print cache.__name__, ":", 
+        _test_hits(cache, maxsize=1000, rangelimit=50)
+
+
+# EOF