Caching and Least-Recently-Used Eviction

Reference

class darts.lib.utils.lru.LRUDict([capacity=1024])

Instances of this class are basically dictionaries, which limit the number of entries they can hold. Each dictionary has a capacity (initialized by the capacity argument to the constructor), which defines this maximum number. The value can be changed at run-time by modifying the capacity property of an instance.

If the dictionary has to remove entries in order to make room for new ones, it will remove those, which haven’t been accessed for a “long time”.

Thread-safety: Instances of this class are not thread-safe, even if only the read accessors are used concurrently. An application intending to share an instance of this class among multiple concurrently executing threads needs to synchronize all access to the instance itself.

The SynchronizedLRUDict provides a stand-alone thread-safe version of this class.

Iteration: The ordering of entries under iteration is undefined. In particular, it usually does not reflect the eviction priority order.

capacity

Contains the current capacity of the dictionary. At any time, the dictionary holds as most as many entries as this value indicates. Changing the value of the property to a smaller number may cause entries to be removed from the dictionary.

clear()

Removes all entries from this dictionary. Note, that currently, this method has a run-time complexity proportional to the number of entries contained in the dictionary.

peek(key[, default=None])

Look up the value of key. This method returns the value associated with key in this dictionary. If no matching entry exists, the method returns default instead. Note, that unlike most accessor methods, this one does not affect the priority of a matching entry, i.e., looking up a value using this method does not count as “access”, adn won’t change the likelyhood of the entry found to be discarded or not, if the dictionary needs to make room for new entries.

get(key[, default=None])

Look up the value of key. This method returns the value associated with key in this dictionary. If no matching entry exists, the method returns default instead. If a matching entry exists, its priority is boosted by this method, making it less likely, that the entry is removed the next time, the dictionary has to make room for new elements.

__getitem__(key)

Look up the value of key. This method returns the value associated with key in this dictionary. If no matching entry exists, the method raises a KeyError instead. If a matching entry exists, its priority is boosted by this method, making it less likely, that the entry is removed the next time, the dictionary has to make room for new elements.

__setitem__(key, value)

Associates the value value to key in this dictionary. If there was already an entry for key, its value is replaced with value.

This method boosts the entry’s priority, making it less likely, that the entry is removed the next time, the dictionary has to make room for new elements.

__delitem__(key)

Deletes an entry from this dictionary. This method deletes the entry associated with key from this dictionary. If no matching entry exists, this method raises a KeyError instead. Calling this method does not affect the priorities of other entries.

__len__()

Answers the current number of elements contained in this dictionary.

__contains__(key)

Tests, whether this dictionary has an entry for the given key. If so, the entry’s priority is boosted, making it less likely, that the entry is removed the next time, the dictionary has to make room for new elements.

__iter__()

See iterkeys().

iterkeys()

This method returns a generator, which produces all the keys currently present in the dictionary. The ordering of the keys is undefined.

itervalues()

This method returns a generator, which produces all the values currently present in the dictionary. The ordering of the values is undefined.

iteritems()

This method returns a generator, which produces tuples of the form key, value for all entries in the dictionary. The ordering of the values is undefined.

class darts.lib.utils.lru.SynchronizedLRUDict([capacity=1024[, lock=None]])

This class provides a thread-safe version of LRUDict. Each instance maintains a plain LRUDict internally, and delegates all method calls to that object, making sure, that the calls are properly synchronized using a thread lock.

If no explicit lock argument is provided at instance creation time, the synchronized LRU dict will create its own lock.

Note, that this class does not inherit from LRUDict.

capacity

Contains the current capacity of the dictionary. At any time, the dictionary holds as most as many entries as this value indicates. Changing the value of the property to a smaller number may cause entries to be removed from the dictionary.

clear()

Removes all entries from this dictionary. Note, that currently, this method has a run-time complexity proportional to the number of entries contained in the dictionary.

peek(key[, default=None])

Look up the value of key. This method returns the value associated with key in this dictionary. If no matching entry exists, the method returns default instead. Note, that unlike most accessor methods, this one does not affect the priority of a matching entry, i.e., looking up a value using this method does not count as “access”, adn won’t change the likelyhood of the entry found to be discarded or not, if the dictionary needs to make room for new entries.

get(key[, default=None])

Look up the value of key. This method returns the value associated with key in this dictionary. If no matching entry exists, the method returns default instead. If a matching entry exists, its priority is boosted by this method, making it less likely, that the entry is removed the next time, the dictionary has to make room for new elements.

__getitem__(key)

Look up the value of key. This method returns the value associated with key in this dictionary. If no matching entry exists, the method raises a KeyError instead. If a matching entry exists, its priority is boosted by this method, making it less likely, that the entry is removed the next time, the dictionary has to make room for new elements.

__setitem__(key, value)

Associates the value value to key in this dictionary. If there was already an entry for key, its value is replaced with value.

This method boosts the entry’s priority, making it less likely, that the entry is removed the next time, the dictionary has to make room for new elements.

__delitem__(key)

Deletes an entry from this dictionary. This method deletes the entry associated with key from this dictionary. If no matching entry exists, this method raises a KeyError instead. Calling this method does not affect the priorities of other entries.

__len__()

Answers the current number of elements contained in this dictionary.

__contains__(key)

Tests, whether this dictionary has an entry for the given key. If so, the entry’s priority is boosted, making it less likely, that the entry is removed the next time, the dictionary has to make room for new elements.

__iter__()

See iterkeys().

iterkeys()

This method returns a generator, which produces all the keys currently present in the dictionary. The ordering of the keys is undefined.

Note, that the generator returned will traverse over a snapshot copy of the actual key set made, when the iterkeys method was called.

itervalues()

This method returns a generator, which produces all the values currently present in the dictionary. The ordering of the values is undefined.

Note, that the generator returned will traverse over a snapshot copy of the actual value collection made, when the itervalues method was called.

iteritems()

This method returns a generator, which produces tuples of the form key, value for all entries in the dictionary. The ordering of the values is undefined.

Note, that the generator returned will traverse over a snapshot copy of the actual items collection made, when the iteritems method was called.

class darts.lib.utils.lru.AutoLRUCache(loader[, capacity=1024])

Instances of this class act as self-contained resource loaders and caches. Each instance of this class has a maximum number of elements it may contains (the cache’s capacity).

The loader must be a callable with the signature

lambda key: …

where key will be the identifier passed to load(). The loader function should return None, if there is no resource with the given key. Any other return value is taken to be the actual resource. Note, that the cache is likely to cache any value returned by this function, even None.

The cache is careful to coalesce multiple concurrent load operations with the same key into a single operation. Note, though, that any number of load operations may started concurrently, as long as they have different keys.

Thread-safety: Instances of this class are fully thread-safe, managing all required synchronization internally. Note, however, that the custom loader function is always called outside of any synchronization scope. In particular, it needs to perform its own synchronization if it needs one.

clear([discard_loads=False])

Removes all entries from this cache. This method removes all entries from this cache. If discard_loads is true, then all currently pending load operations will be discarded, and their results will be ignored.

load(key[, default=None])

Load a resource for a given key. This method returns the resource, whose key matches key, or default if there is no matching resource. If the resource is not currently present in the cache, the cache’s resource loader function is called to load the resource from whatever is the underlying storage.

If an exception is raised by the loader function, it will be re-raised by this method, wrapped in a CacheLoadError exception.

If a call to clear() is made with discard_loads set to true, while the loader function is loading the resource, the method will raise a CacheAbandonedError exception as soon as the loader finishes loading.

Indices and tables