From: Pablo de Lara <pablo.de.lara.guarch@intel.com>
To: dev@dpdk.org
Cc: bruce.richardson@intel.com, Byron Marohn <byron.marohn@intel.com>,
Saikrishna Edupuganti <saikrishna.edupuganti@intel.com>
Subject: [dpdk-dev] [PATCH v5 2/4] hash: reorganize bucket structure
Date: Wed, 5 Oct 2016 00:25:13 +0100 [thread overview]
Message-ID: <1475623515-47587-3-git-send-email-pablo.de.lara.guarch@intel.com> (raw)
In-Reply-To: <1475623515-47587-1-git-send-email-pablo.de.lara.guarch@intel.com>
From: Byron Marohn <byron.marohn@intel.com>
Move current signatures of all entries together in the bucket
and same with all alternative signatures, instead of having
current and alternative signatures together per entry in the bucket.
This will be benefitial in the next commits, where a vectorized
comparison will be performed, achieving better performance.
The alternative signatures have been moved away from
the current signatures, to make the key indices be consecutive
to the current signatures, as these two fields are used by lookup,
so they are in the same cache line.
Signed-off-by: Byron Marohn <byron.marohn@intel.com>
Signed-off-by: Saikrishna Edupuganti <saikrishna.edupuganti@intel.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
Acked-by: Sameh Gobriel <sameh.gobriel@intel.com>
---
lib/librte_hash/rte_cuckoo_hash.c | 43 ++++++++++++++++++-----------------
lib/librte_hash/rte_cuckoo_hash.h | 17 ++++----------
lib/librte_hash/rte_cuckoo_hash_x86.h | 20 ++++++++--------
3 files changed, 37 insertions(+), 43 deletions(-)
diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 4de4422..a7ee2b9 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -421,7 +421,7 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)
*/
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
/* Search for space in alternative locations */
- next_bucket_idx = bkt->signatures[i].alt & h->bucket_bitmask;
+ next_bucket_idx = bkt->sig_alt[i] & h->bucket_bitmask;
next_bkt[i] = &h->buckets[next_bucket_idx];
for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) {
if (next_bkt[i]->key_idx[j] == EMPTY_SLOT)
@@ -434,8 +434,8 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)
/* Alternative location has spare room (end of recursive function) */
if (i != RTE_HASH_BUCKET_ENTRIES) {
- next_bkt[i]->signatures[j].alt = bkt->signatures[i].current;
- next_bkt[i]->signatures[j].current = bkt->signatures[i].alt;
+ next_bkt[i]->sig_alt[j] = bkt->sig_current[i];
+ next_bkt[i]->sig_current[j] = bkt->sig_alt[i];
next_bkt[i]->key_idx[j] = bkt->key_idx[i];
return i;
}
@@ -461,8 +461,8 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)
*/
bkt->flag[i] = 0;
if (ret >= 0) {
- next_bkt[i]->signatures[ret].alt = bkt->signatures[i].current;
- next_bkt[i]->signatures[ret].current = bkt->signatures[i].alt;
+ next_bkt[i]->sig_alt[ret] = bkt->sig_current[i];
+ next_bkt[i]->sig_current[ret] = bkt->sig_alt[i];
next_bkt[i]->key_idx[ret] = bkt->key_idx[i];
return i;
} else
@@ -544,8 +544,8 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
/* Check if key is already inserted in primary location */
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
- if (prim_bkt->signatures[i].current == sig &&
- prim_bkt->signatures[i].alt == alt_hash) {
+ if (prim_bkt->sig_current[i] == sig &&
+ prim_bkt->sig_alt[i] == alt_hash) {
k = (struct rte_hash_key *) ((char *)keys +
prim_bkt->key_idx[i] * h->key_entry_size);
if (rte_hash_cmp_eq(key, k->key, h) == 0) {
@@ -564,8 +564,8 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
/* Check if key is already inserted in secondary location */
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
- if (sec_bkt->signatures[i].alt == sig &&
- sec_bkt->signatures[i].current == alt_hash) {
+ if (sec_bkt->sig_alt[i] == sig &&
+ sec_bkt->sig_current[i] == alt_hash) {
k = (struct rte_hash_key *) ((char *)keys +
sec_bkt->key_idx[i] * h->key_entry_size);
if (rte_hash_cmp_eq(key, k->key, h) == 0) {
@@ -611,8 +611,8 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
/* Check if slot is available */
if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) {
- prim_bkt->signatures[i].current = sig;
- prim_bkt->signatures[i].alt = alt_hash;
+ prim_bkt->sig_current[i] = sig;
+ prim_bkt->sig_alt[i] = alt_hash;
prim_bkt->key_idx[i] = new_idx;
break;
}
@@ -632,8 +632,8 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
*/
ret = make_space_bucket(h, prim_bkt);
if (ret >= 0) {
- prim_bkt->signatures[ret].current = sig;
- prim_bkt->signatures[ret].alt = alt_hash;
+ prim_bkt->sig_current[ret] = sig;
+ prim_bkt->sig_alt[ret] = alt_hash;
prim_bkt->key_idx[ret] = new_idx;
if (h->add_key == ADD_KEY_MULTIWRITER)
rte_spinlock_unlock(h->multiwriter_lock);
@@ -707,7 +707,7 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
/* Check if key is in primary location */
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
- if (bkt->signatures[i].current == sig &&
+ if (bkt->sig_current[i] == sig &&
bkt->key_idx[i] != EMPTY_SLOT) {
k = (struct rte_hash_key *) ((char *)keys +
bkt->key_idx[i] * h->key_entry_size);
@@ -730,8 +730,8 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
/* Check if key is in secondary location */
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
- if (bkt->signatures[i].current == alt_hash &&
- bkt->signatures[i].alt == sig) {
+ if (bkt->sig_current[i] == alt_hash &&
+ bkt->sig_alt[i] == sig) {
k = (struct rte_hash_key *) ((char *)keys +
bkt->key_idx[i] * h->key_entry_size);
if (rte_hash_cmp_eq(key, k->key, h) == 0) {
@@ -785,7 +785,8 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)
unsigned lcore_id, n_slots;
struct lcore_cache *cached_free_slots;
- bkt->signatures[i].sig = NULL_SIGNATURE;
+ bkt->sig_current[i] = NULL_SIGNATURE;
+ bkt->sig_alt[i] = NULL_SIGNATURE;
if (h->hw_trans_mem_support) {
lcore_id = rte_lcore_id();
cached_free_slots = &h->local_free_slots[lcore_id];
@@ -823,7 +824,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
/* Check if key is in primary location */
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
- if (bkt->signatures[i].current == sig &&
+ if (bkt->sig_current[i] == sig &&
bkt->key_idx[i] != EMPTY_SLOT) {
k = (struct rte_hash_key *) ((char *)keys +
bkt->key_idx[i] * h->key_entry_size);
@@ -848,7 +849,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
/* Check if key is in secondary location */
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
- if (bkt->signatures[i].current == alt_hash &&
+ if (bkt->sig_current[i] == alt_hash &&
bkt->key_idx[i] != EMPTY_SLOT) {
k = (struct rte_hash_key *) ((char *)keys +
bkt->key_idx[i] * h->key_entry_size);
@@ -957,8 +958,8 @@ lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash,
prim_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES;
sec_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES;
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
- prim_hash_matches |= ((prim_hash == prim_bkt->signatures[i].current) << i);
- sec_hash_matches |= ((sec_hash == sec_bkt->signatures[i].current) << i);
+ prim_hash_matches |= ((prim_hash == prim_bkt->sig_current[i]) << i);
+ sec_hash_matches |= ((sec_hash == sec_bkt->sig_current[i]) << i);
}
key_idx = prim_bkt->key_idx[__builtin_ctzl(prim_hash_matches)];
diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h
index 27a47e5..6549731 100644
--- a/lib/librte_hash/rte_cuckoo_hash.h
+++ b/lib/librte_hash/rte_cuckoo_hash.h
@@ -151,17 +151,6 @@ struct lcore_cache {
void *objs[LCORE_CACHE_SIZE]; /**< Cache objects */
} __rte_cache_aligned;
-/* Structure storing both primary and secondary hashes */
-struct rte_hash_signatures {
- union {
- struct {
- hash_sig_t current;
- hash_sig_t alt;
- };
- uint64_t sig;
- };
-};
-
/* Structure that stores key-value pair */
struct rte_hash_key {
union {
@@ -174,9 +163,13 @@ struct rte_hash_key {
/** Bucket structure */
struct rte_hash_bucket {
- struct rte_hash_signatures signatures[RTE_HASH_BUCKET_ENTRIES];
+ hash_sig_t sig_current[RTE_HASH_BUCKET_ENTRIES];
+
/* Includes dummy key index that always contains index 0 */
uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES + 1];
+
+ hash_sig_t sig_alt[RTE_HASH_BUCKET_ENTRIES];
+
uint8_t flag[RTE_HASH_BUCKET_ENTRIES];
} __rte_cache_aligned;
diff --git a/lib/librte_hash/rte_cuckoo_hash_x86.h b/lib/librte_hash/rte_cuckoo_hash_x86.h
index 7ffa56f..47aec6d 100644
--- a/lib/librte_hash/rte_cuckoo_hash_x86.h
+++ b/lib/librte_hash/rte_cuckoo_hash_x86.h
@@ -54,8 +54,8 @@ rte_hash_cuckoo_insert_mw_tm(struct rte_hash_bucket *prim_bkt,
for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
/* Check if slot is available */
if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) {
- prim_bkt->signatures[i].current = sig;
- prim_bkt->signatures[i].alt = alt_hash;
+ prim_bkt->sig_current[i] = sig;
+ prim_bkt->sig_alt[i] = alt_hash;
prim_bkt->key_idx[i] = new_idx;
break;
}
@@ -101,7 +101,7 @@ rte_hash_cuckoo_move_insert_mw_tm(const struct rte_hash *h,
prev_slot = curr_node->prev_slot;
prev_alt_bkt_idx
- = prev_bkt->signatures[prev_slot].alt
+ = prev_bkt->sig_alt[prev_slot]
& h->bucket_bitmask;
if (unlikely(&h->buckets[prev_alt_bkt_idx]
@@ -113,10 +113,10 @@ rte_hash_cuckoo_move_insert_mw_tm(const struct rte_hash *h,
* Cuckoo insert to move elements back to its
* primary bucket if available
*/
- curr_bkt->signatures[curr_slot].alt =
- prev_bkt->signatures[prev_slot].current;
- curr_bkt->signatures[curr_slot].current =
- prev_bkt->signatures[prev_slot].alt;
+ curr_bkt->sig_alt[curr_slot] =
+ prev_bkt->sig_current[prev_slot];
+ curr_bkt->sig_current[curr_slot] =
+ prev_bkt->sig_alt[prev_slot];
curr_bkt->key_idx[curr_slot]
= prev_bkt->key_idx[prev_slot];
@@ -125,8 +125,8 @@ rte_hash_cuckoo_move_insert_mw_tm(const struct rte_hash *h,
curr_bkt = curr_node->bkt;
}
- curr_bkt->signatures[curr_slot].current = sig;
- curr_bkt->signatures[curr_slot].alt = alt_hash;
+ curr_bkt->sig_current[curr_slot] = sig;
+ curr_bkt->sig_alt[curr_slot] = alt_hash;
curr_bkt->key_idx[curr_slot] = new_idx;
rte_xend();
@@ -178,7 +178,7 @@ rte_hash_cuckoo_make_space_mw_tm(const struct rte_hash *h,
}
/* Enqueue new node and keep prev node info */
- alt_bkt = &(h->buckets[curr_bkt->signatures[i].alt
+ alt_bkt = &(h->buckets[curr_bkt->sig_alt[i]
& h->bucket_bitmask]);
head->bkt = alt_bkt;
head->prev = tail;
--
2.7.4
next prev parent reply other threads:[~2016-10-04 23:24 UTC|newest]
Thread overview: 37+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-08-26 21:34 [dpdk-dev] [PATCH 0/3] Cuckoo hash lookup enhancements Pablo de Lara
2016-08-26 21:34 ` [dpdk-dev] [PATCH 1/3] hash: reorganize bucket structure Pablo de Lara
2016-08-26 21:34 ` [dpdk-dev] [PATCH 2/3] hash: add vectorized comparison Pablo de Lara
2016-08-27 8:57 ` Thomas Monjalon
2016-09-02 17:05 ` De Lara Guarch, Pablo
2016-08-26 21:34 ` [dpdk-dev] [PATCH 3/3] hash: modify lookup bulk pipeline Pablo de Lara
2016-09-02 22:56 ` [dpdk-dev] [PATCH v2 0/4] Cuckoo hash lookup enhancements Pablo de Lara
2016-09-02 22:56 ` [dpdk-dev] [PATCH v2 1/4] hash: reorder hash structure Pablo de Lara
2016-09-02 22:56 ` [dpdk-dev] [PATCH v2 2/4] hash: reorganize bucket structure Pablo de Lara
2016-09-02 22:56 ` [dpdk-dev] [PATCH v2 3/4] hash: add vectorized comparison Pablo de Lara
2016-09-02 22:56 ` [dpdk-dev] [PATCH v2 4/4] hash: modify lookup bulk pipeline Pablo de Lara
2016-09-06 19:33 ` [dpdk-dev] [PATCH v3 0/4] Cuckoo hash lookup enhancements Pablo de Lara
2016-09-30 7:38 ` [dpdk-dev] [PATCH v4 0/4] Cuckoo hash enhancements Pablo de Lara
2016-09-30 7:38 ` [dpdk-dev] [PATCH v4 1/4] hash: reorder hash structure Pablo de Lara
2016-09-30 7:38 ` [dpdk-dev] [PATCH v4 2/4] hash: reorganize bucket structure Pablo de Lara
2016-09-30 7:38 ` [dpdk-dev] [PATCH v4 3/4] hash: add vectorized comparison Pablo de Lara
2016-09-30 7:38 ` [dpdk-dev] [PATCH v4 4/4] hash: modify lookup bulk pipeline Pablo de Lara
2016-09-30 19:53 ` [dpdk-dev] [PATCH v4 0/4] Cuckoo hash enhancements Gobriel, Sameh
2016-10-03 9:59 ` Bruce Richardson
2016-10-04 6:50 ` De Lara Guarch, Pablo
2016-10-04 7:17 ` De Lara Guarch, Pablo
2016-10-04 9:47 ` Bruce Richardson
2016-10-04 23:25 ` [dpdk-dev] [PATCH v5 " Pablo de Lara
2016-10-04 23:25 ` [dpdk-dev] [PATCH v5 1/4] hash: reorder hash structure Pablo de Lara
2016-10-04 23:25 ` Pablo de Lara [this message]
2016-10-04 23:25 ` [dpdk-dev] [PATCH v5 3/4] hash: add vectorized comparison Pablo de Lara
2016-10-04 23:25 ` [dpdk-dev] [PATCH v5 4/4] hash: modify lookup bulk pipeline Pablo de Lara
2016-10-05 10:12 ` [dpdk-dev] [PATCH v5 0/4] Cuckoo hash enhancements Thomas Monjalon
2016-09-06 19:34 ` [dpdk-dev] [PATCH v3 0/4] Cuckoo hash lookup enhancements Pablo de Lara
2016-09-06 19:34 ` [dpdk-dev] [PATCH v3 1/4] hash: reorder hash structure Pablo de Lara
2016-09-28 9:02 ` Bruce Richardson
2016-09-29 1:33 ` De Lara Guarch, Pablo
2016-09-06 19:34 ` [dpdk-dev] [PATCH v3 2/4] hash: reorganize bucket structure Pablo de Lara
2016-09-28 9:05 ` Bruce Richardson
2016-09-29 1:40 ` De Lara Guarch, Pablo
2016-09-06 19:34 ` [dpdk-dev] [PATCH v3 3/4] hash: add vectorized comparison Pablo de Lara
2016-09-06 19:34 ` [dpdk-dev] [PATCH v3 4/4] hash: modify lookup bulk pipeline Pablo de Lara
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1475623515-47587-3-git-send-email-pablo.de.lara.guarch@intel.com \
--to=pablo.de.lara.guarch@intel.com \
--cc=bruce.richardson@intel.com \
--cc=byron.marohn@intel.com \
--cc=dev@dpdk.org \
--cc=saikrishna.edupuganti@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).