cacheutils - Caches and caching

cacheutils contains consistent implementations of fundamental cache types. Currently there are two to choose from:

  • LRI - Least-recently inserted
  • LRU - Least-recently used

Both caches are dict subtypes, designed to be as interchangeable as possible, to facilitate experimentation. A key practice with performance enhancement with caching is ensuring that the caching strategy is working. If the cache is constantly missing, it is just adding more overhead and code complexity. The standard statistics are:

  • hit_count - the number of times the queried key has been in the cache
  • miss_count - the number of times a key has been absent and/or fetched by the cache
  • soft_miss_count - the number of times a key has been absent, but a default has been provided by the caller, as with dict.get() and dict.setdefault(). Soft misses are a subset of misses, so this number is always less than or equal to miss_count.

Additionally, cacheutils provides ThresholdCounter, a cache-like bounded counter useful for online statistics collection.

Learn more about caching algorithms on Wikipedia.

Least-Recently Inserted (LRI)

The LRI is the simpler cache, implementing a very simple first-in, first-out (FIFO) approach to cache eviction. If the use case calls for simple, very-low overhead caching, such as somewhat expensive local operations (e.g., string operations), then the LRI is likely the right choice.

class boltons.cacheutils.LRI(max_size=128, values=None, on_miss=None)[source]

The LRI implements the basic Least Recently Inserted strategy to caching. One could also think of this as a SizeLimitedDefaultDict.

on_miss is a callable that accepts the missing key (as opposed to collections.defaultdict’s “default_factory”, which accepts no arguments.) Also note that, like the LRI, the LRI is instrumented with statistics tracking.

>>> cap_cache = LRI(max_size=2)
>>> cap_cache['a'], cap_cache['b'] = 'A', 'B'
>>> from pprint import pprint as pp
>>> pp(dict(cap_cache))
{'a': 'A', 'b': 'B'}
>>> [cap_cache['b'] for i in range(3)][0]
'B'
>>> cap_cache['c'] = 'C'
>>> print(cap_cache.get('a'))
None
>>> cap_cache.hit_count, cap_cache.miss_count, cap_cache.soft_miss_count
(3, 1, 1)
clear() → None. Remove all items from D.[source]
copy() → a shallow copy of D[source]
get(key, default=None)[source]

Return the value for key if key is in the dictionary, else default.

pop(k[, d]) → v, remove specified key and return the corresponding value.[source]

If key is not found, d is returned if given, otherwise KeyError is raised

popitem() → (k, v), remove and return some (key, value) pair as a[source]

2-tuple; but raise KeyError if D is empty.

setdefault(key, default=None)[source]

Insert key with a value of default if key is not in the dictionary.

Return the value for key if key is in the dictionary, else default.

update([E, ]**F) → None. Update D from dict/iterable E and F.[source]

If E is present and has a .keys() method, then does: for k in E: D[k] = E[k] If E is present and lacks a .keys() method, then does: for k, v in E: D[k] = v In either case, this is followed by: for k in F: D[k] = F[k]

Least-Recently Used (LRU)

The LRU is the more advanced cache, but it’s still quite simple. When it reaches capacity, a new insertion replaces the least-recently used item. This strategy makes the LRU a more effective cache than the LRI for a wide variety of applications, but also entails more operations for all of its APIs, especially reads. Unlike the LRI, the LRU has threadsafety built in.

class boltons.cacheutils.LRU(max_size=128, values=None, on_miss=None)[source]

The LRU is dict subtype implementation of the Least-Recently Used caching strategy.

Parameters:
  • max_size (int) – Max number of items to cache. Defaults to 128.
  • values (iterable) – Initial values for the cache. Defaults to None.
  • on_miss (callable) – a callable which accepts a single argument, the key not present in the cache, and returns the value to be cached.
>>> cap_cache = LRU(max_size=2)
>>> cap_cache['a'], cap_cache['b'] = 'A', 'B'
>>> from pprint import pprint as pp
>>> pp(dict(cap_cache))
{'a': 'A', 'b': 'B'}
>>> [cap_cache['b'] for i in range(3)][0]
'B'
>>> cap_cache['c'] = 'C'
>>> print(cap_cache.get('a'))
None

This cache is also instrumented with statistics collection. hit_count, miss_count, and soft_miss_count are all integer members that can be used to introspect the performance of the cache. (“Soft” misses are misses that did not raise KeyError, e.g., LRU.get() or on_miss was used to cache a default.

>>> cap_cache.hit_count, cap_cache.miss_count, cap_cache.soft_miss_count
(3, 1, 1)

Other than the size-limiting caching behavior and statistics, LRU acts like its parent class, the built-in Python dict.

Automatic function caching

Continuing in the theme of cache tunability and experimentation, cacheutils also offers a pluggable way to cache function return values: the cached() function decorator and the cachedmethod() method decorator.

boltons.cacheutils.cached(cache, scoped=True, typed=False, key=None)[source]

Cache any function with the cache object of your choosing. Note that the function wrapped should take only hashable arguments.

Parameters:
  • cache (Mapping) – Any dict-like object suitable for use as a cache. Instances of the LRU and LRI are good choices, but a plain dict can work in some cases, as well. This argument can also be a callable which accepts no arguments and returns a mapping.
  • scoped (bool) – Whether the function itself is part of the cache key. True by default, different functions will not read one another’s cache entries, but can evict one another’s results. False can be useful for certain shared cache use cases. More advanced behavior can be produced through the key argument.
  • typed (bool) – Whether to factor argument types into the cache check. Default False, setting to True causes the cache keys for 3 and 3.0 to be considered unequal.
>>> my_cache = LRU()
>>> @cached(my_cache)
... def cached_lower(x):
...     return x.lower()
...
>>> cached_lower("CaChInG's FuN AgAiN!")
"caching's fun again!"
>>> len(my_cache)
1
boltons.cacheutils.cachedmethod(cache, scoped=True, typed=False, key=None)[source]

Similar to cached(), cachedmethod is used to cache methods based on their arguments, using any dict-like cache object.

Parameters:
  • cache (str/Mapping/callable) – Can be the name of an attribute on the instance, any Mapping/dict-like object, or a callable which returns a Mapping.
  • scoped (bool) – Whether the method itself and the object it is bound to are part of the cache keys. True by default, different methods will not read one another’s cache results. False can be useful for certain shared cache use cases. More advanced behavior can be produced through the key arguments.
  • typed (bool) – Whether to factor argument types into the cache check. Default False, setting to True causes the cache keys for 3 and 3.0 to be considered unequal.
  • key (callable) – A callable with a signature that matches make_cache_key() that returns a tuple of hashable values to be used as the key in the cache.
>>> class Lowerer(object):
...     def __init__(self):
...         self.cache = LRI()
...
...     @cachedmethod('cache')
...     def lower(self, text):
...         return text.lower()
...
>>> lowerer = Lowerer()
>>> lowerer.lower('WOW WHO COULD GUESS CACHING COULD BE SO NEAT')
'wow who could guess caching could be so neat'
>>> len(lowerer.cache)
1

Similar functionality can be found in Python 3.4’s functools.lru_cache() decorator, but the functools approach does not support the same cache strategy modification, nor does it support sharing the cache object across multiple functions.

boltons.cacheutils.cachedproperty(func)[source]

The cachedproperty is used similar to property, except that the wrapped method is only called once. This is commonly used to implement lazy attributes.

After the property has been accessed, the value is stored on the instance itself, using the same name as the cachedproperty. This allows the cache to be cleared with delattr(), or through manipulating the object’s __dict__.

Threshold-bounded Counting

class boltons.cacheutils.ThresholdCounter(threshold=0.001)[source]

A bounded dict-like Mapping from keys to counts. The ThresholdCounter automatically compacts after every (1 / threshold) additions, maintaining exact counts for any keys whose count represents at least a threshold ratio of the total data. In other words, if a particular key is not present in the ThresholdCounter, its count represents less than threshold of the total data.

>>> tc = ThresholdCounter(threshold=0.1)
>>> tc.add(1)
>>> tc.items()
[(1, 1)]
>>> tc.update([2] * 10)
>>> tc.get(1)
0
>>> tc.add(5)
>>> 5 in tc
True
>>> len(list(tc.elements()))
11

As you can see above, the API is kept similar to collections.Counter. The most notable feature omissions being that counted items cannot be set directly, uncounted, or removed, as this would disrupt the math.

Use the ThresholdCounter when you need best-effort long-lived counts for dynamically-keyed data. Without a bounded datastructure such as this one, the dynamic keys often represent a memory leak and can impact application reliability. The ThresholdCounter’s item replacement strategy is fully deterministic and can be thought of as Amortized Least Relevant. The absolute upper bound of keys it will store is (2/threshold), but realistically (1/threshold) is expected for uniformly random datastreams, and one or two orders of magnitude better for real-world data.

This algorithm is an implementation of the Lossy Counting algorithm described in “Approximate Frequency Counts over Data Streams” by Manku & Motwani. Hat tip to Kurt Rose for discovery and initial implementation.

add(key)[source]

Increment the count of key by 1, automatically adding it if it does not exist.

Cache compaction is triggered every 1/threshold additions.

elements()[source]

Return an iterator of all the common elements tracked by the counter. Yields each key as many times as it has been seen.

get(key, default=0)[source]

Get count for key, defaulting to 0.

get_common_count()[source]

Get the sum of counts for keys exceeding the configured data threshold.

get_commonality()[source]

Get a float representation of the effective count accuracy. The higher the number, the less uniform the keys being added, and the higher accuracy and efficiency of the ThresholdCounter.

If a stronger measure of data cardinality is required, consider using hyperloglog.

get_uncommon_count()[source]

Get the sum of counts for keys that were culled because the associated counts represented less than the configured threshold. The long-tail counts.

most_common(n=None)[source]

Get the top n keys and counts as tuples. If n is omitted, returns all the pairs.

update(iterable, **kwargs)[source]

Like dict.update() but add counts instead of replacing them, used to add multiple items in one call.

Source can be an iterable of keys to add, or a mapping of keys to integer counts.