Python Dict vs List Lookup: Why Your Cache Gets Slow

The slow cache

Here is an embedding cache that keeps its entries in a list:

class EmbeddingCache:
    def __init__(self) -> None:
        self.entries: list[tuple[str, list[float]]] = []

    def put(self, key: str, vector: list[float]) -> None:
        for i, (k, _) in enumerate(self.entries):
            if k == key:
                self.entries[i] = (key, vector)
                return
        self.entries.append((key, vector))

    def get(self, key: str) -> list[float] | None:
        for k, vec in self.entries:
            if k == key:
                return vec
        return None

    def __len__(self) -> int:
        return len(self.entries)

The code is correct. In a unit test with ten entries it is instant. The problem only appears with real data: get and put both walk the list from the start, so each call does work in proportion to the size of the cache.

Why the list gets slow

• get on a missing key checks every entry before it returns None.
• put must check every entry to see whether the key already exists.
• Loading n entries with put does about n * n / 2 comparisons in total. At 50,000 entries that is more than a billion string comparisons.

This is O(n) per call and O(n^2) to fill the cache. The cache was added to make repeat requests fast, but now each lookup costs more as the cache grows.

The dict version

A dict stores entries in a hash table. Python hashes the key, finds the slot, and checks only the few keys in that slot. Lookup, insert, and delete are O(1) on average, no matter how many entries there are:

class EmbeddingCache:
    def __init__(self) -> None:
        self.entries: dict[str, list[float]] = {}

    def put(self, key: str, vector: list[float]) -> None:
        self.entries[key] = vector          # insert or replace

    def get(self, key: str) -> list[float] | None:
        return self.entries.get(key)        # None if missing

    def __len__(self) -> int:
        return len(self.entries)

The behavior stays the same:

• put on an existing key replaces the vector - dict assignment does that by itself.
• get on a missing key returns None - that is what dict.get does by default.
• len() counts unique keys, as before.

The class interface does not change, so no calling code needs to change.

Measure it

Do not trust the theory alone. Time both versions with the standard library:

import time
from cache import EmbeddingCache

c = EmbeddingCache()
start = time.perf_counter()
for i in range(10_000):
    c.put(f"prompt-{i}", [0.1, 0.2])
print(f"10k puts: {(time.perf_counter() - start) * 1000:.1f} ms")

start = time.perf_counter()
for i in range(1_000):
    c.get(f"prompt-{i * 7}")
print(f"1k gets:  {(time.perf_counter() - start) * 1000:.1f} ms")

With the list version the numbers grow fast as you raise the entry count. With the dict version they stay at a few milliseconds. Run the benchmark at the size you expect in production, not at the size of your test data.

The same bug in other places

The list-scan pattern shows up anywhere code looks something up by key:

• if user_id in banned_users: where banned_users is a list - use a set.
• Finding a session by session ID in a list of session objects.
• Getting a feature flag or prompt template by name from a list of dicts.
• Removing duplicates with if x not in seen_list inside a loop.

A good rule: if the main thing you do with a collection is "find by key" or "is this in it?", use a dict or a set. Use a list when order is the main thing you need.

Things to know about dict keys

• Keys must be hashable. Strings, numbers, and tuples work. Lists do not - convert a list to a tuple first.
• Order is kept. Since Python 3.7, a dict keeps insertion order, so you do not lose the order of the old list.
• Memory grows with size. A cache without a limit grows forever. For a bounded cache use functools.lru_cache for functions, or an OrderedDict and remove the oldest entry when you go over the limit.
• Shared between processes? A dict lives in one process. When several servers need the same cache, move it to Redis - its key lookup is also O(1).