From 88bcba80d5328fa2b3191fab4ffdd396d69937f1 Mon Sep 17 00:00:00 2001 From: Damjan Marion Date: Wed, 15 Apr 2020 19:44:17 +0200 Subject: [PATCH] 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 --- src/vppinfra/cuckoo_template.h | 53 ++++++++++++++++++++---------------------- 1 file 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; } -- 2.16.6