Hello Martin, thanks for your numbers.
> with 16384 hashbuckets and a maximum of 131072 tracked connections it took > 7.5 seconds to perform 1 million lookups in the hashtable (using > __ip_conntrack_find from userspace). Was this 1 million lookups to a random hash bucket each, with guaranteed "no match"? Assuming this in the following... That's 8 connections per bucket, resulting in 8 million "pointer chasings" during table lookup, i.e. about 937ns per chasing. > with the same number of hashbuckets (16384) but with a maximum of 262144 > tracked connections (131072 * 2) it took just over 12 seconds to perform > the same test (1 million lookups). Now you have an average chain length of 16, for 16 million chasings total, and 750ns per chasing - probably a bit better (per chasing, not in reality) because the hash array cache line load amortizes over the list length. > and then I doubled the hashsize to 32768 and left the maximum number of > tracked connections at 262144 and performed the test again. > 1 million lookups took 7.5 seconds again despite that I was tracking twice > as many connections as before. You are back again at an average chain length of 8, so this is not surprising. For nothing but pointer chasing, I'd expect about 250ns (main memory RTT) for a single chasing, so your numbers indicate a pretty large "testing overhead". Maybe a different, non-userlevel testing method would be better. best regards Patrick
