summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/bihash_template.h
diff options
context:
space:
mode:
authorDamjan Marion <damarion@cisco.com>2020-04-23 13:41:47 +0200
committerDamjan Marion <damarion@cisco.com>2020-04-23 13:45:25 +0200
commit68e5fd5206e75cb367375b4fea2e531a3712fd06 (patch)
tree857b29b0a960a4147c6009cf2edc70bdc0ca7be3 /src/vppinfra/bihash_template.h
parent59f71132edffcfa1b94c400736575bd55bdbd7d7 (diff)
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>
Diffstat (limited to 'src/vppinfra/bihash_template.h')
-rw-r--r--src/vppinfra/bihash_template.h46
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++)
{