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 <damarion@cisco.com>

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 <vppinfra/config.h>
 
+#ifdef  __x86_64__
+#include <x86intrin.h>
+#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);			\