5 ms·
If the number of searches for each key isn’t uniformly random, then instead of random replacement, you can bubble sort the bucket values into an LRU eviction sc
by CoolGuySteve 8y ago
If the number of searches for each key isn’t uniformly random, then instead of random replacement, you can bubble sort the bucket values into an LRU eviction scheme. Each time you do a lookup that succceds and the element in the hash entry isn’t index 0, swap it with index - 1. Replacement should always be done on the last element in the bucket vector.
This has 2 advantages:
- scanning the bucket aggregates to theta(1) if your searches follow the Pareto law
- popular keys are less likely to be evicted
Because your buckets are more relevant, you can also make them smaller, reducing the k time in an O(nk) complexity over n searches and decreasing the amount of cache thrashing.
- jorangreef 8y agoIf I understand you correctly, CLOCK LRU works like this, except without the memcpy swapping cost. https://en.wikipedia.org/wiki/Page_replacement_algorithm#Clock https://en.wikipedia.org/wiki/Page_replacement_algorithm#Clo...
- deleted 8y ago[deleted]
- CoolGuySteve 8y agoIn order for the scan to be most efficient in cache, you need to store key-reference pairs in the buckets, so the swap cost should only be a couple instructions rather than a memcpy.
- jandrewrogers 8y agoA concern with using LRU eviction is that the behavior is sensitive to how accesses are distributed over time. The useful property of random eviction versus LRU eviction is that performance falls within a narrow bound: best case scenario is worse, but worst case scenario is better. I think this use case is valuing predictability. The main reason most databases use one of the myriad clock sweep eviction variants instead of true LRU eviction is that they ensure more uniform performance over all possible sequences of a given non-uniform distribution of accesses -- most of the upside of an LRU while (especially in clever variants) avoiding most of the downside as well.