From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id A76F5A057C; Thu, 26 Mar 2020 18:28:36 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id D8F8A1C07E; Thu, 26 Mar 2020 18:28:35 +0100 (CET) Received: from mga02.intel.com (mga02.intel.com [134.134.136.20]) by dpdk.org (Postfix) with ESMTP id 58441374C for ; Thu, 26 Mar 2020 18:28:34 +0100 (CET) IronPort-SDR: BOieu4iuzMg6iOqShsEtfMzphzN5rXltMUYoWXAAnJCLsf7+Iou2SN7jrOh/tF9eYOLIIcKcLq CWwcqOe6WmIw== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga005.jf.intel.com ([10.7.209.41]) by orsmga101.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 26 Mar 2020 10:28:33 -0700 IronPort-SDR: 8HjUCWcYph/jF0MKF44Vkbn2YRKBn5l9No8B2tO8oj94jINwIYE8IXnHUh1ftJnn2n/FPfDFHe LFtLpAzvtcbg== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.72,309,1580803200"; d="scan'208,217";a="420793275" Received: from vmedvedk-mobl.ger.corp.intel.com (HELO [10.252.5.14]) ([10.252.5.14]) by orsmga005.jf.intel.com with ESMTP; 26 Mar 2020 10:28:29 -0700 To: "Wang, Yipeng1" , Stephen Hemminger Cc: =?UTF-8?Q?Morten_Br=c3=b8rup?= , "dev@dpdk.org" , "Ananyev, Konstantin" , "Gobriel, Sameh" , "Richardson, Bruce" , Suanming Mou , Olivier Matz , "Xueming(Steven) Li" , Andrew Rybchenko , Asaf Penso , Ori Kam References: <98CBD80474FA8B44BF855DF32C47DC35C60ED7@smartserver.smartshare.dk> <2baf9a76-a606-d376-dcce-b95c80fc6bb2@intel.com> <20200316123253.7566d799@hermes.lan> From: "Medvedkin, Vladimir" Message-ID: <3aa4f601-aaab-223f-8882-79b51f2e9251@intel.com> Date: Thu, 26 Mar 2020 17:28:29 +0000 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.6.0 MIME-Version: 1.0 In-Reply-To: Content-Language: en-US Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Content-Filtered-By: Mailman/MimeDel 2.1.15 Subject: Re: [dpdk-dev] [PATCH 0/3] add new Double Word Key hash table X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Hi Yipeng, Stephen, all, On 17/03/2020 19:52, Wang, Yipeng1 wrote: >> -----Original Message----- >> From: Stephen Hemminger >> Sent: Monday, March 16, 2020 12:33 PM >> To: Medvedkin, Vladimir >> Cc: Morten Brørup ; dev@dpdk.org; >> Ananyev, Konstantin ; Wang, Yipeng1 >> ; Gobriel, Sameh ; >> Richardson, Bruce ; Suanming Mou >> ; Olivier Matz ; >> Xueming(Steven) Li ; Andrew Rybchenko >> ; Asaf Penso ; Ori Kam >> >> Subject: Re: [dpdk-dev] [PATCH 0/3] add new Double Word Key hash table >> >> On Mon, 16 Mar 2020 18:27:40 +0000 >> "Medvedkin, Vladimir" wrote: >> >>> Hi Morten, >>> >>> >>> On 16/03/2020 14:39, Morten Brørup wrote: >>>>> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Vladimir >>>>> Medvedkin >>>>> Sent: Monday, March 16, 2020 2:38 PM >>>>> >>>>> Currently DPDK has a special implementation of a hash table for >>>>> 4 byte keys which is called FBK hash. Unfortunately its main >>>>> drawback is that it only supports 2 byte values. >>>>> The new implementation called DWK (double word key) hash supports 8 >>>>> byte values, which is enough to store a pointer. >>>>> >>>>> It would also be nice to get feedback on whether to leave the old >>>>> FBK and new DWK implementations, or whether to deprecate the old >> one? >>>> >>>> >>>> Who comes up with these names?!? >>>> >>>> FBK (Four Byte Key) and DWK (Double Word Key) is supposed to mean >> the same. Could you use 32 somewhere in the name instead, like in int32_t, >> instead of using a growing list of creative synonyms for the same thing? >> Pretty please, with a cherry on top! >>> >>> That's true, at first I named it as fbk2, but then it was decided to >>> rename it "dwk", so that there was no confusion with the existing FBK >>> library. Naming suggestions are welcome! >>> >>>> And if the value size is fixed too, perhaps the name should also indicate >> the value size. >>>> >>>> >>>> It's a shame we don't have C++ class templates available in DPDK... >>>> >>>> In other news, Mellanox has sent an RFC for an "indexed memory pool" >> library [1] to conserve memory by using uintXX_t instead of pointers, so >> perhaps a variant of a 32 bit key hash library with 32 bit values (in addition to >> 16 bit values in FBK and 64 bit in DWK) would be nice combination with that >> library. >>>> [1]: http://mails.dpdk.org/archives/dev/2019-October/147513.html >>>> >>>> >>>> Med venlig hilsen / kind regards >>>> - Morten Brørup >>>> >> Why is this different (or better) than existing rte_hash. >> Having more flavors is not necessarily a good thing (except in Gelato) > [Wang, Yipeng] > Hi, Vladimir, > As Stephen mentioned, I think it is good idea to explain the benefit of this new type of hash table more explicitly such as > Specific use cases, differences with current rte_hash, and performance numbers, etc. The main reason for this new hash library is performance. As I mentioned earlier, the current rte_fbk implementation is pretty fast but it has a number of drawbacks such as 2 byte values and limited collision resolving capabilities. On the other hand, rte_hash (cuckoo hash) doesn't have this drawbacks but at the cost of lower performance comparing to rte_fbk. If I understand correctly, performance penalty are due to : 1. Load two buckets 2. First compare signatures 3. If signature comparison hits get a key index and find memory location with a key itself and get the key 4. Using indirect call to memcmp() to compare two uint32_t. The new proposed 4 byte key hash table doesn't have rte_fbk drawbacks while offers the same performance as rte_fbk. Regarding use cases, in rte_ipsec_sad we are using rte_hash with 4 byte key size. Replacing it with a new implementation gives about 30% in performance. The main disadvantage comparing to rte_hash is some performance degradation with high average table utilization due to chain resolving for 5th and subsequent collision. -- Regards, Vladimir