Paul Vixie wrote: > Ted Lemon wrote: > >>How deep do you expect the name tree to get? I rarely see anything > >>more than four levels deep, and three times through the loop isn't > >>a whole lot. > > > >Er, if on average you have to do three hash lookups instead of one, > >and hash lookups are the main expense to answering a query, then that > >would be 66% performance reduction on average on _every_ query. That's > >pretty significant. Am I missing something? Why does this sound like > >"not a whole lot" to you? > > i think if flattened hashing is an inefficient way to implement a dns > cache, then it should and will fall out of favour. in 2002 or so, for a > non-open-source project, we (vernon schryver and myself) implemented a > dns cache as a recursive hash table in the general style of bind4/bind8, > but with strong module boundaries, and arrays for sparse child-sets that > morphed into variable sized hash tables when density increased. this is > where resimprove-00's nxdomain treatment was first implemented, and it > worked well, and it the whole thing was extremely fast, as well as memory > efficient. > > so whenever i hear words like "that'll be slow for flat-hash dns caches" it > reminds me of the joke that begins "doctor, it hurts when i do $this" and > ends with "well, then don't do $this".
OTOH, modern non-cryptographic hash functions (e.g., xxHash, CityHash, etc.) are extremely fast. If the cost of performing a few extra hashes and extra hash table lookups add significant expense to answering a query, then the rest of the system has been impressively well-optimized. -- Robert Edmonds _______________________________________________ DNSOP mailing list DNSOP@ietf.org https://www.ietf.org/mailman/listinfo/dnsop
