75
cache
(lemmy.dbzer0.com)
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
this post was submitted on 16 Jun 2023
75 points (100.0% liked)
Programmer Humor
19572 readers
1863 users here now
Welcome to Programmer Humor!
This is a place where you can post jokes, memes, humor, etc. related to programming!
For sharing awful code theres also Programming Horror.
Rules
- Keep content in english
- No advertisements
- Posts must be related to programming or programmer topics
founded 1 year ago
MODERATORS
Finding clothes on a chair isn't constant-time. You have to search through the heap of clothes to find the item you want. It has the same time complexity as searching through the closet; it's only fast because n is small.
This assumes you're looking for a particular item of clothing. It's true that the clothes cache is not optimized for that.
However, if you are instead looking for a shirt, a pair of pants, and/or so on, without regards to which specific shirt, and if the cache is randomly sorted and the distribution of all such items is roughly equal, then it becomes O(1) - regardless of the size of the cache, you'll get what you want within 4 or 5 checks. Plus, you typically want one of each of the types of item, and you'll get all of them within those same 4 or 5 checks.
Bonus: the checks can be parallelized by using a "wide" cache that enables multiple items to be checked at once. This is why I use a short and wide clean clothes basket and a tall and skinny dirty clothes basket.
It takes 2 pause cycles, that's essentially O(1) compared to a cache miss.
You could implement in-closet indexing instead to make the cache misses hurt less, trading off some extra insertion time but needing less memory for the cache which is much more expensive cost wise. At this point you're storing almost your whole DB in the cache and your room's a mess.