[dpdk-dev] [PATCH v3 00/11] Cuckoo hash
thomas.monjalon at 6wind.com
Thu Jul 9 01:23:54 CEST 2015
Bruce, what is the status of this series?
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.
> - 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
More information about the dev