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 7B112A057B; Wed, 1 Apr 2020 20:37:57 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id DA4D51C0C9; Wed, 1 Apr 2020 20:37:56 +0200 (CEST) Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by dpdk.org (Postfix) with ESMTP id 6745B1C0C7 for ; Wed, 1 Apr 2020 20:37:55 +0200 (CEST) IronPort-SDR: bfj3/PYHMC01hZfISY0Q6J1cYeEtg9EoRuoFWoaQQf8pfpwLgW1IYWSx/luCIjE1PWVHi/8SNe pD4tpjW5L61A== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by fmsmga102.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 01 Apr 2020 11:37:54 -0700 IronPort-SDR: rXRm/4Nddn7UdXcHtlqvj+90KUhscJZIAuoCmNxfv39gP0CbCdhI1C+eVNHhMn2lCmKpUZ/Duk SZa0RFXcE3mg== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.72,332,1580803200"; d="scan'208";a="284505775" Received: from irsmsx152.ger.corp.intel.com ([163.33.192.66]) by fmsmga002.fm.intel.com with ESMTP; 01 Apr 2020 11:37:52 -0700 Received: from irsmsx606.ger.corp.intel.com (163.33.146.139) by IRSMSX152.ger.corp.intel.com (163.33.192.66) with Microsoft SMTP Server (TLS) id 14.3.439.0; Wed, 1 Apr 2020 19:37:51 +0100 Received: from irsmsx605.ger.corp.intel.com (163.33.146.138) by IRSMSX606.ger.corp.intel.com (163.33.146.139) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.1713.5; Wed, 1 Apr 2020 19:37:51 +0100 Received: from irsmsx605.ger.corp.intel.com ([163.33.146.138]) by IRSMSX605.ger.corp.intel.com ([163.33.146.138]) with mapi id 15.01.1713.004; Wed, 1 Apr 2020 19:37:51 +0100 From: "Medvedkin, Vladimir" To: Honnappa Nagarahalli , "thomas@monjalon.net" CC: "Wang, Yipeng1" , Stephen Hemminger , "dev@dpdk.org" , =?iso-8859-1?Q?Morten_Br=F8rup?= , "dev@dpdk.org" , "Ananyev, Konstantin" , "Gobriel, Sameh" , "Richardson, Bruce" , Suanming Mou , Olivier Matz , "Xueming(Steven) Li" , Andrew Rybchenko , "Asaf Penso" , Ori Kam , nd , nd Thread-Topic: [dpdk-dev] [PATCH 0/3] add new Double Word Key hash table Thread-Index: AQHV+5hB9J6rNOeMKU+Ecxs7OcA+JahLSk+AgAA/pgCAABI5gIABl84AgA38wYCAB/QSAIAAFrGAgAF0DlA= Date: Wed, 1 Apr 2020 18:37:51 +0000 Message-ID: References: <3aa4f601-aaab-223f-8882-79b51f2e9251@intel.com> <4749580.haC6HkEk0m@xps> In-Reply-To: Accept-Language: en-IE, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: dlp-reaction: no-action dlp-version: 11.2.0.6 dlp-product: dlpe-windows x-originating-ip: [163.33.253.164] Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 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 Honnappa, -----Original Message----- From: Honnappa Nagarahalli =20 Sent: Tuesday, March 31, 2020 10:17 PM To: thomas@monjalon.net; Medvedkin, Vladimir Cc: Wang, Yipeng1 ; Stephen Hemminger ; dev@dpdk.org; Morten Br=F8rup ; = dev@dpdk.org; Ananyev, Konstantin ; Gobriel, = Sameh ; Richardson, Bruce ; Suanming Mou ; Olivier Matz ; Xueming(Steven) Li ; Andrew Rybchenko ; Asaf Penso ; Ori Kam ; nd ; Honnappa Nagarahalli ; nd Subject: RE: [dpdk-dev] [PATCH 0/3] add new Double Word Key hash table >=20 > 26/03/2020 18:28, Medvedkin, Vladimir: > > Hi Yipeng, Stephen, all, > > > > On 17/03/2020 19:52, Wang, Yipeng1 wrote: > > > From: Stephen Hemminger > > >> On Mon, 16 Mar 2020 18:27:40 +0000 "Medvedkin, Vladimir"=20 > > >> wrote: > > >> > > >>> Hi Morten, > > >>> > > >>> > > >>> On 16/03/2020 14:39, Morten Br=F8rup wrote: > > >>>>> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Vladimir=20 > > >>>>> Medvedkin > > >>>>> Sent: Monday, March 16, 2020 2:38 PM > > >>>>> > > >>>>> Currently DPDK has a special implementation of a hash table=20 > > >>>>> for > > >>>>> 4 byte keys which is called FBK hash. Unfortunately its main=20 > > >>>>> drawback is that it only supports 2 byte values. > > >>>>> The new implementation called DWK (double word key) hash=20 > > >>>>> supports 8 byte values, which is enough to store a pointer. > > >>>>> > > >>>>> It would also be nice to get feedback on whether to leave the=20 > > >>>>> old FBK and new DWK implementations, or whether to deprecate=20 > > >>>>> the old > > >> one? > > >>>> > > >>>> > > >>>> Who comes up with these names?!? > > >>>> > > >>>> FBK (Four Byte Key) and DWK (Double Word Key) is supposed to=20 > > >>>> mean > > >> the same. Could you use 32 somewhere in the name instead, like in=20 > > >> int32_t, instead of using a growing list of creative synonyms for=20 > > >> the same > thing? > > >> Pretty please, with a cherry on top! > > >>> > > >>> That's true, at first I named it as fbk2, but then it was=20 > > >>> decided to rename it "dwk", so that there was no confusion with=20 > > >>> the existing FBK library. Naming suggestions are welcome! > > >>> > > >>>> And if the value size is fixed too, perhaps the name should=20 > > >>>> 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=20 > > >> pointers, so perhaps a variant of a 32 bit key hash library with=20 > > >> 32 bit values (in addition to > > >> 16 bit values in FBK and 64 bit in DWK) would be nice combination=20 > > >> with that library. > > >>>> [1]:=20 > > >>>> http://mails.dpdk.org/archives/dev/2019-October/147513.html >=20 > Yes some work is in progress to propose a new memory allocator for=20 > small objects of fixed size with small memory overhead. >=20 >=20 > > >> 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=20 > > > benefit of this new type of hash table more explicitly such as=20 > > > Specific use cases, > differences with current rte_hash, and performance numbers, etc. > > > > The main reason for this new hash library is performance. As I=20 > > mentioned earlier, the current rte_fbk implementation is pretty fast=20 > > but it has a number of drawbacks such as 2 byte values and limited=20 > > collision resolving capabilities. On the other hand, rte_hash=20 > > (cuckoo > > hash) doesn't have this drawbacks but at the cost of lower=20 > > 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=20 > > 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=20 > > drawbacks while offers the same performance as rte_fbk. > > > > Regarding use cases, in rte_ipsec_sad we are using rte_hash with 4=20 > > byte key size. Replacing it with a new implementation gives about=20 > > 30% in performance. > > > > The main disadvantage comparing to rte_hash is some performance=20 > > degradation with high average table utilization due to chain=20 > > resolving for 5th and subsequent collision. rte_hash is linearly scalable across multiple cores for lookup due to lock-= free algorithm. How is the scalability for the new algorithm? This library is scalable as well. It uses almost the same lock-free algorit= hm. The only difference with cuckoo is that cuckoo in lock-free implementat= ion uses single global "change_counter" for all the table, and the proposed= implementation uses fine grained approach with "change_counter" per bucket= . So it should be more scalable with frequent concurrent updates. >=20 > Thanks for explaining. > Please, such information should added in the documentation: > doc/guides/prog_guide/hash_lib.rst >=20 >=20