> I have done a comparison of the Toeplitz v.s. Jenkins Hash algorithms, > and found that the Toeplitz provides much better distribution of the > connections into send-indirection-table entries. See the data below -- > showing how many TCP connections are distributed into each of the > sixteen table entries. The Toeplitz hash distributes the connections > almost perfectly evenly, but the Jenkins hash distributes them unevenly. > For example, in case of 64 connections, some entries are 0 or 1, some > other entries are 8. This could cause too many connections in one VMBus > channel and slow down the throughput. This is consistent to our test > which showing slower performance while using the generic skb_get_hash > (Jenkins) than using Toeplitz hash (see perf numbers below). > > > #connections:32: > Toeplitz:2,2,2,2,2,1,2,2,2,2,2,3,2,2,2,2, > Jenkins:3,2,2,4,1,1,0,2,1,1,4,3,2,5,1,0, > #connections:64: > Toeplitz:4,4,5,4,4,3,4,4,4,4,4,4,4,4,4,4, > Jenkins:4,5,4,6,3,5,0,6,1,2,8,3,6,8,2,1, > #connections:128: > Toeplitz:8,8,8,8,8,7,9,8,8,8,8,8,8,8,8,8, > Jenkins:8,12,10,9,7,8,3,10,6,8,9,8,10,11,6,3, > These results for Toeplitz are not plausible. Given random input you cannot expect any hash function to produce such uniform results. I suspect either your input data is biased or how your applying the hash is. When I run 64 random IPv4 3-tuples through Toeplitz and Jenkins I get something more reasonable: Toeplitz Buckets: 3 7 4 5 3 6 2 6 2 4 4 5 4 3 2 4 Jenkins Buckets: 6 7 4 4 3 2 6 3 1 4 3 5 5 4 4 3 > Throughput (Gbps) comparison: > #conn Toeplitz Jenkins > 32 26.6 23.2 > 64 32.1 23.4 > 128 29.1 24.1 > > For long term solution, I think we should put the Toeplitz hash as > another option to the generic hash function in kernel... But, for the > time being, can you accept this patch to fix the assumptions on > struct flow_keys layout? > Toeplitz is about a 100x more expensive to compute in the CPU than Jenkins, we can get that down to 50x by precomputing a bunch of lookup tables for a given key but that is at the expense of memory. Besides that, there is a fair amount of analysis already showing that Jenkins hash provides a good distribution and has good enough (though not great) Avalanche effect. Probably the only reason we would need Toeplitz in SW is if we wanted to match a computation being done by HW. One hash that might be better than Jenkins is CRC. This seems to have good uniformity and Avalanche effect, and by using crc32 instruction it seems be a little faster than running Jenkins hash. Tom > Thanks, > - Haiyang > _______________________________________________ devel mailing list devel@xxxxxxxxxxxxxxxxxxxxxx http://driverdev.linuxdriverproject.org/mailman/listinfo/driverdev-devel
