From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga02.intel.com (mga02.intel.com [134.134.136.20]) by dpdk.org (Postfix) with ESMTP id C27BDB6AB for ; Fri, 3 Apr 2015 22:28:13 +0200 (CEST) Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by orsmga101.jf.intel.com with ESMTP; 03 Apr 2015 13:28:13 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.11,519,1422950400"; d="scan'208,217";a="703056478" Received: from irsmsx104.ger.corp.intel.com ([163.33.3.159]) by fmsmga002.fm.intel.com with ESMTP; 03 Apr 2015 13:28:07 -0700 Received: from irsmsx108.ger.corp.intel.com ([169.254.11.216]) by IRSMSX104.ger.corp.intel.com ([169.254.3.49]) with mapi id 14.03.0224.002; Fri, 3 Apr 2015 21:28:06 +0100 From: "De Lara Guarch, Pablo" To: "dev@dpdk.org" Thread-Topic: [RFC] Cuckoo hash for DPDK 2.1 Thread-Index: AdBuTK/NK5NYsl/6SGC4K3F3r9Jwjg== Date: Fri, 3 Apr 2015 20:28:06 +0000 Message-ID: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [163.33.239.181] MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable X-Content-Filtered-By: Mailman/MimeDel 2.1.15 Subject: [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: Fri, 03 Apr 2015 20:28:14 -0000 Hi all, This RFC is to describe a proposed replacement for the existing rte_hash im= plementation, using the cuckoo hash scheme (see http://www.cs.cmu.edu/~dongz/papers/cucko= oswitch.pdf), which should provide better performance, in terms of lookup time, as well a= s a higher load factor. This new implementation also shall offer several improvements compared to t= he existing one, such as: - Data return: existing implementation returns an index to the bucke= t 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 the = existing 64 bytes, without having a big penalty on performance - Increased burst size: current implementation only allows 16 lookup= s at the same time, whereas the new implementation shall allow more than that (probably 64) - Opening addressing: current implementation does not allow new keys= to be added if its target bucket is full, whereas with Cuckoo hash, it offers an altern= ative location to store the key. I am currently working on the implementation, considering several options: - Using a single table to store all the signatures, regardless they = have used their primary or secondary hash function. - Using two tables to store the signatures, one for primary hashes a= nd 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