[dpdk-dev] [PATCH v3 00/11] Cuckoo hash

[Bruce Richardson]

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
>