Re: [Dnsmasq-discuss] [Request for Comments] Optimized Nearest-Domain Lookup
On Fri, Feb 22, 2013 at 7:05 AM, Jason A. Donenfeld wrote: > > > On Wed, Feb 20, 2013 at 3:17 PM, Kaspar Schleiser wrote: > >> Could you elaborate on how your tree works? > > > Went ahead and annotated the source: > http://git.zx2c4.com/domain-lookup-tree/tree/domain-lookup.c > Should be way easier to understand what's up. > > ___ > Dnsmasq-discuss mailing list > Dnsmasq-discuss@lists.thekelleys.org.uk > http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss > > i have an indexed version of this , a bit more memory consuming... https://code.google.com/p/dnsmasq-guard/source/browse/src/filter.c nodes are letter -- - () ascii ribbon campaign - against html e-mail /\ ___ Dnsmasq-discuss mailing list Dnsmasq-discuss@lists.thekelleys.org.uk http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss
Re: [Dnsmasq-discuss] [Request for Comments] Optimized Nearest-Domain Lookup
On Wed, Feb 20, 2013 at 3:17 PM, Kaspar Schleiser wrote: > > Could you elaborate on how your tree works? Went ahead and annotated the source: http://git.zx2c4.com/domain-lookup-tree/tree/domain-lookup.c Should be way easier to understand what's up. ___ Dnsmasq-discuss mailing list Dnsmasq-discuss@lists.thekelleys.org.uk http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss
Re: [Dnsmasq-discuss] [Request for Comments] Optimized Nearest-Domain Lookup
On Wed, Feb 20, 2013 at 9:53 PM, Jason A. Donenfeld wrote: > Okie dokie, benchmark time! 2012 Intel Core i7, gcc 4.7.2. > Looks like gcc was optimizing out the legacy test. Fixed that, and added some data verification. zx2c4@thinkpad ~/Projects/domain-lookup-tree $ make cc -march=native -pipe -fomit-frame-pointer -flto -O3test.c domain-lookup.c domain-lookup.h -o test cc -march=native -pipe -fomit-frame-pointer -flto -O3benchmark.c domain-lookup.c domain-lookup.h -o benchmark zx2c4@thinkpad ~/Projects/domain-lookup-tree $ ./benchmark [+] Populating in memory word list. [+] Creating random lists of domains to query. [+] Populating domain lookup tree. [+] Performing lookup benchmarks: [*] New method took 0.37 seconds. [*] Old method took 188.77 seconds. [+] Verifying that new and old methods produced identical results: [*] New and old methods produced the same results. ___ Dnsmasq-discuss mailing list Dnsmasq-discuss@lists.thekelleys.org.uk http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss
Re: [Dnsmasq-discuss] [Request for Comments] Optimized Nearest-Domain Lookup
On Wed, Feb 20, 2013 at 5:46 PM, Simon Kelley wrote: > > I'm > currently snowed under (at least partially with your earlier good work) > so I may not get to this for a while. No problem. Upstreaming the ipset code is a much bigger priority in my book. This optimization code is mainly just something to play around with. ___ Dnsmasq-discuss mailing list Dnsmasq-discuss@lists.thekelleys.org.uk http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss
Re: [Dnsmasq-discuss] [Request for Comments] Optimized Nearest-Domain Lookup
On Wed, Feb 20, 2013 at 3:17 PM, Kaspar Schleiser wrote: > Did you do any benchmarks? Okie dokie, benchmark time! 2012 Intel Core i7, gcc 4.7.2. With gcc's -O3: zx2c4@thinkpad ~/Projects/domain-lookup-tree $ ./benchmark New method took 0.43 seconds. Old method took 2.75 seconds. Without -O3: zx2c4@thinkpad ~/Projects/domain-lookup-tree $ ./benchmark New method took 0.41 seconds. Old method took 325.94 seconds. Benchmarking code is in previously linked git repository. ___ Dnsmasq-discuss mailing list Dnsmasq-discuss@lists.thekelleys.org.uk http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss
Re: [Dnsmasq-discuss] [Request for Comments] Optimized Nearest-Domain Lookup
On 20/02/13 12:57, Jason A. Donenfeld wrote: > Hi Simon & Folks, > > Currently when dnsmasq processes server=/.../, address=/.../, > local=/.../, ipset=/.../, and similar, it find the nearest match for a > domain name by iterating through all the keys, and keeping track of > which one had the largest match length. This gets the job done and is > fairly, simple. But it also could be optimized quite a bit. > > This might be a bit verbose for dnsmasq's tastes, and maybe the notion > smells a bit too much of "My First Computer Science Data Structure" kind > of thing, but perhaps this might be a welcome optimization. I present > you with domain-lookup-tree, a simple set of C functions that store > domain names in a tree structure: > > http://git.zx2c4.com/domain-lookup-tree/about/ > > It should be relatively straightforward. I wrote it specifically with > dnsmasq in mind, so if you're interested, I'd be thrilled to see it > replace the current nieve matching technique. > > Thoughts? Comments? Ideas? > I've not had time to look at you code yet, but it's worth pointing out that the code you're trying to replace is very old and very gnarly, and very high up the list of "stuff that should be re-written". I'm currently snowed under (at least partially with your earlier good work) so I may not get to this for a while. This email at least puts down a marker that I want to look at it, and if I don't get back to it in few weeks, please remind me. Cheers, Simon. > Jason > > > ___ > Dnsmasq-discuss mailing list > Dnsmasq-discuss@lists.thekelleys.org.uk > http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss > ___ Dnsmasq-discuss mailing list Dnsmasq-discuss@lists.thekelleys.org.uk http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss
Re: [Dnsmasq-discuss] [Request for Comments] Optimized Nearest-Domain Lookup
On Wed, Feb 20, 2013 at 3:17 PM, Kaspar Schleiser wrote: > > Could you elaborate on how your tree works? Did you do any benchmarks? Each node represents a domain component. * -> [com -> [zx2c4 -> [data, blog ], kexec ], org -> [slashdot ] ] It splits the domain string by the period, and then walks the components backward. ___ Dnsmasq-discuss mailing list Dnsmasq-discuss@lists.thekelleys.org.uk http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss
Re: [Dnsmasq-discuss] [Request for Comments] Optimized Nearest-Domain Lookup
Hi Jason, On 02/20/2013 01:57 PM, Jason A. Donenfeld wrote: > Thoughts? Comments? Ideas? Could you elaborate on how your tree works? Did you do any benchmarks? Cheers Kaspar ___ Dnsmasq-discuss mailing list Dnsmasq-discuss@lists.thekelleys.org.uk http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss
[Dnsmasq-discuss] [Request for Comments] Optimized Nearest-Domain Lookup
Hi Simon & Folks, Currently when dnsmasq processes server=/.../, address=/.../, local=/.../, ipset=/.../, and similar, it find the nearest match for a domain name by iterating through all the keys, and keeping track of which one had the largest match length. This gets the job done and is fairly, simple. But it also could be optimized quite a bit. This might be a bit verbose for dnsmasq's tastes, and maybe the notion smells a bit too much of "My First Computer Science Data Structure" kind of thing, but perhaps this might be a welcome optimization. I present you with domain-lookup-tree, a simple set of C functions that store domain names in a tree structure: http://git.zx2c4.com/domain-lookup-tree/about/ It should be relatively straightforward. I wrote it specifically with dnsmasq in mind, so if you're interested, I'd be thrilled to see it replace the current nieve matching technique. Thoughts? Comments? Ideas? Jason ___ Dnsmasq-discuss mailing list Dnsmasq-discuss@lists.thekelleys.org.uk http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss
