Changeset 661 for branches


Ignore:
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:
5 deleted
1 moved

Legend:

Unmodified
Added
Removed
  • branches/decorate/cache.py

    r660 r661  
     1#  
     2 
    13import collections 
     4from random import choice #XXX: biased? 
     5from heapq import nsmallest 
     6from operator import itemgetter 
     7from itertools import ifilterfalse 
    28from functools import update_wrapper 
    39from threading import RLock 
    4 from itertools import ifilterfalse 
    510from cache_helper import _CacheInfo, Counter, hashmap as _keymap 
    611from INF_cache import inf_cache 
    712from NO_cache import no_cache 
     13 
     14 
     15def no_cache(*arg, **kwd): 
     16    '''empty cache decorator. 
     17 
     18    View the cache statistics named tuple (hits, misses, maxsize, currsize) with 
     19    f.info().  Clear the cache and statistics with f.clear().  Access the 
     20    underlying function with f.__wrapped__.  This function does not cache, but 
     21    is a dummy that collects statistics and conforms to the caching interface. 
     22 
     23    ''' 
     24    maxsize = 0 
     25    cache = dict() #XXX: tuple, None, ...? 
     26 
     27    def decorating_function(user_function): 
     28        stats = [0, 0]                  # make statistics updateable non-locally 
     29        HITS, MISSES = 0, 1             # names for the stats fields 
     30        _len = len                      # localize the global len() function 
     31       #lock = RLock()                  # linkedlist updates aren't threadsafe 
     32 
     33        def wrapper(*args, **kwds): 
     34            # compute 
     35            result = user_function(*args, **kwds) 
     36            stats[MISSES] += 1 
     37            return result 
     38 
     39        def clear(): 
     40            """Clear the cache and statistics""" 
     41            stats[:] = [0, 0] 
     42 
     43        def info(): 
     44            """Report cache statistics""" 
     45            return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache)) 
     46 
     47        # interface 
     48        wrapper.__wrapped__ = user_function 
     49        wrapper.info = info 
     50        wrapper.clear = clear 
     51       #wrapper._cache = None  #XXX 
     52       #wrapper._queue = None  #XXX 
     53        return update_wrapper(wrapper, user_function) 
     54 
     55    return decorating_function 
     56 
     57 
     58def inf_cache(*arg, **kwd): 
     59    '''Infinitely-growing cache decorator. 
     60 
     61    If *typed* is True, arguments of different types will be cached separately. 
     62    For example, f(3.0) and f(3) will be treated as distinct calls with 
     63    distinct results.  Cache typing has a memory penalty, and may also may be 
     64    ignored by some 'keymaps'. 
     65 
     66    If *keymap* is given, it will replace the hashing algorithm for generating 
     67    cache keys.  For example, see the other hashing algorithms available in 
     68    'cache_helper.py'. With the default keymap, arguments to the cached 
     69    function must be hashable. 
     70 
     71    View the cache statistics named tuple (hits, misses, maxsize, currsize) with 
     72    f.info().  Clear the cache and statistics with f.clear().  Access the 
     73    underlying function with f.__wrapped__.  This cache will grow without bound. 
     74 
     75    ''' 
     76    maxsize = None 
     77    make_key = kwd.get('keymap', _keymap) 
     78    typed = kwd.get('typed', False) 
     79 
     80    def decorating_function(user_function): 
     81        cache = dict()                  # mapping of args to results 
     82        stats = [0, 0]                  # make statistics updateable non-locally 
     83        HITS, MISSES = 0, 1             # names for the stats fields 
     84       #_len = len                      # localize the global len() function 
     85       #lock = RLock()                  # linkedlist updates aren't threadsafe 
     86 
     87        def wrapper(*args, **kwds): 
     88            key = make_key(args, kwds, typed) 
     89 
     90            # get cache entry or compute if not found 
     91            try: 
     92                result = cache[key] 
     93                stats[HITS] += 1 
     94            except KeyError: 
     95                result = user_function(*args, **kwds) 
     96                cache[key] = result 
     97                stats[MISSES] += 1 
     98            return result 
     99 
     100        def clear(): 
     101            """Clear the cache and statistics""" 
     102            cache.clear() 
     103            stats[:] = [0, 0] 
     104 
     105        def info(): 
     106            """Report cache statistics""" 
     107            return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache)) 
     108 
     109        # interface 
     110        wrapper.__wrapped__ = user_function 
     111        wrapper.info = info 
     112        wrapper.clear = clear 
     113       #wrapper._cache = cache #XXX 
     114       #wrapper._queue = None  #XXX 
     115        return update_wrapper(wrapper, user_function) 
     116 
     117    return decorating_function 
     118 
     119 
     120def lfu_cache(maxsize=100, keymap=None, typed=False): 
     121    '''Least-frequenty-used cache decorator. 
     122 
     123    If *maxsize* is None, the LFU algorithm will be supressed and this cache 
     124    will grow without bound. 
     125 
     126    If *typed* is True, arguments of different types will be cached separately. 
     127    For example, f(3.0) and f(3) will be treated as distinct calls with 
     128    distinct results.  Cache typing has a memory penalty, and may also may be 
     129    ignored by some 'keymaps'. 
     130 
     131    If *keymap* is given, it will replace the hashing algorithm for generating 
     132    cache keys.  For example, see the other hashing algorithms available in 
     133    'cache_helper.py'. With the default keymap, arguments to the cached 
     134    function must be hashable. 
     135 
     136    View the cache statistics named tuple (hits, misses, maxsize, currsize) with 
     137    f.info().  Clear the cache and statistics with f.clear().  Access the 
     138    underlying function with f.__wrapped__. 
     139 
     140    See: http://en.wikipedia.org/wiki/Cache_algorithms#Least_Frequently_Used 
     141 
     142    ''' 
     143    if maxsize == 0: return no_cache() 
     144    if keymap is None: make_key = _keymap 
     145    else: make_key = keymap 
     146    if maxsize is None: return inf_cache(keymap=make_key, typed=typed) 
     147     
     148    def decorating_function(user_function): 
     149        cache = dict()                  # mapping of args to results 
     150        use_count = Counter()           # times each key has been accessed 
     151        stats = [0, 0]                  # make statistics updateable non-locally 
     152        HITS, MISSES = 0, 1             # names for the stats fields 
     153        _len = len                      # localize the global len() function 
     154       #lock = RLock()                  # linkedlist updates aren't threadsafe 
     155 
     156        def wrapper(*args, **kwds): 
     157            key = make_key(args, kwds, typed) 
     158 
     159            # get cache entry or compute if not found 
     160            try: 
     161                result = cache[key] 
     162                use_count[key] += 1 
     163                stats[HITS] += 1 
     164            except KeyError: 
     165                cache[key] = user_function(*args, **kwds) 
     166                # need to add something to the cache, make room if necessary 
     167                if _len(cache) == maxsize: 
     168                    for k, _ in nsmallest(maxsize // 10 or 1, 
     169                                          use_count.iteritems(), 
     170                                          key=itemgetter(1)): 
     171                        del cache[k], use_count[k] 
     172                result = cache[key] 
     173                use_count[key] += 1 
     174                stats[MISSES] += 1 
     175            return result 
     176 
     177        def clear(): 
     178            """Clear the cache and statistics""" 
     179            cache.clear() 
     180            use_count.clear() 
     181            stats[:] = [0, 0] 
     182 
     183        def info(): 
     184            """Report cache statistics""" 
     185            return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache)) 
     186 
     187        # interface 
     188        wrapper.__wrapped__ = user_function 
     189        wrapper.info = info 
     190        wrapper.clear = clear 
     191       #wrapper._cache = cache #XXX 
     192       #wrapper._queue = use_count #XXX 
     193        return update_wrapper(wrapper, user_function) 
     194 
     195    return decorating_function 
     196 
    8197 
    9198def lru_cache(maxsize=100, keymap=None, typed=False): 
     
    110299 
    111300 
    112 if __name__ == '__main__': 
    113  
    114     @lru_cache(maxsize=20, typed=True) 
     301def mru_cache(maxsize=100, keymap=None, typed=False): 
     302    '''Most-recently-used cache decorator. 
     303 
     304    If *maxsize* is None, the MRU algorithm will be supressed and this cache 
     305    will grow without bound. 
     306 
     307    If *typed* is True, arguments of different types will be cached separately. 
     308    For example, f(3.0) and f(3) will be treated as distinct calls with 
     309    distinct results.  Cache typing has a memory penalty, and may also may be 
     310    ignored by some 'keymaps'. 
     311 
     312    If *keymap* is given, it will replace the hashing algorithm for generating 
     313    cache keys.  For example, see the other hashing algorithms available in 
     314    'cache_helper.py'. With the default keymap, arguments to the cached 
     315    function must be hashable. 
     316 
     317    View the cache statistics named tuple (hits, misses, maxsize, currsize) with 
     318    f.info().  Clear the cache and statistics with f.clear().  Access the 
     319    underlying function with f.__wrapped__. 
     320 
     321    See: http://en.wikipedia.org/wiki/Cache_algorithms#Most_Recently_Used 
     322 
     323    ''' 
     324    if maxsize == 0: return no_cache() 
     325    if keymap is None: make_key = _keymap 
     326    else: make_key = keymap 
     327    if maxsize is None: return inf_cache(keymap=make_key, typed=typed) 
     328 
     329    def decorating_function(user_function): 
     330        cache = dict()                  # mapping of args to results 
     331        queue = collections.deque()     # order that keys have been used 
     332        stats = [0, 0]                  # make statistics updateable non-locally 
     333        HITS, MISSES = 0, 1             # names for the stats fields 
     334        _len = len                      # localize the global len() function 
     335       #lock = RLock()                  # linkedlist updates aren't threadsafe 
     336 
     337        # lookup optimizations (ugly but fast) 
     338        queue_append, queue_popleft = queue.append, queue.popleft 
     339        queue_appendleft, queue_pop = queue.appendleft, queue.pop 
     340 
     341        def wrapper(*args, **kwds): 
     342            key = make_key(args, kwds, typed) 
     343 
     344            # get cache entry or compute if not found 
     345            try: 
     346                result = cache[key] 
     347                queue.remove(key) 
     348                stats[HITS] += 1 
     349            except KeyError: 
     350                result = user_function(*args, **kwds) 
     351                cache[key] = result 
     352                stats[MISSES] += 1 
     353 
     354                # purge most recently used cache entry 
     355                if _len(cache) > maxsize: 
     356                    del cache[queue_pop()] 
     357 
     358            # record recent use of this key 
     359            queue_append(key) 
     360            return result 
     361 
     362        def clear(): 
     363            """Clear the cache and statistics""" 
     364            cache.clear() 
     365            queue.clear() 
     366            stats[:] = [0, 0] 
     367 
     368        def info(): 
     369            """Report cache statistics""" 
     370            return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache)) 
     371 
     372        # interface 
     373        wrapper.__wrapped__ = user_function 
     374        wrapper.info = info 
     375        wrapper.clear = clear 
     376       #wrapper._cache = cache #XXX 
     377       #wrapper._queue = queue #XXX 
     378        return update_wrapper(wrapper, user_function) 
     379 
     380    return decorating_function 
     381 
     382 
     383def rr_cache(maxsize=100, keymap=None, typed=False): 
     384    '''random-replacement cache decorator. 
     385 
     386    If *maxsize* is None, the RR algorithm will be supressed and this cache 
     387    will grow without bound. 
     388 
     389    If *typed* is True, arguments of different types will be cached separately. 
     390    For example, f(3.0) and f(3) will be treated as distinct calls with 
     391    distinct results.  Cache typing has a memory penalty, and may also may be 
     392    ignored by some 'keymaps'. 
     393 
     394    If *keymap* is given, it will replace the hashing algorithm for generating 
     395    cache keys.  For example, see the other hashing algorithms available in 
     396    'cache_helper.py'. With the default keymap, arguments to the cached 
     397    function must be hashable. 
     398 
     399    View the cache statistics named tuple (hits, misses, maxsize, currsize) with 
     400    f.info().  Clear the cache and statistics with f.clear().  Access the 
     401    underlying function with f.__wrapped__. 
     402 
     403    http://en.wikipedia.org/wiki/Cache_algorithms#Random_Replacement 
     404 
     405    ''' 
     406    if maxsize == 0: return no_cache() 
     407    if keymap is None: make_key = _keymap 
     408    else: make_key = keymap 
     409    if maxsize is None: return inf_cache(keymap=make_key, typed=typed) 
     410 
     411    def decorating_function(user_function): 
     412        cache = dict()                  # mapping of args to results 
     413        stats = [0, 0]                  # make statistics updateable non-locally 
     414        HITS, MISSES = 0, 1             # names for the stats fields 
     415        _len = len                      # localize the global len() function 
     416       #lock = RLock()                  # linkedlist updates aren't threadsafe 
     417 
     418        def wrapper(*args, **kwds): 
     419            key = make_key(args, kwds, typed) 
     420 
     421            # get cache entry or compute if not found 
     422            try: 
     423                result = cache[key] 
     424                stats[HITS] += 1 
     425            except KeyError: 
     426                result = user_function(*args, **kwds) 
     427                cache[key] = result 
     428                stats[MISSES] += 1 
     429 
     430                # purge random cache entry 
     431                if _len(cache) > maxsize: 
     432                    del cache[choice(cache.keys())] 
     433            return result 
     434 
     435        def clear(): 
     436            """Clear the cache and statistics""" 
     437            cache.clear() 
     438            stats[:] = [0, 0] 
     439 
     440        def info(): 
     441            """Report cache statistics""" 
     442            return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache)) 
     443 
     444        # interface 
     445        wrapper.__wrapped__ = user_function 
     446        wrapper.info = info 
     447        wrapper.clear = clear 
     448       #wrapper._cache = cache #XXX 
     449       #wrapper._queue = None  #XXX 
     450        return update_wrapper(wrapper, user_function) 
     451 
     452    return decorating_function 
     453 
     454 
     455def _test_hits(algorithm, maxsize=20, typed=False, rangelimit=5, tries=1000): 
     456 
     457    @algorithm(maxsize=maxsize, typed=typed) 
    115458    def f(x, y): 
    116459        return 3*x+y 
    117460 
    118     domain = range(5) 
     461    domain = range(rangelimit) 
    119462    domain += [float(i) for i in domain] 
    120463    from random import choice 
    121     for i in range(1000): 
     464    for i in range(tries): 
    122465        r = f(choice(domain), choice(domain)) 
    123466 
    124467    print (f.info()) 
    125468 
     469 
     470if __name__ == '__main__': 
     471 
     472    for cache in [rr_cache, mru_cache, lru_cache, lfu_cache, inf_cache]: 
     473        print cache.__name__, ":",  
     474        _test_hits(cache, maxsize=1000, rangelimit=50) 
     475 
     476 
     477# EOF 
Note: See TracChangeset for help on using the changeset viewer.