You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Describe the bug
The LruCache is implemented with a BTreeMap and a VecDeque, which means that by accessing keys and calling the update_key method, it will invoke a VecDeque::remove operation, which will cost O(n) time.
Expected behavior
Should be O(1).
Additional context
Some other libs that do the complexity right:
lru-cache & linked-hash-map: used a linked hash map, O(1).
Current lru cache is known to be slow:
maidsafe/lru_time_cache#143
This change replaces it with our own lru cache based ond hashlink and
rustc hash. The new implementation uses tests from the original lru
crate. Additionaly the behaviour is verified to be the same using
property based tests.
Signed-off-by: Tomasz Kłak <[email protected]>
Describe the bug
The
LruCache
is implemented with aBTreeMap
and aVecDeque
, which means that by accessing keys and calling theupdate_key
method, it will invoke aVecDeque::remove
operation, which will costO(n)
time.Expected behavior
Should be
O(1)
.Additional context
Some other libs that do the complexity right:
sample
The text was updated successfully, but these errors were encountered: