From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id AB0F66A95 for ; Wed, 15 Apr 2015 17:09:22 +0200 (CEST) Received: from orsmga003.jf.intel.com ([10.7.209.27]) by orsmga102.jf.intel.com with ESMTP; 15 Apr 2015 08:08:34 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.11,582,1422950400"; d="scan'208";a="556503492" Received: from irsmsx151.ger.corp.intel.com ([163.33.192.59]) by orsmga003.jf.intel.com with ESMTP; 15 Apr 2015 08:08:33 -0700 Received: from irsmsx108.ger.corp.intel.com ([169.254.11.216]) by IRSMSX151.ger.corp.intel.com ([169.254.4.100]) with mapi id 14.03.0224.002; Wed, 15 Apr 2015 16:08:29 +0100 From: "De Lara Guarch, Pablo" To: "yangguangjerry@hotmail.com" Thread-Topic: Re:[dpdk-dev] [RFC] Cuckoo hash for DPDK 2.1 Thread-Index: AQHQcRfAGblJypQFnEWmR3EJsNG/sJ1ONpsQgAAB3LA= Date: Wed, 15 Apr 2015 15:08:28 +0000 Message-ID: References: In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [163.33.239.182] Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Cc: "dev@dpdk.org" Subject: Re: [dpdk-dev] [RFC] Cuckoo hash for DPDK 2.1 X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 15 Apr 2015 15:09:23 -0000 Hi, > From: yangguangjerry@hotmail.com [mailto:yangguangjerry@hotmail.com] > Sent: Tuesday, April 07, 2015 10:46 AM > To: De Lara Guarch, Pablo > Cc: "dev@dpdk.org" > Subject: Re:[dpdk-dev] [RFC] Cuckoo hash for DPDK 2.1 >=20 >=20 > hi=A0Pablo, > =A0=A0=A0 rte_hash uses Jenkins hash (http://burtleburtle.net/bob/hash/ )= in older > dpdk veriosn,which is originated lookup2.c in 1996.Bob Jenkins updates hi= s > hash function named lookup3.c in 2006. The hash function is more faster t= han > lookup2.c. > =A0=A0 why=A0not continue to adopt the new hash function lookup3.c ? I have looked at that and you are right, we can use the new hash function,= =20 so I will send a patch to replace the existing jhash function. Anyway, keep in mind that this is independent of my proposal. In the future implementation I will continue using the existing hash functi= ons, and what is going to change is the hash table behaviour and API, not the ha= sh functions themselves. Thanks, Pablo >=20 >=20 >=20 >=20 >=20 > At 2015-04-04 04:28:06, "De Lara Guarch, Pablo" > wrote: > >Hi all, > > > >This RFC is to describe a proposed replacement for the existing rte_hash > implementation, > >using the cuckoo hash scheme (see > http://www.cs.cmu.edu/~dongz/papers/cuckooswitch.pdf), > >which should provide better performance, in terms of lookup time, as wel= l > as a higher load factor. > > > >This new implementation also shall offer several improvements compared > to the existing one, such as: > > > >- Data return: existing implementation returns an index to the bu= cket > where the key is stored, > > > >whereas the new implementation shall return 8-byte integers or pointers = to > external data. > > > > > > > >- Increased key length: key length shall be increased more than t= he > existing 64 bytes, > > > >without having a big penalty on performance > > > > > > > >- Increased burst size: current implementation only allows 16 loo= kups at > the same time, > > > >whereas the new implementation shall allow more than that (probably 64) > > > > > > > >- Opening addressing: current implementation does not allow new k= eys > to be added > > > >if its target bucket is full, whereas with Cuckoo hash, it offers an alt= ernative > location to store the key. > > > >I am currently working on the implementation, considering several option= s: > > > > > >- Using a single table to store all the signatures, regardless th= ey have > used their primary or secondary hash function. > > > > > > > >- Using two tables to store the signatures, one for primary hashe= s and > another for the secondary hashes. > > > > > >I need to do some testing on both implementations to know which one is > more suitable for DPDK. > > > >Any comments/ideas welcome. > > > >Thanks > >Pablo > > > ________________________________________ > yangguangjerry@hotmail.com