From mboxrd@z Thu Jan 1 00:00:00 1970 From: Bruce Richardson Subject: Re: [PATCH v3 00/11] Cuckoo hash Date: Thu, 9 Jul 2015 09:02:53 +0100 Message-ID: <20150709080253.GA8408@bricha3-MOBL3> References: <1435269919-7007-1-git-send-email-pablo.de.lara.guarch@intel.com> <1435530330-10132-1-git-send-email-pablo.de.lara.guarch@intel.com> <49531942.DIgM7i8NQ4@xps13> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Cc: dev@dpdk.org To: Thomas Monjalon Return-path: Received: from mga03.intel.com (mga03.intel.com [134.134.136.65]) by dpdk.org (Postfix) with ESMTP id C5F775A52 for ; Thu, 9 Jul 2015 10:02:57 +0200 (CEST) Content-Disposition: inline In-Reply-To: <49531942.DIgM7i8NQ4@xps13> List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" On Thu, Jul 09, 2015 at 01:23:54AM +0200, Thomas Monjalon wrote: > Bruce, what is the status of this series? > The parts of the series can that are independent of the cuckoo hash update have already been sent out as updates so changes to those can quicker be resolved and merged. Pablo should be sending out a V4 of the cuckoo hash implementation very shortly. /Bruce > 2015-06-28 23:25, Pablo de Lara: > > This patchset is to replace the existing hash library with > > a more efficient and functional approach, using the Cuckoo hash > > method to deal with collisions. This method is based on using > > two different hash functions to have two possible locations > > in the hash table where an entry can be. > > So, if a bucket is full, a new entry can push one of the items > > in that bucket to its alternative location, making space for itself. > > > > Advantages > > ~~~~~~ > > - Offers the option to store more entries when the target bucket is full > > (unlike the previous implementation) > > - Memory efficient: for storing those entries, it is not necessary to > > request new memory, as the entries will be stored in the same table > > - Constant worst lookup time: in worst case scenario, it always takes > > the same time to look up an entry, as there are only two possible locations > > where an entry can be. > > - Storing data: user can store data in the hash table, unlike the > > previous implementation, but he can still use the old API > > > > This implementation tipically offers over 90% utilization. > > Notice that API has been extended, but old API remains. The main > > change in ABI is that rte_hash structure is now private and the > > deprecation of two macros. > > > > Changes in v3: > > > > - Now user can store variable size data, instead of 32 or 64-bit size data, > > using the new parameter "data_len" in rte_hash_parameters > > - Add lookup_bulk_with_hash function in performance unit tests > > - Add new functions that handle data in performance unit tests > > - Remove duplicates in performance unit tests > > - Fix rte_hash_reset, which was not reseting the last entry > [...] > > Pablo de Lara (11): > > eal: add const in prefetch functions > > hash: move rte_hash structure to C file and make it internal > > test/hash: enhance hash unit tests > > test/hash: rename new hash perf unit test back to original name > > hash: replace existing hash library with cuckoo hash implementation > > hash: add new lookup_bulk_with_hash function > > hash: add new function rte_hash_reset > > hash: add new functionality to store data in hash table > > MAINTAINERS: claim responsability for hash library > > doc: announce ABI change of librte_hash > > doc: update hash documentation >