From mboxrd@z Thu Jan 1 00:00:00 1970 From: Bruce Richardson Subject: Re: [PATCH v5 0/7] Cuckoo hash - part 3 of Cuckoo hash Date: Fri, 10 Jul 2015 23:52:28 +0100 Message-ID: <20150710225226.GA5008@bricha3-MOBL3> References: <1436549064-5200-1-git-send-email-pablo.de.lara.guarch@intel.com> <1436565467-13328-1-git-send-email-pablo.de.lara.guarch@intel.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Cc: dev@dpdk.org To: Pablo de Lara Return-path: Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by dpdk.org (Postfix) with ESMTP id 752CAC39A for ; Sat, 11 Jul 2015 00:52:33 +0200 (CEST) Content-Disposition: inline In-Reply-To: <1436565467-13328-1-git-send-email-pablo.de.lara.guarch@intel.com> 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 Fri, Jul 10, 2015 at 10:57:40PM +0100, Pablo de Lara wrote: > 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. > Check documentation included to know more about this new implementation > (including how entries are distributed as table utilization increases). > Only final quibble I have it that I think the data parameter stored should be void * rather than uintptr_t, though both can be cast to each other easily enough. Otherwise the code compiles ok now, and the unit tests pass fine. Series Acked-by: Bruce Richardson