ovstest test-bitmap benchmark 100000 (without this commit): bitmap equal: 52 ms bitmap scan: 758 ms
ovstest test-bitmap benchmark 100000 (with this commit): bitmap equal: 37 ms bitmap scan: 34 ms Tested on Intel Xeon E5-2620 v2 @ 2.10GHz Signed-off-by: Kmindg <[email protected]> --- lib/bitmap.c | 59 ++++++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 49 insertions(+), 10 deletions(-) diff --git a/lib/bitmap.c b/lib/bitmap.c index 7889aa1..13365fb 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -65,16 +65,27 @@ bool bitmap_equal(const unsigned long *a, const unsigned long *b, size_t n) { size_t i; + unsigned long mask = 1; 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 = bitmap_n_longs(n) - 1; + mask <<= n % BITMAP_ULONG_BITS; + mask -= 1; + + return !mask || !((a[i] ^ b[i]) & mask); +} + +static size_t +bitmap_scan__(unsigned long v, bool target) +{ + if (!target) { + v = ~v; } - return true; + + return rightmost_1bit_idx_64(v); } /* Scans 'bitmap' from bit offset 'start' to 'end', excluding 'end' itself. @@ -84,15 +95,43 @@ size_t bitmap_scan(const unsigned long int *bitmap, bool target, size_t start, size_t end) { - /* XXX slow */ - size_t i; + size_t count = end - start; + unsigned long t; + unsigned long v; + size_t idx; + + t = start % BITMAP_ULONG_BITS; + if (t && count) { + /* 'start' is not aligned to BITMAP_ULONG_BITS. */ + v = *bitmap_unit__(bitmap, start) >> t; + + idx = bitmap_scan__(v, target); + if (idx < BITMAP_ULONG_BITS - t) { + return idx + start; + } + count -= BITMAP_ULONG_BITS - t; + start += BITMAP_ULONG_BITS - t; + } - for (i = start; i < end; i++) { - if (bitmap_is_set(bitmap, i) == target) { + /* 't' is a unsigned long unit which does not contain 'target'. */ + t = -(unsigned long)(!target); + for (; count >= BITMAP_ULONG_BITS; count -= BITMAP_ULONG_BITS) { + if (*bitmap_unit__(bitmap, start) != t) { break; } + start += BITMAP_ULONG_BITS; } - return i; + + /* 'end' is not aligned to BITMAP_ULONG_BITS or we have found a unsigned + * long unit which contains 'target'. */ + if (count) { + v = *bitmap_unit__(bitmap, start); + + idx = bitmap_scan__(v, target); + return MIN(start + idx, end); + } + + return start; } /* Returns the number of 1-bits in the 'n'-bit bitmap at 'bitmap'. */ -- 1.7.9.5 _______________________________________________ dev mailing list [email protected] http://openvswitch.org/mailman/listinfo/dev
