Ah ok, the lazy construction part is what I was missing, if you basically never build the full key, there's nothing to cache. Makes sense now why the LRU didn't help. I'll think about it over the nextdays.