| Message ID | 20190625211520.43181-2-honnappa.nagarahalli@arm.com |
|---|---|
| State | Superseded |
| Headers | show |
| Series | lib/hash: perf improvements for lock-free | expand |
>-----Original Message----- >From: Honnappa Nagarahalli [mailto:honnappa.nagarahalli@arm.com] >Sent: Tuesday, June 25, 2019 2:15 PM >To: Wang, Yipeng1 <yipeng1.wang@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>; Richardson, Bruce ><bruce.richardson@intel.com>; De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>; honnappa.nagarahalli@arm.com >Cc: gavin.hu@arm.com; ruifeng.wang@arm.com; dev@dpdk.org; nd@arm.com; stable@dpdk.org >Subject: [PATCH 1/3] lib/hash: use ordered loads only if signature matches > >Relaxed signature comparison is done first. Further ordered loads >are done only if the signature matches. Any false positives are >caught by the full key comparison. [Wang, Yipeng] add: This commit improves lookup performance. > >Fixes: e605a1d36 ("hash: add lock-free r/w concurrency") >Cc: stable@dpdk.org > >Signed-off-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com> >Reviewed-by: Gavin Hu <gavin.hu@arm.com> >Tested-by: Ruifeng Wang <ruifeng.wang@arm.com> >--- > lib/librte_hash/rte_cuckoo_hash.c | 35 ++++++++++++++++++------------- > 1 file changed, 21 insertions(+), 14 deletions(-) > >diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c >index 953928f27..f37f6957d 100644 >--- a/lib/librte_hash/rte_cuckoo_hash.c >+++ b/lib/librte_hash/rte_cuckoo_hash.c >@@ -1188,22 +1188,29 @@ search_one_bucket_lf(const struct rte_hash *h, const void *key, uint16_t sig, > struct rte_hash_key *k, *keys = h->key_store; > > for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { >- key_idx = __atomic_load_n(&bkt->key_idx[i], >+ /* Signature comparison is done before the acquire-load >+ * of the key index to achieve better performance. >+ * Any false positives will be caught in full comparison >+ * of the key. >+ */ [Wang, Yipeng] A bit more explanation would be helpful for future understanding of the code: "Signature comparison is done ... performance. Although this could accidentally cause the reader to read an old signature while the key_idx is updated to a new key's, any false positive will be .... of the key." Otherwise: Acked-by: Yipeng Wang <yipeng1.wang@intel.com>
diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 953928f27..f37f6957d 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -1188,22 +1188,29 @@ search_one_bucket_lf(const struct rte_hash *h, const void *key, uint16_t sig, struct rte_hash_key *k, *keys = h->key_store; for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { - key_idx = __atomic_load_n(&bkt->key_idx[i], + /* Signature comparison is done before the acquire-load + * of the key index to achieve better performance. + * Any false positives will be caught in full comparison + * of the key. + */ + if (bkt->sig_current[i] == sig) { + key_idx = __atomic_load_n(&bkt->key_idx[i], __ATOMIC_ACQUIRE); - if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) { - k = (struct rte_hash_key *) ((char *)keys + - key_idx * h->key_entry_size); - pdata = __atomic_load_n(&k->pdata, - __ATOMIC_ACQUIRE); + if (key_idx != EMPTY_SLOT) { + k = (struct rte_hash_key *) ((char *)keys + + key_idx * h->key_entry_size); + pdata = __atomic_load_n(&k->pdata, + __ATOMIC_ACQUIRE); - if (rte_hash_cmp_eq(key, k->key, h) == 0) { - if (data != NULL) - *data = pdata; - /* - * Return index where key is stored, - * subtracting the first dummy index - */ - return key_idx - 1; + if (rte_hash_cmp_eq(key, k->key, h) == 0) { + if (data != NULL) + *data = pdata; + /* + * Return index where key is stored, + * subtracting the first dummy index + */ + return key_idx - 1; + } } } }
Relaxed signature comparison is done first. Further ordered loads are done only if the signature matches. Any false positives are caught by the full key comparison. Fixes: e605a1d36 ("hash: add lock-free r/w concurrency") Cc: stable@dpdk.org Signed-off-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com> Reviewed-by: Gavin Hu <gavin.hu@arm.com> Tested-by: Ruifeng Wang <ruifeng.wang@arm.com> --- lib/librte_hash/rte_cuckoo_hash.c | 35 ++++++++++++++++++------------- 1 file changed, 21 insertions(+), 14 deletions(-) -- 2.17.1