Implement faster match result cache
Background
Request blocking in Adblock Plus is now so fast that the current caching of match results makes no significant difference. In fact, with subsequent changes (#28 (closed), !85 (closed), etc.), the cache is going to become a liability. We could either get rid of the cache entirely or implement something smarter. This is a proposal to do the latter.
Instead of a Map
object (hash table), we could just use an array of "slots" and keep only the last key in its corresponding slot. For example, we could have an array of 64 elements. The key for a request would be "hashed" to a value between 0 and 63 and both the key and the value would be entered in the slot at that index. If a key with the same hash comes up for matching, and if this key is exactly equal to the last key entered in the slot, we would then return the corresponding value in the slot instead of recomputing it.
Here is some pseudocode to explain this:
// Creation of the cache.
cache = new Array(64).fill(null).map(() => ({key: null, value: null}));
// Looking up the last entry and returning the value if the key matches
// the current key.
if (cache[key.length % 64].key == key)
return cache[key.length % 64].value;
// Setting the newly computed value.
cache[key.length % 64].key = key;
cache[key.length % 64].value = value;
In the above example, we have a cache with 64 slots. For every key, we hash it by taking the remainder of the key length after dividing it by 64. In other words, we keep up to 64 key-value pairs. If a new key matches an existing key, we return the corresponding value; otherwise we overwrite the last key-value pair with the new one.
This is fast and memory efficient.
An implementation with 64 slots seems to have a good distribution. In practice against real browsing data, it gives a hit rate (very approximately) between 40% and 80% of the current hit rate.
What to change
To be determined.