Cache tables
fgiesen.wordpress.com
fgiesen.wordpress.com
/* Add the specified entry to the cache of recently seen ICAO addresses.
* Note that we also add a timestamp so that we can make sure that the
* entry is only valid for MODES_ICAO_CACHE_TTL seconds. */
void addRecentlySeenICAOAddr(uint32_t addr) {
uint32_t h = ICAOCacheHashAddress(addr);
Modes.icao_cache[h*2] = addr;
Modes.icao_cache[h*2+1] = (uint32_t) time(NULL);
}
/* Returns 1 if the specified ICAO address was seen in a DF format with
* proper checksum (not xored with address) no more than * MODES_ICAO_CACHE_TTL
* seconds ago. Otherwise returns 0. */
int ICAOAddressWasRecentlySeen(uint32_t addr) {
uint32_t h = ICAOCacheHashAddress(addr);
uint32_t a = Modes.icao_cache[h*2];
uint32_t t = Modes.icao_cache[h*2+1];
return a && a == addr && time(NULL)-t <= MODES_ICAO_CACHE_TTL;
}
As you can see adding a timestamp you can give a TTL to the cached entry validity without any additional effort: in that case you don't need to purge the hash table of old entries eventually, because the cache table is fixed size and the entires will get replaced.The linked article is about having multiple entries per open indexed hash entry, and sizing them to take advantage of cache line sizes.
Your code seems like it basically turns each open index entry into a struct of hash code and timestamp and then compares the timestamp on lookup. This just isn't clear because of how you store the timestamp in odd table offsets after shifting the bottom bit off the hash.
You could take your hash code / timestamp pair and use the articles cache line packing together really (at the cost of half the line).
If anyone is interested, I wrote @ronomon/hash-table as a fast, scalable cuckoo hash table for Node.js.
It has high load factor, constant lookup time in the worst-case and uses a non-recursive variant of the cuckoo probing scheme, together with a bloom filter to reduce cache misses to the alternative cuckoo bucket by an order of magnitude.
Last but not least, caching is supported according to the CLOCK LRU algorithm, which is elegant and effective.
Benchmarks and design decisions are in the README:
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.
https://en.wikipedia.org/wiki/Page_replacement_algorithm#Clo...
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.
Most data structures that rely on a chain of items can be improved by bucketing for cache lines (even linked lists).
I've also implemented 32 byte multi-buckets for a cuckoo hash scheme to try and balance search time and memory usages (you can get extremely high load factors using this approach). I don't think this approach is any better than a few other similar multiple-hashing schemes though.
I have tried keeping the hashs together in memory and using SSE compare instructions to do the comparison/mask of the entire bucket in a couple instructions, but have found the technique hit/miss.