[ovs-dev] [PATCH] bitmap: Optimize bitmap_equal and bitmap_scan

[Kmindg]

---
 lib/bitmap.c | 36 ++++++++++++++++++++++++------------
 1 file changed, 24 insertions(+), 12 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 7889aa1..b62a8be 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -65,16 +65,17 @@ 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;
-        }
-    }
-    return true;
+
+    i = bitmap_n_longs(n);
+    mask <<= n % BITMAP_ULONG_BITS;
+    mask -= 1;
+
+    return !mask || !((a[i] ^ b[i]) & mask);
 }
 
 /* Scans 'bitmap' from bit offset 'start' to 'end', excluding 'end' itself.
@@ -84,15 +85,26 @@ 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) {
+    size_t count = end - start;
+    unsigned long t = -(unsigned long)(!target);
+    for (; count && start % BITMAP_ULONG_BITS; count--,start++) {
+        if (bitmap_is_set(bitmap, start) == target) {
+            return start;
+        }
+    }
+    for (; count >= BITMAP_ULONG_BITS; count -= BITMAP_ULONG_BITS) {
+        if (*bitmap_unit__(bitmap, start) != t) {
             break;
         }
+        start += BITMAP_ULONG_BITS;
+    }
+    for (; count; count--,start++) {
+        if (bitmap_is_set(bitmap, start) == target) {
+            return start;
+        }
     }
-    return i;
+
+    return start;
 }
 
 /* Returns the number of 1-bits in the 'n'-bit bitmap at 'bitmap'. */
-- 
2.0.3

_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev