LRU cache is actually FIFO

2e0byo commented 2 years ago

Disclaimer: I may be being stupid here.

Currently LruCache is just a FIFO. When the cache overflows it pops the item added least recently. An LRU cache should (right?) take access into account.

I can add a PR to make it a true LruCache, or to rename it to FifoCache, or I could just need a gentle explainer about how caches work if I'm being daft.

Expected behaviour:

from mopidy_tidal import LruCache

def test_lru():
    lru_cache = LruCache(max_size=8, persist=True, directory="cache")
    lru_cache |= {f"tidal:uri:{val}": val for val in range(8)}
    lru_cache["tidal:uri:0"] # 0th entry becomes most recently accessed
    lru_cache["tidal:uri:8"] = 8
    assert lru_cache == {f"tidal:uri:{val}": val for val in (0, *range(2, 9))}

blacklight commented 2 years ago

It's still an LRU cache technically, it's just that its definition of "used" means "inserted", not "read" - the order of insertion is basically guaranteed by extending OrderedDict.

I think it makes sense to make it a "true" LRU cache - meaning that it should move an item to the top also when it's read.

2e0byo commented 2 years ago

Great---I'll have a think about the implementation and suggest a PR. With a bit of thought it should be possible to abstract the interface and have the track cache inherit as well, so that'll solve another worry.

(Isn't that just a FIFO? Insertion only happens if the item isn't in the cache anyhow, so effectively an item is in the cache until it's the oldest, at which point it's evicted. Or more generally, FIFO is a special case of LRU where insertion = updated and re-insertion is forbidden. Anyhow it's moot.)

tehkillerbee / mopidy-tidal

LRU cache is actually FIFO #71