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>

1 files changed, 34 insertions, 12 deletions

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++)
     {