Skip to contentSkip to conversation

bitops: use vector algorithm to optimize find_next_bit()

RFC PATCH In review Peter Lieven 2 participants 2 messages Mar 12, 2013

lore
Share & tools
lore
#0 lore raw

RFC PATCH 7/9 bitops: use vector algorithm to optimize find_next_bit()

this patch adds the usage of buffer_find_nonzero_offset() to skip large areas of zeroes.

compared to loop unrolling this adds another 50% performance benefit for skipping large areas of zeroes.

---
 util/bitops.c |   23 ++++++++++++++++++++---
 1 file changed, 20 insertions(+), 3 deletions(-)
util/bitops.c +20 -3
index e72237a..0a056ff 100644
@@ -42,10 +42,27 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
         size -= BITS_PER_LONG;
         result += BITS_PER_LONG;
     }
-    while (size & ~(BITS_PER_LONG-1)) {
-        if ((tmp = *(p++))) {
-            goto found_middle;
+    while (size >= BITS_PER_LONG) {
+        if ((tmp = *p)) {
+             goto found_middle;
+         }
+        if (((uintptr_t) p) % sizeof(VECTYPE) == 0
+              && size >= BITS_PER_BYTE*8*sizeof(VECTYPE)) {
+          unsigned long tmp2 =
+              buffer_find_nonzero_offset(p, ((size/BITS_PER_BYTE) & ~(8*sizeof(VECTYPE)-1)));
+          result += tmp2 * BITS_PER_BYTE;
+          size -= tmp2 * BITS_PER_BYTE;
+          p += tmp2 / sizeof(unsigned long);
+          if (!size) {
+              return result;
+          }
+          if (tmp2) {
+             if ((tmp = *p)) {
+                 goto found_middle;
+             }
+          }
         }
+        p++;
         result += BITS_PER_LONG;
         size -= BITS_PER_LONG;
     }
Signature · 1 line
1.7.9.5
#1 lore raw

util/bitops.c unsigned long find_next_bit(const unsigned long *addr, unsigned long size, · line 50

Quoted 13 lines · Peter Lieven

this patch adds the usage of buffer_find_nonzero_offset() to skip large areas of zeroes.

compared to loop unrolling this adds another 50% performance benefit for skipping large areas of zeroes.

---
 util/bitops.c |   23 ++++++++++++++++++++---
 1 file changed, 20 insertions(+), 3 deletions(-)
util/bitops.c +2 -0
+        if (((uintptr_t) p) % sizeof(VECTYPE) == 0
+              && size >= BITS_PER_BYTE*8*sizeof(VECTYPE)) {

Spaces around binary operators. CHAR_BITS instead of magic 8.

Quoted 3 lines
(quoted diff) +2 -0
+          unsigned long tmp2 =
+              buffer_find_nonzero_offset(p, ((size/BITS_PER_BYTE) &

~(8*sizeof(VECTYPE)-1)));

Spaces around binary operators.

Signature · 2 lines
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org