Skip to content

Bug in LRUCache implementation #596

@epicblueprints

Description

@epicblueprints
class LRUCache(....):

def set(self, key: K, value: V):
  if self.cache.get(key):
    self.cache[key] = value
    self.cache.move_to_end(key, last=True)
  else:
    self.cache[key] = value

    # Check, if the cache is full and we have to remove old items
    # If the queue is of unlimited size, self.capacity is NaN and
    # x > NaN is always False in Python and the cache won't be cleared.
    if self.capacity is not None and self.length > self.capacity:
        self.cache.popitem(last=False)

The condition if self.cache.get(key): checks if the value is truthy, not if the key exists. This causes problems when Falsy values (0, False, "", [], None, etc.) are stored for a key.
When updating an existing key with a falsy value, it's treated as a new key (goes to else) and breaks LRU ordering.

A test case to demonstrate this bug. This test fails

def test_lru_cache_set_item():
    cache = LRUCache(capacity=3)
    cache["a"] = 0      # Falsy value!
    cache["b"] = 1
    cache["c"] = 2

    assert sorted(cache.lru) == ["a", "b", "c"]
    
    cache.set("a", 3)   # This should update "a" and move it to end
    cache.set("d", 4)   # This should evict "b"
    
    assert sorted(cache.lru) == ["a", "c", "d"]  # "b" should be gone but "a" is evicted in the current implementation

On the other end, the following test case passes -

def test_lru_cache_set_item():
    cache = LRUCache(capacity=3)
    cache["a"] = 3
    cache["b"] = 1
    cache["c"] = 2

    assert sorted(cache.lru) == ["a", "b", "c"]

    cache.set("a", 0)
    cache.set("d", 4)

    assert sorted(cache.lru) == ["a", "c", "d"]

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions