From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by dpdk.org (Postfix) with ESMTP id 831FAC42A for ; Fri, 10 Jul 2015 22:52:54 +0200 (CEST) Received: from orsmga002.jf.intel.com ([10.7.209.21]) by fmsmga102.fm.intel.com with ESMTP; 10 Jul 2015 13:52:53 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.15,449,1432623600"; d="scan'208";a="762172911" Received: from dmsimmon-mobl.amr.corp.intel.com ([10.252.138.82]) by orsmga002.jf.intel.com with SMTP; 10 Jul 2015 13:52:51 -0700 Received: by (sSMTP sendmail emulation); Fri, 10 Jul 2015 21:52:50 +0025 Date: Fri, 10 Jul 2015 21:52:49 +0100 From: Bruce Richardson To: Pablo de Lara Message-ID: <20150710205248.GC11920@bricha3-MOBL3> References: <1435530330-10132-1-git-send-email-pablo.de.lara.guarch@intel.com> <1436549064-5200-1-git-send-email-pablo.de.lara.guarch@intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1436549064-5200-1-git-send-email-pablo.de.lara.guarch@intel.com> Organization: Intel Shannon Ltd. User-Agent: Mutt/1.5.23 (2014-03-12) Cc: dev@dpdk.org Subject: Re: [dpdk-dev] [PATCH v4 0/7] Cuckoo hash - part 3 of Cuckoo hash 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, 10 Jul 2015 20:52:54 -0000 On Fri, Jul 10, 2015 at 06:24:17PM +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). > > Changes in v4: > - Unit tests enhancements are not part of this patchset anymore. > - rte_hash structure has been made internal in another patch, > so it is not part of this patchset anymore. > - Add function to iterate through the hash table, as rte_hash > structure has been made private. > - Added extra_flag parameter in rte_hash_parameter to be able > to add new parameters in the future without breaking the ABI > - Remove proposed lookup_bulk_with_hash function, as it is > not of much use with the existing hash functions > (there are no vector hash functions). > - User can store 8-byte integer or pointer as data, instead > of variable size data, as discussed in the mailing list. > Hi Pablo, I'm getting some compile errors with this code, perhaps you could recheck e.g 32-bit and with clang. On the plus side, I like the docs included with this set. Regards, /Bruce