[ovs-dev] [PATCH v2] lib/bitmap: Faster bitmap functions.
Jarno Rajahalme
jrajahalme at nicira.com
Fri Oct 3 20:22:07 UTC 2014
Replace bitwise loops with a single operation, inline all bitmap
functions. Inlining allows the compiler to remove unnecessary code
due to some parameters being compile-time constants.
Before:
$ tests/ovstest test-bitmap benchmark 1000000
bitmap equal: 341 ms
bitmap scan: 8089 ms
After:
$ tests/ovstest test-bitmap benchmark 1000000
bitmap equal: 152 ms
bitmap scan: 146 ms
Signed-off-by: Kmindg <kmindg at gmail.com>
Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
lib/automake.mk | 1 -
lib/bitmap.c | 155 -----------------------------------------
lib/bitmap.h | 193 ++++++++++++++++++++++++++++++++++++++++++++++-----
lib/util.h | 2 +-
tests/test-bitmap.c | 12 ++--
5 files changed, 181 insertions(+), 182 deletions(-)
delete mode 100644 lib/bitmap.c
diff --git a/lib/automake.mk b/lib/automake.mk
index c44a77f..374f561 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -23,7 +23,6 @@ lib_libopenvswitch_la_SOURCES = \
lib/backtrace.h \
lib/bfd.c \
lib/bfd.h \
- lib/bitmap.c \
lib/bitmap.h \
lib/bundle.c \
lib/bundle.h \
diff --git a/lib/bitmap.c b/lib/bitmap.c
deleted file mode 100644
index 7889aa1..0000000
--- a/lib/bitmap.c
+++ /dev/null
@@ -1,155 +0,0 @@
-/*
- * Copyright (c) 2008, 2009, 2011, 2014 Nicira, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at:
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include <config.h>
-#include "bitmap.h"
-#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
-bitmap_set_multiple(unsigned long *bitmap, size_t start, size_t count,
- bool value)
-{
- for (; count && start % BITMAP_ULONG_BITS; count--) {
- bitmap_set(bitmap, start++, value);
- }
- for (; count >= BITMAP_ULONG_BITS; count -= BITMAP_ULONG_BITS) {
- *bitmap_unit__(bitmap, start) = -(unsigned long) value;
- start += BITMAP_ULONG_BITS;
- }
- for (; count; count--) {
- bitmap_set(bitmap, start++, value);
- }
-}
-
-/* Compares the 'n' bits in bitmaps 'a' and 'b'. Returns true if all bits are
- * equal, false otherwise. */
-bool
-bitmap_equal(const unsigned long *a, const unsigned long *b, size_t n)
-{
- size_t i;
-
- 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;
- }
- }
- 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'. */
-size_t
-bitmap_scan(const unsigned long int *bitmap, bool target,
- size_t start, size_t end)
-{
- /* XXX slow */
- size_t i;
-
- for (i = start; i < end; i++) {
- if (bitmap_is_set(bitmap, i) == target) {
- break;
- }
- }
- return i;
-}
-
-/* Returns the number of 1-bits in the 'n'-bit bitmap at 'bitmap'. */
-size_t
-bitmap_count1(const unsigned long int *bitmap, size_t n)
-{
- size_t i;
- size_t count = 0;
-
- BUILD_ASSERT(ULONG_MAX <= UINT64_MAX);
- for (i = 0; i < BITMAP_N_LONGS(n); i++) {
- count += count_1bits(bitmap[i]);
- }
-
- return count;
-}
-
-/* "dst &= arg;" for n-bit dst and arg. */
-void
-bitmap_and(unsigned long *dst, const unsigned long *arg, size_t n)
-{
- size_t i;
-
- for (i = 0; i < BITMAP_N_LONGS(n); i++) {
- dst[i] &= arg[i];
- }
-}
-
-/* "dst |= arg;" for n-bit dst and arg. */
-void
-bitmap_or(unsigned long *dst, const unsigned long *arg, size_t n)
-{
- size_t i;
-
- for (i = 0; i < BITMAP_N_LONGS(n); i++) {
- dst[i] |= arg[i];
- }
-}
-
-/* "dst = ~dst;" for n-bit dst. */
-void
-bitmap_not(unsigned long *dst, size_t n)
-{
- size_t i;
-
- for (i = 0; i < n / BITMAP_ULONG_BITS; i++) {
- dst[i] = ~dst[i];
- }
- if (n % BITMAP_ULONG_BITS) {
- 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..e771e60 100644
--- a/lib/bitmap.h
+++ b/lib/bitmap.h
@@ -55,7 +55,27 @@ 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 unsigned long *
+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] >>= BITMAP_ULONG_BITS - r_bits;
+ }
+ return bitmap;
+}
+
+/* Allocates and returns a bitmap initialized to all-1-bits. */
+static inline unsigned long *
+bitmap_allocate1(size_t n_bits)
+{
+ return bitmap_init1(xmalloc(bitmap_n_bytes(n_bits)), n_bits);
+}
static inline unsigned long *
bitmap_clone(const unsigned long *bitmap, size_t n_bits)
@@ -75,43 +95,178 @@ bitmap_is_set(const unsigned long *bitmap, size_t offset)
return (*bitmap_unit__(bitmap, offset) & bitmap_bit__(offset)) != 0;
}
-static inline void
+static inline unsigned long *
bitmap_set1(unsigned long *bitmap, size_t offset)
{
*bitmap_unit__(bitmap, offset) |= bitmap_bit__(offset);
+ return bitmap;
}
-static inline void
+static inline unsigned long *
bitmap_set0(unsigned long *bitmap, size_t offset)
{
*bitmap_unit__(bitmap, offset) &= ~bitmap_bit__(offset);
+ return bitmap;
}
-static inline void
+static inline unsigned long *
bitmap_set(unsigned long *bitmap, size_t offset, bool value)
{
+ return (value) ? bitmap_set1(bitmap, offset) : bitmap_set0(bitmap, offset);
+}
+
+/* Sets 'n' bits of a single unit. */
+static inline void
+bitmap_set_n__(unsigned long *bitmap, size_t start, size_t n, bool value)
+{
+ unsigned long mask = ((1UL << n) - 1) << start % BITMAP_ULONG_BITS;
+
if (value) {
- bitmap_set1(bitmap, offset);
+ *bitmap_unit__(bitmap, start) |= mask;
} else {
- bitmap_set0(bitmap, offset);
+ *bitmap_unit__(bitmap, start) &= ~mask;
+ }
+}
+
+/* Sets 'count' consecutive bits in 'bitmap', starting at bit offset 'start',
+ * to 'value'. */
+static inline unsigned long *
+bitmap_set_multiple(unsigned long *bitmap, size_t start, size_t count,
+ bool value)
+{
+ if (count && start % BITMAP_ULONG_BITS) {
+ size_t n = MIN(count, BITMAP_ULONG_BITS - start % BITMAP_ULONG_BITS);
+
+ bitmap_set_n__(bitmap, start, n, value);
+ count -= n;
+ start += n;
+ }
+ for (; count >= BITMAP_ULONG_BITS; count -= BITMAP_ULONG_BITS) {
+ *bitmap_unit__(bitmap, start) = (unsigned long)!value - 1;
+ start += BITMAP_ULONG_BITS;
+ }
+ if (count) {
+ bitmap_set_n__(bitmap, start, count, value);
+ }
+ return bitmap;
+}
+
+/* Returns the number of 1-bits in the 'n'-bit bitmap at 'bitmap'. */
+static inline size_t
+bitmap_count1(const unsigned long int *bitmap, size_t n)
+{
+ size_t i;
+ size_t count = 0;
+
+ BUILD_ASSERT(ULONG_MAX <= UINT64_MAX);
+ for (i = 0; i < BITMAP_N_LONGS(n); i++) {
+ count += count_1bits(bitmap[i]);
}
+ return count;
}
-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_count1(const unsigned long *, size_t n);
+/* "dst &= arg;" for n-bit dst and arg. */
+static inline unsigned long *
+bitmap_and(unsigned long *dst, const unsigned long *arg, size_t n)
+{
+ size_t i;
+
+ for (i = 0; i < BITMAP_N_LONGS(n); i++) {
+ dst[i] &= arg[i];
+ }
+ return dst;
+}
+
+/* "dst |= arg;" for n-bit dst and arg. */
+static inline unsigned long *
+bitmap_or(unsigned long *dst, const unsigned long *arg, size_t n)
+{
+ size_t i;
+
+ for (i = 0; i < BITMAP_N_LONGS(n); i++) {
+ dst[i] |= arg[i];
+ }
+ return dst;
+}
+
+/* "dst = ~dst;" for n-bit dst. */
+static inline unsigned long *
+bitmap_not(unsigned long *dst, size_t n)
+{
+ size_t i;
+
+ for (i = 0; i < n / BITMAP_ULONG_BITS; i++) {
+ dst[i] = ~dst[i];
+ }
+ if (n % BITMAP_ULONG_BITS) {
+ dst[i] ^= (1UL << (n % BITMAP_ULONG_BITS)) - 1;
+ }
+ return dst;
+}
-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);
+/* Compares the 'n' bits in bitmaps 'a' and 'b'. Returns true if all bits are
+ * equal, false otherwise. */
+static inline bool
+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;
+ }
+ if (n % BITMAP_ULONG_BITS) {
+ unsigned long mask = (1UL << n % BITMAP_ULONG_BITS) - 1;
+ unsigned long diff = *bitmap_unit__(a, n) ^ *bitmap_unit__(b, n);
-bool bitmap_is_all_zeros(const unsigned long *, size_t n);
+ 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'. 'target' is typically a
+ * compile-time constant, so it makes sense to inline this. Compiler may also
+ * optimize parts away depending on the 'start' and 'end' values passed in. */
+static inline size_t
+bitmap_scan(const unsigned long *bitmap, bool target, size_t start, size_t end)
+{
+ if (OVS_LIKELY(start < end)) {
+ unsigned long *p, unit;
+
+ p = bitmap_unit__(bitmap, start);
+ unit = (target ? *p : ~*p) >> (start % BITMAP_ULONG_BITS);
+ if (!unit) {
+ start -= start % BITMAP_ULONG_BITS; /* Round down. */
+ start += BITMAP_ULONG_BITS; /* Start of the next unit. */
+
+ for (; start < end; start += BITMAP_ULONG_BITS) {
+ unit = target ? *++p : ~*++p;
+ if (unit) {
+ goto found;
+ }
+ }
+ return end;
+ }
+found:
+ start += raw_ctz(unit); /* unit != 0 */
+ if (OVS_LIKELY(start < end)) {
+ return start;
+ }
+ }
+ return end;
+}
+
+/* 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_scan(bitmap, true, 0, n) == n;
+}
-#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))
+#define BITMAP_FOR_EACH_1_RANGE(IDX, BEGIN, END, BITMAP) \
+ for ((IDX) = bitmap_scan(BITMAP, true, BEGIN, END); (IDX) < (END); \
+ (IDX) = bitmap_scan(BITMAP, true, (IDX) + 1, END))
+#define BITMAP_FOR_EACH_1(IDX, SIZE, BITMAP) \
+ BITMAP_FOR_EACH_1_RANGE(IDX, 0, SIZE, BITMAP)
#endif /* bitmap.h */
diff --git a/lib/util.h b/lib/util.h
index 7da7aa8..10af3e6 100644
--- a/lib/util.h
+++ b/lib/util.h
@@ -476,7 +476,7 @@ 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);
diff --git a/tests/test-bitmap.c b/tests/test-bitmap.c
index 3644419..9e874b5 100644
--- a/tests/test-bitmap.c
+++ b/tests/test-bitmap.c
@@ -82,12 +82,12 @@ test_bitmap_scan(void)
bitmap_set1(a, MAX_BITS - 1);
assert(bitmap_scan(a, true, 0, MAX_BITS) == MAX_BITS - 1);
bitmap_set1(a, MAX_BITS - BITMAP_ULONG_BITS + 1);
- assert(bitmap_scan(a, true, 0, MAX_BITS - 1)
+ assert(bitmap_scan(a, true, 3, MAX_BITS)
== MAX_BITS - BITMAP_ULONG_BITS + 1);
bitmap_set1(a, BITMAP_ULONG_BITS - 1);
- assert(bitmap_scan(a, true, 0, MAX_BITS - 1) == BITMAP_ULONG_BITS - 1);
+ assert(bitmap_scan(a, true, 7, MAX_BITS - 1) == BITMAP_ULONG_BITS - 1);
bitmap_set1(a, 0);
- assert(bitmap_scan(a, true, 0, MAX_BITS - 1) == 0);
+ assert(bitmap_scan(a, true, 0, MAX_BITS - 7) == 0);
bitmap_set_multiple(a, 0, MAX_BITS, true);
@@ -104,12 +104,12 @@ test_bitmap_scan(void)
bitmap_set0(a, MAX_BITS - 1);
assert(bitmap_scan(a, false, 0, MAX_BITS) == MAX_BITS - 1);
bitmap_set0(a, MAX_BITS - BITMAP_ULONG_BITS + 1);
- assert(bitmap_scan(a, false, 0, MAX_BITS - 1)
+ assert(bitmap_scan(a, false, 3, MAX_BITS)
== MAX_BITS - BITMAP_ULONG_BITS + 1);
bitmap_set0(a, BITMAP_ULONG_BITS - 1);
- assert(bitmap_scan(a, false, 0, MAX_BITS - 1) == BITMAP_ULONG_BITS - 1);
+ assert(bitmap_scan(a, false, 7, MAX_BITS - 1) == BITMAP_ULONG_BITS - 1);
bitmap_set0(a, 0);
- assert(bitmap_scan(a, false, 0, MAX_BITS - 1) == 0);
+ assert(bitmap_scan(a, false, 0, MAX_BITS - 7) == 0);
free(a);
}
--
1.7.10.4
More information about the dev
mailing list