DPDK patches and discussions
 help / color / mirror / Atom feed
* [dpdk-dev] [PATCH 0/6] Cuckoo hash
@ 2015-06-05 14:33 Pablo de Lara
  2015-06-05 14:33 ` [dpdk-dev] [PATCH 1/6] eal: add const in prefetch functions Pablo de Lara
                   ` (7 more replies)
  0 siblings, 8 replies; 92+ messages in thread
From: Pablo de Lara @ 2015-06-05 14:33 UTC (permalink / raw)
  To: dev

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

^ permalink raw reply	[flat|nested] 92+ messages in thread

end of thread, other threads:[~2015-07-17 14:39 UTC | newest]

Thread overview: 92+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-06-05 14:33 [dpdk-dev] [PATCH 0/6] Cuckoo hash Pablo de Lara
2015-06-05 14:33 ` [dpdk-dev] [PATCH 1/6] eal: add const in prefetch functions Pablo de Lara
2015-06-16 15:10   ` Bruce Richardson
2015-06-05 14:33 ` [dpdk-dev] [PATCH 2/6] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-17 15:31   ` Bruce Richardson
2015-06-18  9:50   ` Bruce Richardson
2015-06-05 14:33 ` [dpdk-dev] [PATCH 3/6] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-05 14:33 ` [dpdk-dev] [PATCH 4/6] hash: add new functions rte_hash_rehash and rte_hash_reset Pablo de Lara
2015-06-05 14:33 ` [dpdk-dev] [PATCH 5/6] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-05 14:33 ` [dpdk-dev] [PATCH 6/6] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-16 13:44 ` [dpdk-dev] [PATCH 0/6] Cuckoo hash Thomas Monjalon
2015-06-16 21:44   ` De Lara Guarch, Pablo
2015-06-25 22:05 ` [dpdk-dev] [PATCH v2 00/11] " Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 01/11] eal: add const in prefetch functions Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 02/11] hash: move rte_hash structure to C file and make it internal Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 03/11] test/hash: enhance hash unit tests Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 04/11] test/hash: rename new hash perf unit test back to original name Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 05/11] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 06/11] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 07/11] hash: add new function rte_hash_reset Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 08/11] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-26 16:49     ` Stephen Hemminger
2015-06-28 22:23       ` De Lara Guarch, Pablo
2015-06-30  7:36         ` Stephen Hemminger
2015-07-10 10:39         ` Bruce Richardson
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 09/11] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 10/11] doc: announce ABI change of librte_hash Pablo de Lara
2015-06-25 22:05   ` [dpdk-dev] [PATCH v2 11/11] doc: update hash documentation Pablo de Lara
2015-06-28 22:25   ` [dpdk-dev] [PATCH v3 00/11] Cuckoo hash Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 01/11] eal: add const in prefetch functions Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 02/11] hash: move rte_hash structure to C file and make it internal Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 03/11] test/hash: enhance hash unit tests Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 04/11] test/hash: rename new hash perf unit test back to original name Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 05/11] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 06/11] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 07/11] hash: add new function rte_hash_reset Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 08/11] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 09/11] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 10/11] doc: announce ABI change of librte_hash Pablo de Lara
2015-06-28 22:25     ` [dpdk-dev] [PATCH v3 11/11] doc: update hash documentation Pablo de Lara
2015-07-08 23:23     ` [dpdk-dev] [PATCH v3 00/11] Cuckoo hash Thomas Monjalon
2015-07-09  8:02       ` Bruce Richardson
2015-07-10 17:24     ` [dpdk-dev] [PATCH v4 0/7] Cuckoo hash - part 3 of " Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 4/7] hash: add iterate function Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 17:24       ` [dpdk-dev] [PATCH v4 7/7] doc: update hash documentation Pablo de Lara
2015-07-10 20:52       ` [dpdk-dev] [PATCH v4 0/7] Cuckoo hash - part 3 of Cuckoo hash Bruce Richardson
2015-07-10 21:57       ` [dpdk-dev] [PATCH v5 " Pablo de Lara
2015-07-10 21:57         ` [dpdk-dev] [PATCH v5 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 21:57         ` [dpdk-dev] [PATCH v5 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 21:57         ` [dpdk-dev] [PATCH v5 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 21:57         ` [dpdk-dev] [PATCH v5 4/7] hash: add iterate function Pablo de Lara
2015-07-10 21:57         ` [dpdk-dev] [PATCH v5 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 21:57         ` [dpdk-dev] [PATCH v5 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 21:57         ` [dpdk-dev] [PATCH v5 7/7] doc: update hash documentation Pablo de Lara
2015-07-10 22:52         ` [dpdk-dev] [PATCH v5 0/7] Cuckoo hash - part 3 of Cuckoo hash Bruce Richardson
2015-07-10 23:30         ` [dpdk-dev] [PATCH v6 " Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 4/7] hash: add iterate function Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 23:30           ` [dpdk-dev] [PATCH v6 7/7] doc: update hash documentation Pablo de Lara
2015-07-11  0:18           ` [dpdk-dev] [PATCH v7 0/7] Cuckoo hash - part 3 of Cuckoo hash Pablo de Lara
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-12 22:29               ` Thomas Monjalon
2015-07-13 16:11                 ` Bruce Richardson
2015-07-13 16:14                   ` Bruce Richardson
2015-07-13 16:20                     ` Thomas Monjalon
2015-07-13 16:26                       ` Bruce Richardson
2015-07-16  9:39               ` Tony Lu
2015-07-16 20:42                 ` De Lara Guarch, Pablo
2015-07-17  3:34                   ` Tony Lu
2015-07-17  7:34                     ` De Lara Guarch, Pablo
2015-07-17  7:58                       ` Tony Lu
2015-07-17  9:06                         ` De Lara Guarch, Pablo
2015-07-17 14:39                           ` Tony Lu
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-12 22:16               ` Thomas Monjalon
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-12 22:00               ` Thomas Monjalon
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 4/7] hash: add iterate function Pablo de Lara
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-12 22:38               ` Thomas Monjalon
2015-07-11  0:18             ` [dpdk-dev] [PATCH v7 7/7] doc: update hash documentation Pablo de Lara
2015-07-12 22:46             ` [dpdk-dev] [PATCH v7 0/7] Cuckoo hash - part 3 of Cuckoo hash Thomas Monjalon

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).