> 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@lists.openwrt.org https://lists.openwrt.org/cgi-bin/mailman/listinfo/openwrt-devel