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 CB931A057B; Wed, 1 Apr 2020 20:31:06 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 1812E1C0C7; Wed, 1 Apr 2020 20:31:06 +0200 (CEST) Received: from mga03.intel.com (mga03.intel.com [134.134.136.65]) by dpdk.org (Postfix) with ESMTP id D23911BEBC for ; Wed, 1 Apr 2020 20:31:03 +0200 (CEST) IronPort-SDR: eRKcC6tBVXu9mp2rdpydecbgQdeEMF6oUv7aurxCiPkSg/2/RvU06P7wZnbAAr5oU1dh2JXvqp SLrN1um73GQw== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga007.jf.intel.com ([10.7.209.58]) by orsmga103.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 01 Apr 2020 11:31:02 -0700 IronPort-SDR: 3NKZJIuO1Qar1aaQCchgFBFV7+XW+u8NswCvIymSRo2nlZq97dyTC1EAG0PdzOWB+5BF/gvvHd vRwjbdEYpwmw== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.72,332,1580803200"; d="scan'208";a="238266892" Received: from irsmsx103.ger.corp.intel.com ([163.33.3.157]) by orsmga007.jf.intel.com with ESMTP; 01 Apr 2020 11:31:00 -0700 Received: from irsmsx602.ger.corp.intel.com (163.33.146.8) by IRSMSX103.ger.corp.intel.com (163.33.3.157) with Microsoft SMTP Server (TLS) id 14.3.439.0; Wed, 1 Apr 2020 19:28:01 +0100 Received: from irsmsx605.ger.corp.intel.com (163.33.146.138) by irsmsx602.ger.corp.intel.com (163.33.146.8) 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:28:01 +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:28:01 +0100 From: "Medvedkin, Vladimir" To: Thomas Monjalon 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 Thread-Topic: [dpdk-dev] [PATCH 0/3] add new Double Word Key hash table Thread-Index: AQHV+5hB9J6rNOeMKU+Ecxs7OcA+JahLSk+AgAA/pgCAABI5gIABl84AgA38wYCAB/QSAIABif1w Date: Wed, 1 Apr 2020 18:28:00 +0000 Message-ID: <52b1d35cb20448b28820e9a510f9ce94@intel.com> References: <3aa4f601-aaab-223f-8882-79b51f2e9251@intel.com> <4749580.haC6HkEk0m@xps> In-Reply-To: <4749580.haC6HkEk0m@xps> 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 Thomas, -----Original Message----- From: Thomas Monjalon =20 Sent: Tuesday, March 31, 2020 8:56 PM To: 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 Subject: Re: [dpdk-dev] [PATCH 0/3] add new Double Word Key hash table 26/03/2020 18:28, Medvedkin, Vladimir: > Hi Yipeng, Stephen, all, >=20 > On 17/03/2020 19:52, Wang, Yipeng1 wrote: > > From: Stephen Hemminger > >> On Mon, 16 Mar 2020 18:27:40 +0000 > >> "Medvedkin, Vladimir" 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 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 the=20 > >>>>> 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=20 > >> 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=20 > >>> to rename it "dwk", so that there was no confusion with the=20 > >>> existing FBK library. Naming suggestions are welcome! > >>> > >>>> And if the value size is fixed too, perhaps the name should also=20 > >>>> 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 32=20 > >> bit values (in addition to > >> 16 bit values in FBK and 64 bit in DWK) would be nice combination=20 > >> with that library. > >>>> [1]: http://mails.dpdk.org/archives/dev/2019-October/147513.html Yes some work is in progress to propose a new memory allocator for small ob= jects of fixed size with small memory overhead. > >> Why is this different (or better) than existing rte_hash. > >> Having more flavors is not necessarily a good thing (except in=20 > >> Gelato) > > [Wang, Yipeng] > > Hi, Vladimir, > > As Stephen mentioned, I think it is good idea to explain the benefit=20 > > of this new type of hash table more explicitly such as Specific use cas= es, differences with current rte_hash, and performance numbers, etc. >=20 > 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 (cuckoo=20 > hash) doesn't have this drawbacks but at the cost of lower performance=20 > comparing to rte_fbk. >=20 > If I understand correctly, performance penalty are due to : >=20 > 1. Load two buckets >=20 > 2. First compare signatures >=20 > 3. If signature comparison hits get a key index and find memory=20 > location with a key itself and get the key >=20 > 4. Using indirect call to memcmp() to compare two uint32_t. >=20 > The new proposed 4 byte key hash table doesn't have rte_fbk drawbacks=20 > while offers the same performance as rte_fbk. >=20 > 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 30%=20 > in performance. >=20 > The main disadvantage comparing to rte_hash is some performance=20 > degradation with high average table utilization due to chain resolving=20 > for 5th and subsequent collision. Thanks for explaining. Please, such information should added in the documentation: doc/guides/prog_guide/hash_lib.rst I'm going to submit v2 this week, will add documentation update.