2 ms·

Caching is bounded, GC is potentially boundless. Caching is all about deciding what to evict.

taeric 3y ago
Right, I know there are differences. Easiest consideration there is that caches are probably never walking to root pointers. They can choose to work on individual entries with no regard to the rest. My point is not any different than how you design your kitchen/house. Things that you use all of the time, you have up front. The more often you use them, the closer they are to where they are used. Same for general storage. Why would cache not follow the same pattern? In each "bin" you can go with LRU or Sieve, but having multiple bins makes a ton of sense. And it looks a lot like the way that GC works.
- vlovich123 3y ago
  Cache design has a lot of different constraints and you can exploit those constraints to build more efficient systems. And yes, people in the space are aware of GC research and leverage design concepts from there where appropriate. Think of sieve as one component of a full caching systems. Many caching systems will combine primitives to have a “newly encountered” and “recently expired” generation where they’ll use a probabilistic filter or something similarly compact to determine whether they’ve seen something enough to spend resources caching it. There’s memory usage concerns (frequently you want a hard upper bound on memory consumption), speed/latencies (these systems are handling many thousands of requests per second and need to have near 0 latency), and fit as much as possible into the memory constraints (eg using probabilistic filters for admittance). SIEVE can be integrated into things like W-TinyLfu / s3fifo to replace certain individual components (I would read their papers - they’re fairly approachable and discuss the full design).
ActionHank 3y ago
GC is intrinsically bounded by the amount of memory available. GC is also about deciding what to evict albeit the heuristic used to determine that is based on current use rather than frequency of use. dotnet runtime GC is interesting for caching, because it has multiple generations for the GC. Each time there is a GC the survivors are moved to the next generation. Moving most used items to the next generation and looking in the later generations first when resolving could be pretty quick.

Right, I know there are differences. Easiest consideration there is that caches are probably never walking to root pointers. They can choose to work on individual entries with no regard to the rest. My point is not any different than how you design your kitchen/house. Things that you use all of the time, you have up front. The more often you use them, the closer they are to where they are used. Same for general storage. Why would cache not follow the same pattern? In each "bin" you can go with LRU or Sieve, but having multiple bins makes a ton of sense. And it looks a lot like the way that GC works.

vlovich123 3y ago
Cache design has a lot of different constraints and you can exploit those constraints to build more efficient systems. And yes, people in the space are aware of GC research and leverage design concepts from there where appropriate. Think of sieve as one component of a full caching systems. Many caching systems will combine primitives to have a “newly encountered” and “recently expired” generation where they’ll use a probabilistic filter or something similarly compact to determine whether they’ve seen something enough to spend resources caching it. There’s memory usage concerns (frequently you want a hard upper bound on memory consumption), speed/latencies (these systems are handling many thousands of requests per second and need to have near 0 latency), and fit as much as possible into the memory constraints (eg using probabilistic filters for admittance). SIEVE can be integrated into things like W-TinyLfu / s3fifo to replace certain individual components (I would read their papers - they’re fairly approachable and discuss the full design).

ActionHank 3y ago

GC is intrinsically bounded by the amount of memory available. GC is also about deciding what to evict albeit the heuristic used to determine that is based on current use rather than frequency of use. dotnet runtime GC is interesting for caching, because it has multiple generations for the GC. Each time there is a GC the survivors are moved to the next generation. Moving most used items to the next generation and looking in the later generations first when resolving could be pretty quick.