Stan Hoeppner put forth on 11/4/2010 9:20 PM: > Wietse Venema put forth on 11/4/2010 7:30 PM: >> Stan Hoeppner: >>> What's the CIDR lookup table performance difference between say 256 /32 >>> entries and a single /24 entry? Is it 256:1? >> >> One /32 match is a probably a little faster than one /24 match. >> The difference depends on compiler and hardware used. >> >> The CIDR implementation could be sped up by using IF/ELSE/ENDIF as >> in pcre and regexp tables. Adding that is much more work than it >> was with pcre or regexp. >> >>> Or, how about 90,000 /32 >>> entries vs 60,000 entries that consolidate many of those 90,000 /32s >>> into larger CIDRs such as /24s and /21s etc? I have no idea what the >>> total processing time would be on such size CIDRs. Is it small enough >>> to be irrelevant, or are we looking at something like multiple seconds >>> per lookup (obviously dependent on hardware)? >> >> Try measuring it on a few systems. > > Is using "time postmap -q 1.1.1.1 cidr:./map.pcre" a realistic test method?
In my informal testing with postmap -q I'm seeing something I wouldn't have expected. The results seem to show that the total size of the map file has more of an impact on search time than the number or order of entries. -rw-r--r-- 1 root root 1.4M Nov 4 03:58 dnswl -rw-r--r-- 1 root root 2.9M Nov 4 21:37 dnswl.tst $ cat dnswl|wc -l 63120 $ cat dnswl.tst|wc -l 63120 $ time postmap -q "192.220.88.224" cidr:./dnswl OK real 0m0.383s user 0m0.352s sys 0m0.028s $ time postmap -q "192.220.88.224" cidr:./dnswl.tst permit_auth_destination real 0m0.483s user 0m0.420s sys 0m0.060s $ time postmap -q "65.41.216.221" cidr:./dnswl OK real 0m0.372s user 0m0.328s sys 0m0.040s $ time postmap -q "65.41.216.221" cidr:./dnswl.tst permit_auth_destination real 0m0.478s user 0m0.424s sys 0m0.052s The original postfix-dnswl-permit file: -rw-r--r-- 1 root root 3.5M Nov 4 03:21 postfix-dnswl-permit $ cat postfix-dnswl-permit|wc -l 88506 x$ time postmap -q "192.220.88.224" cidr:./postfix-dnswl-permit permit_auth_destination real 0m0.673s user 0m0.604s sys 0m0.068s $ time postmap -q "65.41.216.221" cidr:./postfix-dnswl-permit permit_auth_destination real 0m0.679s user 0m0.624s sys 0m0.056s The two test files are the output of running postfix-dnswl-permit through a CIDR consolidating perl script which merges multiple CIDRs into a larger CIDR when possible. This cut the number of entries in the table from 88506 to 63120. The only difference between the two test files is the action. The number of bytes in "permit_auth_destination" is sufficient to double the file size vs the byte count of "OK". Interestingly, there seems to be no difference in elapsed time when searching for the first entry, the last entry, or something in the middle. This seems to contradict Jeroen's recommendation "And always, definitely, list the largest ranges first." >From my rudimentary testing, ordering within the file seems to make little difference WRT search time. What seems to make the most difference is the action itself, or more likely, the number of bytes of the action changing the total file size. My testing was performed on a very low performance system so others may see much lower times. The timed results above show a direct correlation, almost a linear slope, between table file size and lookup time, independent of the number of table entries. Is indicative of Postfix behavior, possibly the way my Linux system and libraries are setup, or the nature of the hardware in my test system? This CPU only has 512KB of L2 cache. The Postfix binaries I am running are version 2.5.5 Debian Lenny. I don't know what GCC optimizations were used when compiling. This is a 32 bit i686 system with kernel.org kernel 2.6.34.1 rolled by yours truly. Based on the above testing, even having gargantuan CIDR files shouldn't be much of a performance impact on smtpd processes for low to mid volume servers. Adding a fraction of a second to extremely high volume servers may have an impact, given all the other smptd checks we have our systems perform. Given the difference is lookup performance between using an "OK" action and a "permit_auth_destination" action, is using "OK" in such a whitelist manner suitable? If not, could another action of shorter word length be used in order to cut down on file size thus increasing lookup performance? I gotta say this is pretty interesting stuff. I didn't expect these results, and am surprised the code performs in this manner, if indeed it's the code, and not my platform, showing these results. -- Stan
