From 1105600416e0560cb05120a22e0a2e7359a13665 Mon Sep 17 00:00:00 2001 From: Damjan Marion Date: Thu, 10 May 2018 13:40:44 +0200 Subject: vppinfra: use count_trailing_zeros in sparse_vec_index It is much cheaper to use ctzll than to do shift,subtract and mask in likely case when we are looking for 1st set bit in the uword. Change-Id: I31954081571978878c7098bafad0c85a91755fa2 Signed-off-by: Damjan Marion --- src/vppinfra/sparse_vec.h | 33 +++++++++++++++++++++++---------- 1 file changed, 23 insertions(+), 10 deletions(-) (limited to 'src/vppinfra/sparse_vec.h') diff --git a/src/vppinfra/sparse_vec.h b/src/vppinfra/sparse_vec.h index 0da154d8b68..cfa5778e290 100644 --- a/src/vppinfra/sparse_vec.h +++ b/src/vppinfra/sparse_vec.h @@ -108,15 +108,20 @@ sparse_vec_index_internal (void *v, h = sparse_vec_header (v); i = sparse_index / BITS (h->is_member_bitmap[0]); - b = (uword) 1 << (uword) (sparse_index % BITS (h->is_member_bitmap[0])); + b = sparse_index % BITS (h->is_member_bitmap[0]); ASSERT (i < vec_len (h->is_member_bitmap)); ASSERT (i < vec_len (h->member_counts)); w = h->is_member_bitmap[i]; - d = h->member_counts[i] + count_set_bits (w & (b - 1)); - is_member = (w & b) != 0; + if (PREDICT_TRUE (maybe_range == 0 && insert == 0 && + count_trailing_zeros (w) == b)) + return h->member_counts[i] + 1; + + d = h->member_counts[i] + count_set_bits (w & ((1ULL << b) - 1)); + is_member = (w & (1ULL << b)) != 0; + if (maybe_range) { u8 r = h->range_flags[d]; @@ -134,7 +139,7 @@ sparse_vec_index_internal (void *v, if (!is_member) { uword j; - w |= b; + w |= 1ULL << b; h->is_member_bitmap[i] = w; for (j = i + 1; j < vec_len (h->member_counts); j++) h->member_counts[j] += 1; @@ -170,8 +175,8 @@ sparse_vec_index2 (void *v, i0 = si0 / BITS (h->is_member_bitmap[0]); i1 = si1 / BITS (h->is_member_bitmap[0]); - b0 = (uword) 1 << (uword) (si0 % BITS (h->is_member_bitmap[0])); - b1 = (uword) 1 << (uword) (si1 % BITS (h->is_member_bitmap[0])); + b0 = si0 % BITS (h->is_member_bitmap[0]); + b1 = si1 % BITS (h->is_member_bitmap[0]); ASSERT (i0 < vec_len (h->is_member_bitmap)); ASSERT (i1 < vec_len (h->is_member_bitmap)); @@ -182,8 +187,16 @@ sparse_vec_index2 (void *v, w0 = h->is_member_bitmap[i0]; w1 = h->is_member_bitmap[i1]; - v0 = w0 & (b0 - 1); - v1 = w1 & (b1 - 1); + if (PREDICT_TRUE ((count_trailing_zeros (w0) == b0) + + (count_trailing_zeros (w1) == b1) == 2)) + { + *i0_return = h->member_counts[i0] + 1; + *i1_return = h->member_counts[i1] + 1; + return; + } + + v0 = w0 & ((1ULL << b0) - 1); + v1 = w1 & ((1ULL << b1) - 1); /* Speculate that masks will have zero or one bits set. */ d0 = h->member_counts[i0] + (v0 != 0); @@ -196,8 +209,8 @@ sparse_vec_index2 (void *v, d1 += count_set_bits (v1) - (v1 != 0); } - is_member0 = (w0 & b0) != 0; - is_member1 = (w1 & b1) != 0; + is_member0 = (w0 & (1ULL << b0)) != 0; + is_member1 = (w1 & (1ULL << b1)) != 0; d0 = is_member0 ? d0 : 0; d1 = is_member1 ? d1 : 0; -- cgit 1.2.3-korg