4. Compatibility

Being a fork of the lru module, this module is designed with compatibility in mind. Most of the time, drop-in replacement can be achieved by the import statement

from lru_ng import LRUDict as LRU

However, this module is also intended for newer CPython applications following newer conventions and standards, which can diverge from the inherited code (hence the “ng” in the module name, for “new generation”). I attempt to provide a list of differences from lru == 1.1.7 here.

4.1. Differences from lru.LRU 1.1.7

  • Name of the class has changed to LRUDict (because the acronym “LRU” is better reserved as an adjective or a description of the particular replacement policy).

  • Python 2.7 support is removed. Instead, CPython 3.6+ is now required.

  • The get_size(), set_size(), and set_callback() methods are obsoleted. To resize or change the callback, use the properties size and callback respectively.

  • The peek_first_item() and peek_last_item() methods raise KeyError for empty LRUDict, rather than return None.

  • The popitem() method by default pops in the order from the most recent to the least recent. This is the inverse of the old default behaviour.

  • The string returned by repr() can now be distinguished from that of a plain dict.

In addition, there are also some significant internal changes that affect behaviours in more subtle ways.

  • The methods that takes a “key” parameter evaluate the hash only once, like the Python dict. This results in a performance gain.

  • Python garbage collection (reclaiming objects forming reference cycles that are otherwise unreachable) is supported (see also Memory usage).

  • The LRUDict instance is unhashable.

  • The callback is now executed outside the critical section of the code (where internal changes to the data structures are taking place). Newly evicted items are buffered, and a purge() method can optionally ensure that the buffer is cleared, although the code takes care of purging normally. This change reduces the likelihood that a misbehaving callback may crash the Python process.

  • Similarly, the __del__() of the key or value cannot be normally triggered inside the critical section.

  • The callback’s exception is suppressed (more details in Caveats with callbacks).

  • Assuming the protection of the global interpreter lock, the methods now has limited protection of the critical section. If for some exotic reason the __hash__() or __eq__() special-methods of the key attempt to modify the LRUDict object inside a method call, the code will attempt to detect this and raise an LRUDictBusyError exception.

  • Overall behaviour in Python threads or other execution units (such as coroutines or greenlets) is now more predictable and safer. Even if a callback releases the GIL, the internal state remains consistent. There is limited ability to detect conflicting access at runtime; see Thread safety for more.

4.2. Comparison with Python dict or OrderedDict

LRUDict attempts to emulate Python built-in dict in API and behaviour (when sensible). However, currently returning an iterable proxy by keys(), values(), and items() are among the unsupported methods. The reason is that the internal ordering of keys is volatile, and an iterator honouring the ordering is very easily invalidated, thus limiting its use.

A dict maintains key-insertion order (since CPython 3.6+), which is not the same as key-use order in the LRU sense: a hit promotes the key to the highest priority but does not necessarily change the insertion order (unless it is removed and inserted again).

Python offers another mapping type, collections.OrderedDict, which bear some similarity to LRUDict. The major difference is that LRUDict is focused on bounded size and eviction callback while the former is a more flexible mapping type.

4.3. Comparison with Python functools.lru_cache()

Python provides a native and optimized functools.lru_cache() implementation, which is primarily used as a decorator for memoization (remembering return values for inputs that has been evaluated before).

This module, however, provides a container/mapping class, and a memoizing LRU decorator can be built on top of it (although not as fast as the native one, because the latter implements more optimizations and also avoids a lot of overhead of handling Python calls or exceptions). Instead, this module focuses on dict-compatibility and the ability to set a callback.

Also, unlike functools.lru_cache(), there is no default size limit at initialization: a value must be provided by the user. Unbound size is not supported, either: the size bound must be explicit (although ultimately hard-limited by the platform’s sys.maxsize).