1# Copyright 2007 Matt Chaput. All rights reserved. 2# 3# Redistribution and use in source and binary forms, with or without 4# modification, are permitted provided that the following conditions are met: 5# 6# 1. Redistributions of source code must retain the above copyright notice, 7# this list of conditions and the following disclaimer. 8# 9# 2. Redistributions in binary form must reproduce the above copyright 10# notice, this list of conditions and the following disclaimer in the 11# documentation and/or other materials provided with the distribution. 12# 13# THIS SOFTWARE IS PROVIDED BY MATT CHAPUT ``AS IS'' AND ANY EXPRESS OR 14# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 15# MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO 16# EVENT SHALL MATT CHAPUT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 17# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 18# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, 19# OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 20# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 21# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 22# EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 23# 24# The views and conclusions contained in the software and documentation are 25# those of the authors and should not be interpreted as representing official 26# policies, either expressed or implied, of Matt Chaput. 27 28from __future__ import with_statement 29import functools, random 30from array import array 31from heapq import nsmallest 32from operator import itemgetter 33from threading import Lock 34from time import time 35 36from whoosh.compat import iteritems, xrange 37 38 39try: 40 from collections import Counter 41except ImportError: 42 class Counter(dict): 43 def __missing__(self, key): 44 return 0 45 46 47def unbound_cache(func): 48 """Caching decorator with an unbounded cache size. 49 """ 50 51 cache = {} 52 53 @functools.wraps(func) 54 def caching_wrapper(*args): 55 try: 56 return cache[args] 57 except KeyError: 58 result = func(*args) 59 cache[args] = result 60 return result 61 62 return caching_wrapper 63 64 65def lru_cache(maxsize=100): 66 """A simple cache that, when the cache is full, deletes the least recently 67 used 10% of the cached values. 68 69 This function duplicates (more-or-less) the protocol of the 70 ``functools.lru_cache`` decorator in the Python 3.2 standard library. 71 72 Arguments to the cached function must be hashable. 73 74 View the cache statistics tuple ``(hits, misses, maxsize, currsize)`` 75 with f.cache_info(). Clear the cache and statistics with f.cache_clear(). 76 Access the underlying function with f.__wrapped__. 77 """ 78 79 def decorating_function(user_function): 80 stats = [0, 0] # Hits, misses 81 data = {} 82 lastused = {} 83 84 @functools.wraps(user_function) 85 def wrapper(*args): 86 try: 87 result = data[args] 88 stats[0] += 1 # Hit 89 except KeyError: 90 stats[1] += 1 # Miss 91 if len(data) == maxsize: 92 for k, _ in nsmallest(maxsize // 10 or 1, 93 iteritems(lastused), 94 key=itemgetter(1)): 95 del data[k] 96 del lastused[k] 97 data[args] = user_function(*args) 98 result = data[args] 99 finally: 100 lastused[args] = time() 101 return result 102 103 def cache_info(): 104 return stats[0], stats[1], maxsize, len(data) 105 106 def cache_clear(): 107 data.clear() 108 lastused.clear() 109 stats[0] = stats[1] = 0 110 111 wrapper.cache_info = cache_info 112 wrapper.cache_clear = cache_clear 113 return wrapper 114 return decorating_function 115 116 117def lfu_cache(maxsize=100): 118 """A simple cache that, when the cache is full, deletes the least frequently 119 used 10% of the cached values. 120 121 This function duplicates (more-or-less) the protocol of the 122 ``functools.lru_cache`` decorator in the Python 3.2 standard library. 123 124 Arguments to the cached function must be hashable. 125 126 View the cache statistics tuple ``(hits, misses, maxsize, currsize)`` 127 with f.cache_info(). Clear the cache and statistics with f.cache_clear(). 128 Access the underlying function with f.__wrapped__. 129 """ 130 131 def decorating_function(user_function): 132 stats = [0, 0] # Hits, misses 133 data = {} 134 usecount = Counter() 135 136 @functools.wraps(user_function) 137 def wrapper(*args): 138 try: 139 result = data[args] 140 stats[0] += 1 # Hit 141 except KeyError: 142 stats[1] += 1 # Miss 143 if len(data) == maxsize: 144 for k, _ in nsmallest(maxsize // 10 or 1, 145 iteritems(usecount), 146 key=itemgetter(1)): 147 del data[k] 148 del usecount[k] 149 data[args] = user_function(*args) 150 result = data[args] 151 finally: 152 usecount[args] += 1 153 return result 154 155 def cache_info(): 156 return stats[0], stats[1], maxsize, len(data) 157 158 def cache_clear(): 159 data.clear() 160 usecount.clear() 161 162 wrapper.cache_info = cache_info 163 wrapper.cache_clear = cache_clear 164 return wrapper 165 return decorating_function 166 167 168def random_cache(maxsize=100): 169 """A very simple cache that, when the cache is filled, deletes 10% of the 170 cached values AT RANDOM. 171 172 This function duplicates (more-or-less) the protocol of the 173 ``functools.lru_cache`` decorator in the Python 3.2 standard library. 174 175 Arguments to the cached function must be hashable. 176 177 View the cache statistics tuple ``(hits, misses, maxsize, currsize)`` 178 with f.cache_info(). Clear the cache and statistics with f.cache_clear(). 179 Access the underlying function with f.__wrapped__. 180 """ 181 182 def decorating_function(user_function): 183 stats = [0, 0] # hits, misses 184 data = {} 185 186 @functools.wraps(user_function) 187 def wrapper(*args): 188 try: 189 result = data[args] 190 stats[0] += 1 # Hit 191 except KeyError: 192 stats[1] += 1 # Miss 193 if len(data) == maxsize: 194 keys = data.keys() 195 for i in xrange(maxsize // 10 or 1): 196 n = random.randint(0, len(keys) - 1) 197 k = keys.pop(n) 198 del data[k] 199 data[args] = user_function(*args) 200 result = data[args] 201 return result 202 203 def cache_info(): 204 return stats[0], stats[1], maxsize, len(data) 205 206 def cache_clear(): 207 data.clear() 208 209 wrapper.cache_info = cache_info 210 wrapper.cache_clear = cache_clear 211 return wrapper 212 return decorating_function 213 214 215def db_lru_cache(maxsize=100): 216 """Double-barrel least-recently-used cache decorator. This is a simple 217 LRU algorithm that keeps a primary and secondary dict. Keys are checked 218 in the primary dict, and then the secondary. Once the primary dict fills 219 up, the secondary dict is cleared and the two dicts are swapped. 220 221 This function duplicates (more-or-less) the protocol of the 222 ``functools.lru_cache`` decorator in the Python 3.2 standard library. 223 224 Arguments to the cached function must be hashable. 225 226 View the cache statistics tuple ``(hits, misses, maxsize, currsize)`` 227 with f.cache_info(). Clear the cache and statistics with f.cache_clear(). 228 Access the underlying function with f.__wrapped__. 229 """ 230 231 def decorating_function(user_function): 232 # Cache1, Cache2, Pointer, Hits, Misses 233 stats = [{}, {}, 0, 0, 0] 234 235 @functools.wraps(user_function) 236 def wrapper(*args): 237 ptr = stats[2] 238 a = stats[ptr] 239 b = stats[not ptr] 240 key = args 241 242 if key in a: 243 stats[3] += 1 # Hit 244 return a[key] 245 elif key in b: 246 stats[3] += 1 # Hit 247 return b[key] 248 else: 249 stats[4] += 1 # Miss 250 result = user_function(*args) 251 a[key] = result 252 if len(a) >= maxsize: 253 stats[2] = not ptr 254 b.clear() 255 return result 256 257 def cache_info(): 258 return stats[3], stats[4], maxsize, len(stats[0]) + len(stats[1]) 259 260 def cache_clear(): 261 """Clear the cache and cache statistics""" 262 stats[0].clear() 263 stats[1].clear() 264 stats[3] = stats[4] = 0 265 266 wrapper.cache_info = cache_info 267 wrapper.cache_clear = cache_clear 268 269 return wrapper 270 return decorating_function 271 272 273def clockface_lru_cache(maxsize=100): 274 """Least-recently-used cache decorator. 275 276 This function duplicates (more-or-less) the protocol of the 277 ``functools.lru_cache`` decorator in the Python 3.2 standard library, but 278 uses the clock face LRU algorithm instead of an ordered dictionary. 279 280 If *maxsize* is set to None, the LRU features are disabled and the cache 281 can grow without bound. 282 283 Arguments to the cached function must be hashable. 284 285 View the cache statistics named tuple (hits, misses, maxsize, currsize) 286 with f.cache_info(). Clear the cache and statistics with f.cache_clear(). 287 Access the underlying function with f.__wrapped__. 288 """ 289 290 def decorating_function(user_function): 291 stats = [0, 0, 0] # hits, misses, hand 292 data = {} 293 294 if maxsize: 295 # The keys at each point on the clock face 296 clock_keys = [None] * maxsize 297 # The "referenced" bits at each point on the clock face 298 clock_refs = array("B", (0 for _ in xrange(maxsize))) 299 lock = Lock() 300 301 @functools.wraps(user_function) 302 def wrapper(*args): 303 key = args 304 try: 305 with lock: 306 pos, result = data[key] 307 # The key is in the cache. Set the key's reference bit 308 clock_refs[pos] = 1 309 # Record a cache hit 310 stats[0] += 1 311 except KeyError: 312 # Compute the value 313 result = user_function(*args) 314 with lock: 315 # Current position of the clock hand 316 hand = stats[2] 317 # Remember to stop here after a full revolution 318 end = hand 319 # Sweep around the clock looking for a position with 320 # the reference bit off 321 while True: 322 hand = (hand + 1) % maxsize 323 current_ref = clock_refs[hand] 324 if current_ref: 325 # This position's "referenced" bit is set. Turn 326 # the bit off and move on. 327 clock_refs[hand] = 0 328 elif not current_ref or hand == end: 329 # We've either found a position with the 330 # "reference" bit off or reached the end of the 331 # circular cache. So we'll replace this 332 # position with the new key 333 current_key = clock_keys[hand] 334 if current_key in data: 335 del data[current_key] 336 clock_keys[hand] = key 337 clock_refs[hand] = 1 338 break 339 # Put the key and result in the cache 340 data[key] = (hand, result) 341 # Save the new hand position 342 stats[2] = hand 343 # Record a cache miss 344 stats[1] += 1 345 return result 346 347 else: 348 @functools.wraps(user_function) 349 def wrapper(*args): 350 key = args 351 try: 352 result = data[key] 353 stats[0] += 1 354 except KeyError: 355 result = user_function(*args) 356 data[key] = result 357 stats[1] += 1 358 return result 359 360 def cache_info(): 361 return stats[0], stats[1], maxsize, len(data) 362 363 def cache_clear(): 364 """Clear the cache and cache statistics""" 365 data.clear() 366 stats[0] = stats[1] = stats[2] = 0 367 for i in xrange(maxsize): 368 clock_keys[i] = None 369 clock_refs[i] = 0 370 371 wrapper.cache_info = cache_info 372 wrapper.cache_clear = cache_clear 373 return wrapper 374 return decorating_function 375 376