From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756023AbcANROQ (ORCPT ); Thu, 14 Jan 2016 12:14:16 -0500 Received: from mail-ig0-f182.google.com ([209.85.213.182]:35293 "EHLO mail-ig0-f182.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755860AbcANRON (ORCPT ); Thu, 14 Jan 2016 12:14:13 -0500 MIME-Version: 1.0 In-Reply-To: References: <1452159189-11473-1-git-send-email-vkuznets@redhat.com> <20160110.172558.367101858392871618.davem@davemloft.net> Date: Thu, 14 Jan 2016 09:14:12 -0800 Message-ID: Subject: Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct flow_keys layout From: Tom Herbert To: Haiyang Zhang Cc: David Miller , "vkuznets@redhat.com" , "netdev@vger.kernel.org" , KY Srinivasan , "devel@linuxdriverproject.org" , "linux-kernel@vger.kernel.org" , "eric.dumazet@gmail.com" Content-Type: text/plain; charset=UTF-8 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org > 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 > From mboxrd@z Thu Jan 1 00:00:00 1970 From: Tom Herbert Subject: Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct flow_keys layout Date: Thu, 14 Jan 2016 09:14:12 -0800 Message-ID: References: <1452159189-11473-1-git-send-email-vkuznets@redhat.com> <20160110.172558.367101858392871618.davem@davemloft.net> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Cc: "eric.dumazet@gmail.com" , "netdev@vger.kernel.org" , "linux-kernel@vger.kernel.org" , "devel@linuxdriverproject.org" , David Miller To: Haiyang Zhang Return-path: In-Reply-To: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: driverdev-devel-bounces@linuxdriverproject.org Sender: "devel" List-Id: netdev.vger.kernel.org > 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 >