diff options
author | Jarno Rajahalme <jrajahalme@nicira.com> | 2014-10-07 14:35:04 -0700 |
---|---|---|
committer | Jarno Rajahalme <jrajahalme@nicira.com> | 2014-10-07 14:35:04 -0700 |
commit | 795b3288aa5cb869da4fd50f5ebd09cdcc6d0c5c (patch) | |
tree | 1640dd6e18100608b72b28b6db2311ee193cb899 | |
parent | 1f2e8d2d85ab7dac37653c4f9d034ce452f289ca (diff) | |
download | openvswitch-795b3288aa5cb869da4fd50f5ebd09cdcc6d0c5c.tar.gz |
lib/bitmap: Faster bitmap functions.
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: Jarno Rajahalme <jrajahalme@nicira.com>
Co-authored-by: Kmindg <kmindg@gmail.com>
Acked-by: Ben Pfaff <blp@nicira.com>
-rw-r--r-- | lib/automake.mk | 1 | ||||
-rw-r--r-- | lib/bitmap.c | 155 | ||||
-rw-r--r-- | lib/bitmap.h | 193 | ||||
-rw-r--r-- | lib/util.h | 2 | ||||
-rw-r--r-- | tests/test-bitmap.c | 12 |
5 files changed, 181 insertions, 182 deletions
diff --git a/lib/automake.mk b/lib/automake.mk index b1d40b962..6c1db9a7e 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 7889aa1de..000000000 --- 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 eb3d57567..a2ca46e32 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,44 +95,179 @@ 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) /* More efficient access to a map of single ulong. */ #define ULONG_FOR_EACH_1(IDX, MAP) \ diff --git a/lib/util.h b/lib/util.h index ecc8e5f72..af2273d92 100644 --- a/lib/util.h +++ b/lib/util.h @@ -512,7 +512,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 3644419d1..9e874b5ad 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); } |