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 0E24BA0562; Tue, 31 Mar 2020 21:56:00 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id D6AD21C1F2; Tue, 31 Mar 2020 21:55:58 +0200 (CEST) Received: from new4-smtp.messagingengine.com (new4-smtp.messagingengine.com [66.111.4.230]) by dpdk.org (Postfix) with ESMTP id B91A61C1F1 for ; Tue, 31 Mar 2020 21:55:56 +0200 (CEST) Received: from compute7.internal (compute7.nyi.internal [10.202.2.47]) by mailnew.nyi.internal (Postfix) with ESMTP id 09C2A5806AC; Tue, 31 Mar 2020 15:55:56 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute7.internal (MEProxy); Tue, 31 Mar 2020 15:55:56 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=monjalon.net; h= from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding:content-type; s=mesmtp; bh=Vz4TnUVz/T7QkyYH+8NGcRLGFOh8fnmjkIAvsswYwck=; b=FoGAuvjXvDyG D320z17iWDQ/itDnlUIuNdT/ILp3EIMNLl+AHVdcGwjHJTKwdyrmqDWBO/TtNPzl CgzMgDITmO8iqQn69IAmZ2p9L+cQvSZ+U7/UGpcbquP1QQ40I6NHqsVciTBBIRzD qc3Fx3aKj2w5wpDTEbBhPoS3DvGQ+5A= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm2; bh=Vz4TnUVz/T7QkyYH+8NGcRLGFOh8fnmjkIAvsswYw ck=; b=qP97ymTPgHyIWflKWUXLs6LOSZkzU0Jt3RwBEd7Dst+GahFqPyWFJmr6I D6E10vjf2BuDCEMZDq/qAV7BUchzaaGOfKthsVvmaMt6PUmxrkiZQ29iJj7RFSpX NIeQzTnQHZUcwo5ybzhmZKLDxTNkJkYG89Syr2RjD8gbKacXs1+ymPk+j+eeFEnR D0huk+KlSCKgVSH0d35BpI093Mb06C4sevNDxc43WQHD8urGrRGlAy2Z0tzajSHh 5IzmceDt6bSDsAVnPoNhzMydcyPxwwT7BgtKEd1+joFJUFrAObPEMazUuGo/2aWM MWX5fr6mNzVeXCsM147CXJqHocFZg== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduhedrtddtgddutdelucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne cujfgurhephffvufffkfgjfhgggfgtsehtqhertddttddunecuhfhrohhmpefvhhhomhgr shcuofhonhhjrghlohhnuceothhhohhmrghssehmohhnjhgrlhhonhdrnhgvtheqnecuff homhgrihhnpeguphgukhdrohhrghenucfkphepjeejrddufeegrddvtdefrddukeegnecu vehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepthhhohhmrg hssehmohhnjhgrlhhonhdrnhgvth X-ME-Proxy: Received: from xps.localnet (184.203.134.77.rev.sfr.net [77.134.203.184]) by mail.messagingengine.com (Postfix) with ESMTPA id 4CCC0306CBD7; Tue, 31 Mar 2020 15:55:53 -0400 (EDT) From: Thomas Monjalon To: "Medvedkin, Vladimir" Cc: "Wang, Yipeng1" , Stephen Hemminger , dev@dpdk.org, Morten =?ISO-8859-1?Q?Br=F8rup?= , "dev@dpdk.org" , "Ananyev, Konstantin" , "Gobriel, Sameh" , "Richardson, Bruce" , Suanming Mou , Olivier Matz , "Xueming(Steven) Li" , Andrew Rybchenko , Asaf Penso , Ori Kam Date: Tue, 31 Mar 2020 21:55:52 +0200 Message-ID: <4749580.haC6HkEk0m@xps> In-Reply-To: <3aa4f601-aaab-223f-8882-79b51f2e9251@intel.com> References: <3aa4f601-aaab-223f-8882-79b51f2e9251@intel.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="iso-8859-1" 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" 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 > >>>>> 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 int3= 2_t, > >> instead of using a growing list of creative synonyms for the same thin= g? > >> 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 ind= icate > >> 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 Yes some work is in progress to propose a new memory allocator for small objects 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 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. >=20 > The main reason for this new hash library is performance. As I mentioned= =20 > earlier, the current rte_fbk implementation is pretty fast but it has a=20 > number of drawbacks such as 2 byte values and limited collision=20 > resolving capabilities. On the other hand, rte_hash (cuckoo hash)=20 > 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 location= =20 > 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 byte=20 > key size. Replacing it with a new implementation gives about 30% in=20 > 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