From 68e5fd5206e75cb367375b4fea2e531a3712fd06 Mon Sep 17 00:00:00 2001 From: Damjan Marion Date: Thu, 23 Apr 2020 13:41:47 +0200 Subject: [PATCH] vppinfra: more bihash optimizatons * Avoid doing expensive bit extraction for most likely case where bucket .log2_page_size == 0 and .linear_search == 0, saves 3-5 cycles for lookup, data_prefetch and add operation * use bextr instruction when available (x86 BMI instruction set) Type: improvement Change-Id: I163df36a29287482c5f133be8b21d62a2f7440de Signed-off-by: Damjan Marion --- src/vppinfra/bihash_template.c | 74 ++++++++++++------------------------------ src/vppinfra/bihash_template.h | 46 +++++++++++++++++++------- src/vppinfra/clib.h | 13 ++++++++ 3 files changed, 67 insertions(+), 66 deletions(-) diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 7269959f4a6..f7d88073418 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -463,8 +463,7 @@ BV (split_and_rehash) /* rehash the item onto its new home-page */ new_hash = BV (clib_bihash_hash) (&(old_values->kvp[i])); - new_hash >>= h->log2_nbuckets; - new_hash &= (1 << new_log2_pages) - 1; + new_hash = extract_bits (new_hash, h->log2_nbuckets, new_log2_pages); new_v = &new_values[new_hash]; /* Across the new home-page */ @@ -547,6 +546,14 @@ static_always_inline int BV (clib_bihash_add_del_inline_with_hash) int mark_bucket_linear; int resplit_once; + /* *INDENT-OFF* */ + static const BVT (clib_bihash_bucket) mask = { + .linear_search = 1, + .log2_pages = -1 + }; + /* *INDENT-ON* */ + +#if BIHASH_LAZY_INSTANTIATE /* * Create the table (is_add=1,2), or flunk the request now (is_add=0) * Use the alloc_lock to protect the instantiate operation. @@ -561,11 +568,10 @@ static_always_inline int BV (clib_bihash_add_del_inline_with_hash) BV (clib_bihash_instantiate) (h); BV (clib_bihash_alloc_unlock) (h); } +#endif b = BV (clib_bihash_get_bucket) (h, hash); - hash >>= h->log2_nbuckets; - BV (clib_bihash_lock_bucket) (b); /* First elt in the bucket? */ @@ -597,10 +603,13 @@ static_always_inline int BV (clib_bihash_add_del_inline_with_hash) limit = BIHASH_KVP_PER_PAGE; v = BV (clib_bihash_get_value) (h, b->offset); - if (b->linear_search) - limit <<= b->log2_pages; - else - v += hash & ((1 << b->log2_pages) - 1); + if (PREDICT_FALSE (b->as_u64 & mask.as_u64)) + { + if (PREDICT_FALSE (b->linear_search)) + limit <<= b->log2_pages; + else + v += extract_bits (hash, h->log2_nbuckets, b->log2_pages); + } if (is_add) { @@ -782,9 +791,8 @@ static_always_inline int BV (clib_bihash_add_del_inline_with_hash) limit = BIHASH_KVP_PER_PAGE; if (mark_bucket_linear) limit <<= new_log2_pages; - new_hash >>= h->log2_nbuckets; - new_hash &= (1 << new_log2_pages) - 1; - new_v += mark_bucket_linear ? 0 : new_hash; + else + new_v += extract_bits (new_hash, h->log2_nbuckets, new_log2_pages); for (i = 0; i < limit; i++) { @@ -864,49 +872,7 @@ int BV (clib_bihash_search) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep) { - u64 hash; - BVT (clib_bihash_value) * v; - BVT (clib_bihash_bucket) * b; - int i, limit; - - ASSERT (valuep); - -#if BIHASH_LAZY_INSTANTIATE - if (PREDICT_FALSE (alloc_arena (h) == 0)) - return -1; -#endif - - hash = BV (clib_bihash_hash) (search_key); - - b = BV (clib_bihash_get_bucket) (h, hash); - - if (BV (clib_bihash_bucket_is_empty) (b)) - return -1; - - if (PREDICT_FALSE (b->lock)) - { - volatile BVT (clib_bihash_bucket) * bv = b; - while (bv->lock) - CLIB_PAUSE (); - } - - hash >>= h->log2_nbuckets; - - v = BV (clib_bihash_get_value) (h, b->offset); - limit = BIHASH_KVP_PER_PAGE; - v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0; - if (PREDICT_FALSE (b->linear_search)) - limit <<= b->log2_pages; - - for (i = 0; i < limit; i++) - { - if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key)) - { - *valuep = v->kvp[i]; - return 0; - } - } - return -1; + return BV (clib_bihash_search_inline_2) (h, search_key, valuep); } u8 *BV (format_bihash) (u8 * s, va_list * args) diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index 50b4af65710..f49c572b193 100644 --- a/src/vppinfra/bihash_template.h +++ b/src/vppinfra/bihash_template.h @@ -380,6 +380,13 @@ static inline int BV (clib_bihash_search_inline_with_hash) BVT (clib_bihash_bucket) * b; int i, limit; + /* *INDENT-OFF* */ + static const BVT (clib_bihash_bucket) mask = { + .linear_search = 1, + .log2_pages = -1 + }; + /* *INDENT-ON* */ + #if BIHASH_LAZY_INSTANTIATE if (PREDICT_FALSE (alloc_arena (h) == 0)) return -1; @@ -397,15 +404,18 @@ static inline int BV (clib_bihash_search_inline_with_hash) CLIB_PAUSE (); } - hash >>= h->log2_nbuckets; - v = BV (clib_bihash_get_value) (h, b->offset); /* If the bucket has unresolvable collisions, use linear search */ limit = BIHASH_KVP_PER_PAGE; - v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0; - if (PREDICT_FALSE (b->linear_search)) - limit <<= b->log2_pages; + + if (PREDICT_FALSE (b->as_u64 & mask.as_u64)) + { + if (PREDICT_FALSE (b->linear_search)) + limit <<= b->log2_pages; + else + v += extract_bits (hash, h->log2_nbuckets, b->log2_pages); + } for (i = 0; i < limit; i++) { @@ -452,12 +462,13 @@ static inline void BV (clib_bihash_prefetch_data) if (PREDICT_FALSE (BV (clib_bihash_bucket_is_empty) (b))) return; - hash >>= h->log2_nbuckets; v = BV (clib_bihash_get_value) (h, b->offset); - v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0; + if (PREDICT_FALSE (b->log2_pages && b->linear_search == 0)) + v += extract_bits (hash, h->log2_nbuckets, b->log2_pages); - clib_prefetch_load (v); + CLIB_PREFETCH (v, BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv)), + LOAD); } static inline int BV (clib_bihash_search_inline_2_with_hash) @@ -468,6 +479,13 @@ static inline int BV (clib_bihash_search_inline_2_with_hash) BVT (clib_bihash_bucket) * b; int i, limit; +/* *INDENT-OFF* */ + static const BVT (clib_bihash_bucket) mask = { + .linear_search = 1, + .log2_pages = -1 + }; +/* *INDENT-ON* */ + ASSERT (valuep); #if BIHASH_LAZY_INSTANTIATE @@ -487,14 +505,18 @@ static inline int BV (clib_bihash_search_inline_2_with_hash) CLIB_PAUSE (); } - hash >>= h->log2_nbuckets; v = BV (clib_bihash_get_value) (h, b->offset); /* If the bucket has unresolvable collisions, use linear search */ limit = BIHASH_KVP_PER_PAGE; - v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0; - if (PREDICT_FALSE (b->linear_search)) - limit <<= b->log2_pages; + + if (PREDICT_FALSE (b->as_u64 & mask.as_u64)) + { + if (PREDICT_FALSE (b->linear_search)) + limit <<= b->log2_pages; + else + v += extract_bits (hash, h->log2_nbuckets, b->log2_pages); + } for (i = 0; i < limit; i++) { diff --git a/src/vppinfra/clib.h b/src/vppinfra/clib.h index dac41adb165..bdea43b3fe0 100644 --- a/src/vppinfra/clib.h +++ b/src/vppinfra/clib.h @@ -40,6 +40,10 @@ #include +#ifdef __x86_64__ +#include +#endif + /* Standalone means to not assume we are running on a Unix box. */ #if ! defined (CLIB_STANDALONE) && ! defined (CLIB_LINUX_KERNEL) #define CLIB_UNIX @@ -293,6 +297,15 @@ flt_round_to_multiple (f64 x, f64 f) return f * flt_round_nearest (x / f); } +always_inline uword +extract_bits (uword x, int start, int count) +{ +#ifdef __BMI__ + return _bextr_u64 (x, start, count); +#endif + return (x >> start) & pow2_mask (count); +} + #define clib_max(x,y) \ ({ \ __typeof__ (x) _x = (x); \ -- 2.16.6