[ovs-dev] [PATCH 3/3] lib/bitmap: Faster bitmap_scan().
Jarno Rajahalme
jrajahalme at nicira.com
Wed Sep 24 18:24:02 UTC 2014
Before:
$ tests/ovstest test-bitmap benchmark 1000000
bitmap equal: 328 ms
bitmap scan: 8159 ms
After:
$ tests/ovstest test-bitmap benchmark 1000000
bitmap equal: 230 ms
bitmap scan: 185 ms
Signed-off-by: Kmindg <kmindg at gmail.com>
Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
lib/bitmap.c | 102 +++++++++++++++++++++++++++++++++-------------------------
lib/bitmap.h | 57 ++++++++++++++++++++++++++++----
lib/util.h | 10 +++++-
3 files changed, 117 insertions(+), 52 deletions(-)
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 7889aa1..0520210 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -19,28 +19,6 @@
#include <string.h>
#include "util.h"
-/* Allocates and returns a bitmap initialized to all-1-bits. */
-unsigned long *
-bitmap_allocate1(size_t n_bits)
-{
- size_t n_bytes = bitmap_n_bytes(n_bits);
- size_t n_longs = bitmap_n_longs(n_bits);
- size_t r_bits = n_bits % BITMAP_ULONG_BITS;
- unsigned long *bitmap;
-
- /* Allocate and initialize most of the bitmap. */
- bitmap = xmalloc(n_bytes);
- memset(bitmap, 0xff, n_bytes);
-
- /* Ensure that the last "unsigned long" in the bitmap only has as many
- * 1-bits as there actually should be. */
- if (r_bits) {
- bitmap[n_longs - 1] = (1UL << r_bits) - 1;
- }
-
- return bitmap;
-}
-
/* Sets 'count' consecutive bits in 'bitmap', starting at bit offset 'start',
* to 'value'. */
void
@@ -69,30 +47,74 @@ bitmap_equal(const unsigned long *a, const unsigned long *b, size_t n)
if (memcmp(a, b, n / BITMAP_ULONG_BITS * sizeof(unsigned long))) {
return false;
}
- for (i = ROUND_DOWN(n, BITMAP_ULONG_BITS); i < n; i++) {
- if (bitmap_is_set(a, i) != bitmap_is_set(b, i)) {
- return false;
- }
+ i = ROUND_DOWN(n, BITMAP_ULONG_BITS);
+ n -= i; /* Remaining bits. */
+ if (n) {
+ unsigned long mask = (1UL << n) - 1;
+ unsigned long diff = *bitmap_unit__(a, i) ^ *bitmap_unit__(b, i);
+
+ return !(diff & mask);
}
return true;
}
/* Scans 'bitmap' from bit offset 'start' to 'end', excluding 'end' itself.
- * Returns the bit offset of the lowest-numbered bit set to 'target', or 'end'
- * if all of the bits are set to '!target'. */
+ * Returns the bit offset of the lowest-numbered bit set to 1, or 'end'
+ * if all of the bits are set to 0. */
size_t
-bitmap_scan(const unsigned long int *bitmap, bool target,
- size_t start, size_t end)
+bitmap_scan1(const unsigned long *bitmap, size_t start, size_t end)
{
- /* XXX slow */
- size_t i;
+ if (OVS_LIKELY(start < end)) {
+ unsigned long *p, unit;
+
+ p = bitmap_unit__(bitmap, start);
+ unit = *p >> (start % BITMAP_ULONG_BITS);
+ if (!unit) {
+ start &= ~(BITMAP_ULONG_BITS - 1); /* Round down. */
+ start += BITMAP_ULONG_BITS; /* Start of the next unit. */
+
+ while (start < end && !(unit = *++p)) {
+ start += BITMAP_ULONG_BITS;
+ }
+ if (!unit) {
+ return end;
+ }
+ }
+ start += rightmost_1bit_idx64(unit);
+ if (OVS_LIKELY(start < end)) {
+ return start;
+ }
+ }
+ return end;
+}
- for (i = start; i < end; i++) {
- if (bitmap_is_set(bitmap, i) == target) {
- break;
+/* This differs only in that we invert the data we read from the bitmap,
+ * so we can still look for ones. */
+size_t
+bitmap_scan0(const unsigned long *bitmap, size_t start, size_t end)
+{
+ if (OVS_LIKELY(start < end)) {
+ unsigned long *p, unit;
+
+ p = bitmap_unit__(bitmap, start);
+ unit = ~*p >> (start % BITMAP_ULONG_BITS);
+ if (!unit) {
+ start &= ~(BITMAP_ULONG_BITS - 1); /* Round down. */
+ start += BITMAP_ULONG_BITS; /* Start of the next unit. */
+
+ while (start < end && !(unit = ~*++p)) {
+ start += BITMAP_ULONG_BITS;
+ }
+ if (!unit) {
+ return end;
+ }
+ }
+ start += rightmost_1bit_idx64(unit);
+ if (OVS_LIKELY(start < end)) {
+ return start;
}
}
- return i;
+ return end;
}
/* Returns the number of 1-bits in the 'n'-bit bitmap at 'bitmap'. */
@@ -145,11 +167,3 @@ bitmap_not(unsigned long *dst, size_t n)
dst[i] ^= (1u << (n % BITMAP_ULONG_BITS)) - 1;
}
}
-
-/* Returns true if all of the 'n' bits in 'bitmap' are 0,
- * false if at least one bit is a 1.*/
-bool
-bitmap_is_all_zeros(const unsigned long *bitmap, size_t n)
-{
- return bitmap_scan(bitmap, true, 0, n) == n;
-}
diff --git a/lib/bitmap.h b/lib/bitmap.h
index ace091f..6cc4b14 100644
--- a/lib/bitmap.h
+++ b/lib/bitmap.h
@@ -55,7 +55,28 @@ bitmap_allocate(size_t n_bits)
return xzalloc(bitmap_n_bytes(n_bits));
}
-unsigned long *bitmap_allocate1(size_t n_bits);
+/* Initializes bitmap to all-1-bits and returns the bitmap pointer. */
+static inline void
+bitmap_init1(unsigned long *bitmap, size_t n_bits)
+{
+ size_t n_longs = bitmap_n_longs(n_bits);
+ size_t n_bytes = bitmap_n_bytes(n_bits);
+ size_t r_bits = n_bits % BITMAP_ULONG_BITS;
+
+ memset(bitmap, 0xff, n_bytes);
+ if (r_bits) {
+ bitmap[n_longs - 1] >>= 64 - r_bits;
+ }
+}
+
+/* Allocates and returns a bitmap initialized to all-1-bits. */
+static inline unsigned long *
+bitmap_allocate1(size_t n_bits)
+{
+ unsigned long *bitmap = xmalloc(bitmap_n_bytes(n_bits));
+ bitmap_init1(bitmap, n_bits);
+ return bitmap;
+}
static inline unsigned long *
bitmap_clone(const unsigned long *bitmap, size_t n_bits)
@@ -100,18 +121,40 @@ bitmap_set(unsigned long *bitmap, size_t offset, bool value)
void bitmap_set_multiple(unsigned long *, size_t start, size_t count,
bool value);
bool bitmap_equal(const unsigned long *, const unsigned long *, size_t n);
-size_t bitmap_scan(const unsigned long int *, bool target,
- size_t start, size_t end);
+size_t bitmap_scan1(const unsigned long *bitmap, size_t start, size_t end);
+size_t bitmap_scan0(const unsigned long *bitmap, size_t start, size_t end);
size_t bitmap_count1(const unsigned long *, size_t n);
void bitmap_and(unsigned long *dst, const unsigned long *arg, size_t n);
void bitmap_or(unsigned long *dst, const unsigned long *arg, size_t n);
void bitmap_not(unsigned long *dst, size_t n);
-bool bitmap_is_all_zeros(const unsigned long *, size_t n);
+/* Returns true if all of the 'n' bits in 'bitmap' are 0,
+ * false if at least one bit is a 1.*/
+static inline bool
+bitmap_is_all_zeros(const unsigned long *bitmap, size_t n)
+{
+ return bitmap_scan1(bitmap, 0, n) == n;
+}
+
+#define BITMAP_FOR_EACH_1_RANGE(IDX, BEGIN, END, BITMAP) \
+ for ((IDX) = bitmap_scan1(BITMAP, BEGIN, END); (IDX) < (END); \
+ (IDX) = bitmap_scan1(BITMAP, (IDX) + 1, END))
+#define BITMAP_FOR_EACH_1(IDX, SIZE, BITMAP) \
+ BITMAP_FOR_EACH_1_RANGE(IDX, 0, SIZE, BITMAP)
+
+/* Scans 'bitmap' from bit offset 'start' to 'end', excluding 'end' itself.
+ * Returns the bit offset of the lowest-numbered bit set to 'target', or 'end'
+ * if all of the bits are set to '!target'. 'target' is typically a
+ * compile-time constant, so it makes sense to inline this. */
+static inline size_t
+bitmap_scan(const unsigned long *bitmap, bool target,
+ size_t start, size_t end)
+{
+ return target
+ ? bitmap_scan1(bitmap, start, end)
+ : bitmap_scan0(bitmap, start, end);
+}
-#define BITMAP_FOR_EACH_1(IDX, SIZE, BITMAP) \
- for ((IDX) = bitmap_scan(BITMAP, 1, 0, SIZE); (IDX) < (SIZE); \
- (IDX) = bitmap_scan(BITMAP, 1, (IDX) + 1, SIZE))
#endif /* bitmap.h */
diff --git a/lib/util.h b/lib/util.h
index 7da7aa8..757eec2 100644
--- a/lib/util.h
+++ b/lib/util.h
@@ -476,12 +476,20 @@ zero_rightmost_1bit(uintmax_t x)
*
* Unlike the other functions for rightmost 1-bits, this function only works
* with 32-bit integers. */
-static inline uint32_t
+static inline int
rightmost_1bit_idx(uint32_t x)
{
return ctz32(x);
}
+/* Returns the index of the rightmost 1-bit in 'x' (e.g. 01011000 => 3), or 64
+ * if 'x' is 0. */
+static inline int
+rightmost_1bit_idx64(uint64_t x)
+{
+ return ctz64(x);
+}
+
/* Returns the index of the leftmost 1-bit in 'x' (e.g. 01011000 => 6), or 32
* if 'x' is 0.
*
--
1.7.10.4
More information about the dev
mailing list