3 ms·
I use this technique often and I love the simplicity it has. If you want to see a real-world usage, there is one in https://github.com/antirez/dump1090 https://
by antirez 8y ago
I use this technique often and I love the simplicity it has. If you want to see a real-world usage, there is one in https://github.com/antirez/dump1090 https://github.com/antirez/dump1090:
/* 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.
- CoolGuySteve 8y agoIs there a reason why you store at h*2 instead of making icao_cache an array of "struct { uint32_t a; uint32_t t; }"?
- antirez 8y agoNope, I guess I was in an assembly mood :-D
- jnordwick 8y agoI don't really see how this applies to the post, or am I missing something? 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).
- antirez 8y agoI think that the main point of the blog post, is that instead of an exact match in O(N) worst time, you change the algorithm in order to replace the entry when adding, so that the lookup time also is always O(1) and the size is bound. The cacheline thing is just an optimization in order get the best out of the single cache miss you incurred. The table offset I use is the manual version of what you would do with a struct, no differences in the generated code more or less: the entry and the timestamp are stored at sequential addresses.
- jnordwick 8y agoI can see that a little. It is a good article regardless what you drew from it. I found it more of a lossy set membership test that used packed cache lines to help in performance (over chaining), but I don't really know what his use case was. Good write up none the less.