[dpdk-dev] [PATCH 0/6] Cuckoo hash

Pablo de Lara pablo.de.lara.guarch at intel.com
Fri Jun 5 16:33:18 CEST 2015


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 before having
to rehash the table, so it is unlikely that a rehash is necessary,
as long as there is enough free space and user uses reasonable good hash functions.

Things left for v2:
- Improve unit tests to show clearer performance numbers
- Documentation changes

Pablo de Lara (6):
  eal: add const in prefetch functions
  hash: replace existing hash library with cuckoo hash implementation
  hash: add new lookup_bulk_with_hash function
  hash: add new functions rte_hash_rehash and rte_hash_reset
  hash: add new functionality to store data in hash table
  MAINTAINERS: claim responsability for hash library

 MAINTAINERS                                        |    1 +
 app/test/Makefile                                  |    3 +
 app/test/test_hash.c                               |  105 +-
 .../common/include/arch/ppc_64/rte_prefetch.h      |    6 +-
 .../common/include/arch/x86/rte_prefetch.h         |   12 +-
 .../common/include/generic/rte_prefetch.h          |    6 +-
 lib/librte_hash/rte_hash.c                         | 1226 +++++++++++++++++---
 lib/librte_hash/rte_hash.h                         |  373 +++++-
 lib/librte_hash/rte_hash_version.map               |   18 +
 9 files changed, 1422 insertions(+), 328 deletions(-)

-- 
2.4.2



More information about the dev mailing list