7. Performance¶
7.1. Speed¶
In general, the code should perform as fast as lru.LRU
for the
following operations:
Lookup by key (either a hit or miss), and
Replace a key’s associated value.
Internally there is more overhead because of some extra checking and loading in order to avoid executing foreign code in a critical section. Such overhead are insignificant though as shown by benchmarks, and the benefit outweighs the cost.
The following operations are faster and overall safer (where applicable):
Inserting a new item,
Deleting an existing key-value pair,
Evicting items under insertion load, with or without callback set, and
Dict-like methods.
The one scenario that could incur significant slowdown is when
a callback is not set, and
the evicted key or value’s
__del__()
method would have presented a risk of executing arbitrary code.
As special cases, for a handful of Python built-in types such as str
or
bytearray
(but not for subclasses), we can be certain that their
finalization/deallocation wouldn’t interfere with our normal operation, and
they will not cause slowdown.
However, in general, we take extra care to defer potential deallocation despite
the overhead, because the safety far outweighs the extra speed. The “slow” code
can be observed in benchmarks where the evictions are triggered by resizing a
very large LRUDict
object to a small size, without the callback. The
cause is the overhead of extra moves to ensure that no __del__()
code may be triggered while doing internal sensitive operations, and that
normal method calls may not fail spuriously.
7.2. Memory usage¶
The memory usage is larger because of internal memoization of key hash values. The overhead per key is the same as the platform’s pointer size (4/8 bytes on 32/64-bit systems). That is, the overhead is O(n) where n is the number of keys.
Some additional memory allocations are made to keep a queue of items facing
imminent destruction, but these are usual small and allocated per
LRUDict
instance, or O(1).
The LRUDict
object participates effectively in Python’s garbage
collection. Reference cycles are detected by Python’s cyclic garbage collector
and broken up when all external references are dropped. For example, the
following code
from lru_ng import LRUDict
r = LRUDict(4)
r[0] = r
del r
will not leave a self-referencing, unusable, but “live” object permanently in memory. It will eventually be collected by Python’s garbage collector.