rec: Add a NetmaskTree-based cache index for ECS entries
The main idea is not to have to go through all the netmask-specific
entries for a given (qname/qtype), but to have to know quickly which
netmask-specific entry is the best match.
To do that we add an index containing a NetmaskTree for each
(qname,qtype), and we then know quickly which entry to get from the
"regular" cache.
Initial benchmarking results:
- inserting non-netmask-specific entries has the same performance ;
- inserting netmask-specific entries is 40% slower because of the additional insertion ;
- looking for a (qname/qtype) that has no netmask-specific entries remains the same ;
- looking for (qname/qtype) with 65k netmask-specific entries but only matching the non-netmask one is around 2000 times faster ;
- looking for (qname/qtype) with 65k netmask-specific entries and matching one is also around 2000 times faster ;
- pruning the cache is a lot slower (from 11 millions/s to 1.8 millions/s)
Remaining issues:
- ANY queries do not use the index ;
- we have to do two lookups
- removal is slower, but might still be good enough
- NetmaskTree.erase() does not compact the tree.
Ideas that didn't seem to work out:
- Storing a pointer of some kind in the NetmaskTree to save a lookup:
caused issues with our generic cache management functions (moving
entries to the front or to the back requires an iterator)
- Keeping the NMT index in the empty Netmak entry (the non-netmask
specific one) save the additional lookup when we have no ECS
entries, but made cache management very awkward because we needed
to keep the non-netmask specific entry around as a place holder
for the ECS index even if it held no data.