[OpenWrt-Devel] Slow DNSMasq with > 100, 000 entries in additional addresses file

[Juliusz Chroboczek]

> I also fiddled a bit with bloom filters, which strike me as appropo.

Bloom filters trade accuracy for space -- they're arbitrarily smaller than
hash tables, but at the cost of causing more false positives.  Since your
tests indicate that perfect hash tables are small enough, a Bloom filter
would probably not be useful here.

If I had a few days to spare on the issue, I'd rework the data structures
in dnsmasq to deal with that case.  While I haven't looked at the dnsmasq
code, 100 000 entries is not a lot, if dnsmasq cannot deal with that, it's
probably using very naive data structures, it should be easy enough to use
something better.

(I'd use a B-tree, by the way, which is a pain to implement but should
give much better performance than open hashing.  If you're too lazy to
implement B-trees, then use pre-randomized binary search trees, they
should be just as good as AVL or RB-trees and trivial to implement.)

-- Juliusz
_______________________________________________
openwrt-devel mailing list
openwrt-devel at lists.openwrt.org
https://lists.openwrt.org/cgi-bin/mailman/listinfo/openwrt-devel