aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDamjan Marion <damarion@cisco.com>2020-04-15 19:44:17 +0200
committerFlorin Coras <florin.coras@gmail.com>2020-04-15 19:34:03 +0000
commit88bcba80d5328fa2b3191fab4ffdd396d69937f1 (patch)
tree886acc15fe0cbf5f585efbce324539d1c23b6f8b
parent7edc86d005d7051341d380fba2b1fe4bc7dd016e (diff)
vppinfra: delay bucket2 calc in cuckoo search
There is no need to calculate bucket2 if there is hit on bucket1 Type: improvement Change-Id: Id01c37963497668c0160068501294568a181d011 Signed-off-by: Damjan Marion <damarion@cisco.com>
-rw-r--r--src/vppinfra/cuckoo_template.h53
1 files changed, 25 insertions, 28 deletions
diff --git a/src/vppinfra/cuckoo_template.h b/src/vppinfra/cuckoo_template.h
index f785e7ec642..d48079a9e6c 100644
--- a/src/vppinfra/cuckoo_template.h
+++ b/src/vppinfra/cuckoo_template.h
@@ -412,38 +412,35 @@ always_inline int
CV (clib_cuckoo_search_inline_with_hash) (CVT (clib_cuckoo) * h, u64 hash,
CVT (clib_cuckoo_kv) * kvp)
{
- clib_cuckoo_lookup_info_t lookup;
+ CVT (clib_cuckoo_bucket) * buckets = h->buckets;
+ uword bucket1, bucket2;
+ u8 reduced_hash;
+ u64 nbuckets = vec_len (buckets);
+ u64 mask = nbuckets - 1;
int rv;
- CVT (clib_cuckoo_bucket) * buckets;
+ bucket1 = hash & mask;
+ reduced_hash = clib_cuckoo_reduce_hash (hash);
+
again:
- buckets = h->buckets;
- lookup = CV (clib_cuckoo_calc_lookup) (buckets, hash);
- do
- {
- rv =
- CV (clib_cuckoo_bucket_search) (vec_elt_at_index
- (buckets, lookup.bucket1), kvp,
- lookup.reduced_hash);
- }
- while (PREDICT_FALSE (CLIB_CUCKOO_ERROR_AGAIN == rv));
- if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
- {
- return CLIB_CUCKOO_ERROR_SUCCESS;
- }
+ rv = CV (clib_cuckoo_bucket_search) (vec_elt_at_index (buckets, bucket1),
+ kvp, reduced_hash);
+
+ if (rv == CLIB_CUCKOO_ERROR_SUCCESS)
+ return CLIB_CUCKOO_ERROR_SUCCESS;
+
+ if (PREDICT_FALSE (rv == CLIB_CUCKOO_ERROR_AGAIN))
+ goto again;
+
+ bucket2 = clib_cuckoo_get_other_bucket (nbuckets, bucket1, reduced_hash);
+ rv = CV (clib_cuckoo_bucket_search) (vec_elt_at_index (buckets, bucket2),
+ kvp, reduced_hash);
+
+ /* change to 2nd bucket could bump the item to 1st bucket and the bucket
+ * indexes might not even be valid anymore - restart the search */
+ if (PREDICT_FALSE (rv == CLIB_CUCKOO_ERROR_AGAIN))
+ goto again;
- rv =
- CV (clib_cuckoo_bucket_search) (vec_elt_at_index
- (buckets, lookup.bucket2), kvp,
- lookup.reduced_hash);
- if (PREDICT_FALSE (CLIB_CUCKOO_ERROR_AGAIN == rv))
- {
- /*
- * change to 2nd bucket could bump the item to 1st bucket and the bucket
- * indexes might not even be valid anymore - restart the search
- */
- goto again;
- }
return rv;
}