SomewhatLikely
Joined 11 years ago
Karma
692
Submissions
402
Member since
May 19
Joined 11 years ago
If you would build an in-memory cache, how would you do it?
It should have good performance and be able to hold many entries.
Reads are more common than writes. I know how I would do it already,
but I’m curious about your approach.
Was to add this requirement since it comes up so often: Let's assume that keys accessed follow a power law, so some keys get
accessed very frequently and we would like them to have the fastest
retrieval of all.
I'm not sure if there are any efficient tweaks to hash tables or b-trees that might help with this additional requirement. Obviously we could make a hash table take way more space than needed to reduce collisions, but with a decent load factor is the answer to just swap frequently accessed keys to the beginning of their probe chain? How do we know it's frequently accessed? Count-Min sketch?Even with that tweak, the hottest keys will still be scattered around memory. Wouldn't it be best if their entries could fit into fewer pages? So, maybe a much smaller "hot" table containing say the 1,000 most accessed keys. We still want a high load factor to maximize the use of cache pages so perhaps perfect hashing?
By the way, I like testing AIs on new games as they aren't in the training data and gpt5.6 sol high thinking was able to get from my second guess result to the correct answer. One letter was already locked and four more were down to a five letterish range. Still impressive as I remember models up until about the second generation of reasoning models really struggling with games like wordle.