All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH v1 0/5] hash: add extendable bucket and partial-key hashing
@ 2018-09-06 17:09 Yipeng Wang
  2018-09-06 17:09 ` [PATCH v1 1/5] test: fix bucket size in hash table perf test Yipeng Wang
                   ` (7 more replies)
  0 siblings, 8 replies; 107+ messages in thread
From: Yipeng Wang @ 2018-09-06 17:09 UTC (permalink / raw)
  To: pablo.de.lara.guarch, bruce.richardson
  Cc: dev, yipeng1.wang, michel, honnappa.nagarahalli

This patch set made two major improvements over the current rte_hash library.

First, it adds Extendable Bucket Table feature: a new structure that can
accommodate keys that failed to get inserted into the main hash table due to
the unlikely event of excessive hash collisions. The hash table buckets will
get extended using a linked list to host these keys. This new design will
guarantee insertion of 100% of the keys for a given hash table size with
minimal overhead. A new flag value is added for user to indicate if the
extendable bucket feature should be enabled or not. The linked list buckets is
similar concept to the extendable bucket hash table in packet framework.
In details, for insertion, the linked buckets will be used to store the keys
that fail to get in the primary and the secondary bucket and the cuckoo path
could not find an empty location for the maximum path length (small
probability). For lookup, the key is checked first in the primary, then the
secondary, then if the secondary is extended the linked list is traversed
for a possible match.

Second, the patch set changes the current hashing algorithm to be "partial-key
hashing". Partial-key hashing is the concept from Bin Fan, et al.'s paper
"MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter
Hashing". Instead of storing both 32-bit signature and alternative signature
in the bucket, we only store a small 16-bit signature and calculate the
alternative bucket index by XORing the signature with the current bucket index.
This doubles the hash table memory efficiency since now one bucket
only occupies one cache line instead of two in the original design.

Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>

Yipeng Wang (5):
  test: fix bucket size in hash table perf test
  test: more accurate hash table perf test output
  hash: add extendable bucket feature
  test: implement extendable bucket hash test
  hash: use partial-key hashing

 lib/librte_hash/rte_cuckoo_hash.c | 518 +++++++++++++++++++++++++++-----------
 lib/librte_hash/rte_cuckoo_hash.h |  11 +-
 lib/librte_hash/rte_hash.h        |   3 +
 test/test/test_hash.c             | 145 ++++++++++-
 test/test/test_hash_perf.c        | 126 +++++++---
 5 files changed, 618 insertions(+), 185 deletions(-)

-- 
2.7.4

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

end of thread, other threads:[~2018-10-25 23:07 UTC | newest]

Thread overview: 107+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-09-06 17:09 [PATCH v1 0/5] hash: add extendable bucket and partial-key hashing Yipeng Wang
2018-09-06 17:09 ` [PATCH v1 1/5] test: fix bucket size in hash table perf test Yipeng Wang
2018-09-06 17:09 ` [PATCH v1 2/5] test: more accurate hash table perf test output Yipeng Wang
2018-09-06 17:09 ` [PATCH v1 3/5] hash: add extendable bucket feature Yipeng Wang
2018-09-06 17:09 ` [PATCH v1 4/5] test: implement extendable bucket hash test Yipeng Wang
2018-09-06 17:09 ` [PATCH v1 5/5] hash: use partial-key hashing Yipeng Wang
2018-09-21 17:17 ` [PATCH v2 0/7] hash: add extendable bucket and partial key hashing Yipeng Wang
2018-09-21 17:17   ` [PATCH v2 1/7] test/hash: fix bucket size in hash perf test Yipeng Wang
2018-09-26 10:04     ` Bruce Richardson
2018-09-27  3:39       ` Wang, Yipeng1
2018-09-27  4:23     ` Honnappa Nagarahalli
2018-09-29  0:31       ` Wang, Yipeng1
2018-09-21 17:17   ` [PATCH v2 2/7] test/hash: more accurate hash perf test output Yipeng Wang
2018-09-26 10:07     ` Bruce Richardson
2018-09-21 17:17   ` [PATCH v2 3/7] test/hash: fix rw test with non-consecutive cores Yipeng Wang
2018-09-26 11:02     ` Bruce Richardson
2018-09-27  3:40       ` Wang, Yipeng1
2018-09-26 11:13     ` Bruce Richardson
2018-09-21 17:17   ` [PATCH v2 4/7] hash: fix unnecessary code Yipeng Wang
2018-09-26 12:55     ` Bruce Richardson
2018-09-21 17:17   ` [PATCH v2 5/7] hash: add extendable bucket feature Yipeng Wang
2018-09-27  4:23     ` Honnappa Nagarahalli
2018-09-27 11:15       ` Bruce Richardson
2018-09-27 11:27         ` Ananyev, Konstantin
2018-09-27 12:27           ` Bruce Richardson
2018-09-27 12:33             ` Ananyev, Konstantin
2018-09-27 19:21         ` Honnappa Nagarahalli
2018-09-28 17:35           ` Wang, Yipeng1
2018-09-29 21:09             ` Honnappa Nagarahalli
2018-09-29  1:10       ` Wang, Yipeng1
2018-10-01 20:56         ` Honnappa Nagarahalli
2018-10-02  1:56           ` Wang, Yipeng1
2018-09-21 17:17   ` [PATCH v2 6/7] test/hash: implement extendable bucket hash test Yipeng Wang
2018-09-27  4:24     ` Honnappa Nagarahalli
2018-09-29  0:50       ` Wang, Yipeng1
2018-09-21 17:17   ` [PATCH v2 7/7] hash: use partial-key hashing Yipeng Wang
2018-09-27  4:24     ` Honnappa Nagarahalli
2018-09-29  0:55       ` Wang, Yipeng1
2018-09-26 12:57   ` [PATCH v2 0/7] hash: add extendable bucket and partial key hashing Bruce Richardson
2018-09-27  3:41     ` Wang, Yipeng1
2018-09-27  4:23   ` Honnappa Nagarahalli
2018-09-29  0:46     ` Wang, Yipeng1
2018-09-26 12:54 ` [PATCH v3 0/5] hash: fix multiple issues Yipeng Wang
2018-09-26 12:54   ` [PATCH v3 1/5] test/hash: fix bucket size in hash perf test Yipeng Wang
2018-09-27 11:17     ` Bruce Richardson
2018-09-26 12:54   ` [PATCH v3 2/5] test/hash: more accurate hash perf test output Yipeng Wang
2018-09-26 12:54   ` [PATCH v3 3/5] test/hash: fix rw test with non-consecutive cores Yipeng Wang
2018-09-27 11:18     ` Bruce Richardson
2018-09-26 12:54   ` [PATCH v3 4/5] test/hash: fix missing file in meson build file Yipeng Wang
2018-09-27 11:22     ` Bruce Richardson
2018-09-26 12:54   ` [PATCH v3 5/5] hash: fix unused define Yipeng Wang
2018-09-28 14:11   ` [PATCH v4 0/5] hash: fix multiple issues Yipeng Wang
2018-09-28 14:11     ` [PATCH v4 1/5] test/hash: fix bucket size in hash perf test Yipeng Wang
2018-10-01 20:28       ` Honnappa Nagarahalli
2018-09-28 14:11     ` [PATCH v4 2/5] test/hash: more accurate hash perf test output Yipeng Wang
2018-09-28 14:11     ` [PATCH v4 3/5] test/hash: fix rw test with non-consecutive cores Yipeng Wang
2018-09-28 14:11     ` [PATCH v4 4/5] test/hash: fix missing file in meson build file Yipeng Wang
2018-09-28 14:11     ` [PATCH v4 5/5] hash: fix unused define Yipeng Wang
2018-10-25 22:04     ` [PATCH v4 0/5] hash: fix multiple issues Thomas Monjalon
2018-09-26 20:26 ` [PATCH v3 0/3] hash: add extendable bucket and partial key hashing Yipeng Wang
2018-09-26 20:26   ` [PATCH v3 1/3] hash: add extendable bucket feature Yipeng Wang
2018-09-26 20:26   ` [PATCH v3 2/3] test/hash: implement extendable bucket hash test Yipeng Wang
2018-09-26 20:26   ` [PATCH v3 3/3] hash: use partial-key hashing Yipeng Wang
2018-09-28 17:23   ` [PATCH v4 0/4] hash: add extendable bucket and partial key hashing Yipeng Wang
2018-09-28 17:23     ` [PATCH v4 1/4] hash: fix race condition in iterate Yipeng Wang
2018-10-01 20:23       ` Honnappa Nagarahalli
2018-10-02  0:17         ` Wang, Yipeng1
2018-10-02  4:26           ` Honnappa Nagarahalli
2018-10-02 23:53             ` Wang, Yipeng1
2018-09-28 17:23     ` [PATCH v4 2/4] hash: add extendable bucket feature Yipeng Wang
2018-10-02  3:58       ` Honnappa Nagarahalli
2018-10-02 23:39         ` Wang, Yipeng1
2018-10-03  4:37           ` Honnappa Nagarahalli
2018-10-03 15:08           ` Stephen Hemminger
2018-10-03 15:08       ` Stephen Hemminger
2018-10-03 16:53         ` Wang, Yipeng1
2018-10-03 17:59           ` Honnappa Nagarahalli
2018-10-04  1:22             ` Wang, Yipeng1
2018-09-28 17:23     ` [PATCH v4 3/4] test/hash: implement extendable bucket hash test Yipeng Wang
2018-10-01 19:53       ` Honnappa Nagarahalli
2018-09-28 17:23     ` [PATCH v4 4/4] hash: use partial-key hashing Yipeng Wang
2018-10-01 20:09       ` Honnappa Nagarahalli
2018-10-03 19:05     ` [PATCH v4 0/4] hash: add extendable bucket and partial key hashing Dharmik Thakkar
2018-10-01 18:34   ` [PATCH v5 " Yipeng Wang
2018-10-01 18:34     ` [PATCH v5 1/4] hash: fix race condition in iterate Yipeng Wang
2018-10-02 17:26       ` Honnappa Nagarahalli
2018-10-01 18:35     ` [PATCH v5 2/4] hash: add extendable bucket feature Yipeng Wang
2018-10-01 18:35     ` [PATCH v5 3/4] test/hash: implement extendable bucket hash test Yipeng Wang
2018-10-01 18:35     ` [PATCH v5 4/4] hash: use partial-key hashing Yipeng Wang
2018-10-02 20:52       ` Dharmik Thakkar
2018-10-03  0:43         ` Wang, Yipeng1
2018-10-03 19:10     ` [PATCH v5 0/4] hash: add extendable bucket and partial key hashing Dharmik Thakkar
2018-10-04  0:36       ` Wang, Yipeng1
2018-10-04 16:35   ` [PATCH v6 " Yipeng Wang
2018-10-04 16:35     ` [PATCH v6 1/4] hash: fix race condition in iterate Yipeng Wang
2018-10-04 16:35     ` [PATCH v6 2/4] hash: add extendable bucket feature Yipeng Wang
2018-10-04 16:35     ` [PATCH v6 3/4] test/hash: implement extendable bucket hash test Yipeng Wang
2018-10-04 16:35     ` [PATCH v6 4/4] hash: use partial-key hashing Yipeng Wang
2018-10-10 21:27     ` [PATCH v7 0/4] hash: add extendable bucket and partial key hashing Yipeng Wang
2018-10-10 21:27       ` [PATCH v7 1/4] hash: fix race condition in iterate Yipeng Wang
2018-10-10 21:27       ` [PATCH v7 2/4] hash: add extendable bucket feature Yipeng Wang
2018-10-10 21:27       ` [PATCH v7 3/4] test/hash: implement extendable bucket hash test Yipeng Wang
2018-10-10 21:27       ` [PATCH v7 4/4] hash: use partial-key hashing Yipeng Wang
2018-10-16 18:47       ` [PATCH] doc: update release note for hash library Yipeng Wang
2018-10-17 20:09         ` Honnappa Nagarahalli
2018-10-25 18:45           ` Wang, Yipeng1
2018-10-25 23:07             ` Thomas Monjalon

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.