Skip to contentSkip to conversation

find_next_bit optimizations

RFC In review Peter Lieven 5 participants 22 messages Mar 11, 2013 – Mar 12, 2013

lore
Share & tools
lore
#0 lore raw

RFC 1/1 find_next_bit optimizations

Hi,

I ever since had a few VMs which are very hard to migrate because of a lot of memory I/O. I found that finding the next dirty bit seemed to be one of the culprits (apart from removing locking which Paolo is working on).

I have to following proposal which seems to help a lot in my case. Just wanted to have some feedback. I applied the same unrolling idea like in buffer_is_zero().

Peter

util/bitops.c +14 -1
@@ -24,12 +24,13 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
     const unsigned long *p = addr + BITOP_WORD(offset);
     unsigned long result = offset & ~(BITS_PER_LONG-1);
     unsigned long tmp;
+    unsigned long d0,d1,d2,d3;
 
     if (offset >= size) {
         return size;
     }
     size -= result;
-    offset %= BITS_PER_LONG;
+    offset &= (BITS_PER_LONG-1);
     if (offset) {
         tmp = *(p++);
         tmp &= (~0UL << offset);
@@ -43,6 +44,18 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
         result += BITS_PER_LONG;
     }
     while (size & ~(BITS_PER_LONG-1)) {
+        while (!(size & (4*BITS_PER_LONG-1))) {
+            d0 = *p;
+            d1 = *(p+1);
+            d2 = *(p+2);
+            d3 = *(p+3);
+            if (d0 || d1 || d2 || d3) {
+                break;
+            }
+            p+=4;
+            result += 4*BITS_PER_LONG;
+            size -= 4*BITS_PER_LONG;
+        }
         if ((tmp = *(p++))) {
             goto found_middle;
         }
#1 lore raw

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

Quoted 13 lines · Peter Lieven
util/bitops.c +2 -1
@@ -24,12 +24,13 @@ unsigned long find_next_bit(const unsigned long *addr,
 unsigned long size,
     const unsigned long *p = addr + BITOP_WORD(offset);
     unsigned long result = offset & ~(BITS_PER_LONG-1);
     unsigned long tmp;
+    unsigned long d0,d1,d2,d3;
 
     if (offset >= size) {
         return size;
     }
     size -= result;
-    offset %= BITS_PER_LONG;
+    offset &= (BITS_PER_LONG-1);

This change at least is unnecessary -- I just checked, and gcc is already smart enough to turn the % operation into a logical and. The generated object files are identical.

-- PMM

#2 lore raw
In reply to Peter Lieven

Il 11/03/2013 14:44, Peter Lieven ha scritto:

Quoted 32 lines

Hi,

I ever since had a few VMs which are very hard to migrate because of a lot of memory I/O. I found that finding the next dirty bit seemed to be one of the culprits (apart from removing locking which Paolo is working on).

I have to following proposal which seems to help a lot in my case. Just wanted to have some feedback.
I applied the same unrolling idea like in buffer_is_zero().

Peter

util/bitops.c +2 -1
@@ -24,12 +24,13 @@ unsigned long find_next_bit(const unsigned long
 *addr, unsigned long size,
     const unsigned long *p = addr + BITOP_WORD(offset);
     unsigned long result = offset & ~(BITS_PER_LONG-1);
     unsigned long tmp;
+    unsigned long d0,d1,d2,d3;
 
     if (offset >= size) {
         return size;
     }
     size -= result;
-    offset %= BITS_PER_LONG;
+    offset &= (BITS_PER_LONG-1);
     if (offset) {
         tmp = *(p++);
         tmp &= (~0UL << offset);

util/bitops.c unsigned long find_next_bit(const unsigned long · line 48

Quoted 5 lines
util/bitops.c +1 -0
@@ -43,6 +44,18 @@ unsigned long find_next_bit(const unsigned long
 *addr, unsigned long size,
         result += BITS_PER_LONG;
     }
     while (size & ~(BITS_PER_LONG-1)) {
+        while (!(size & (4*BITS_PER_LONG-1))) {

This really means

       if (!(size & (4*BITS_PER_LONG-1))) {
           while (1) {
               ...
           }
       }

because the subtraction will not change the result of the "while" loop condition.

What you want is probably "while (size & ~(4*BITS_PER_LONG-1))", which in turn means "while (size >= 4*BITS_PER_LONG).

Please change both while loops to use a ">=" condition, it's easier to read.

Paolo

Quoted 14 lines
util/bitops.c +11 -0
+            d0 = *p;
+            d1 = *(p+1);
+            d2 = *(p+2);
+            d3 = *(p+3);
+            if (d0 || d1 || d2 || d3) {
+                break;
+            }
+            p+=4;
+            result += 4*BITS_PER_LONG;
+            size -= 4*BITS_PER_LONG;
+        }
         if ((tmp = *(p++))) {
             goto found_middle;
         }
#3 lore raw

Am 11.03.2013 um 15:14 schrieb Paolo Bonzini <[email protected]>:

Quoted 41 lines

Il 11/03/2013 14:44, Peter Lieven ha scritto:

Quoted 32 lines

Hi,

I ever since had a few VMs which are very hard to migrate because of a lot of memory I/O. I found that finding the next dirty bit seemed to be one of the culprits (apart from removing locking which Paolo is working on).

I have to following proposal which seems to help a lot in my case. Just wanted to have some feedback.
I applied the same unrolling idea like in buffer_is_zero().

Peter

util/bitops.c +2 -1
@@ -24,12 +24,13 @@ unsigned long find_next_bit(const unsigned long
 *addr, unsigned long size,
    const unsigned long *p = addr + BITOP_WORD(offset);
    unsigned long result = offset & ~(BITS_PER_LONG-1);
    unsigned long tmp;
+    unsigned long d0,d1,d2,d3;
 
    if (offset >= size) {
        return size;
    }
    size -= result;
-    offset %= BITS_PER_LONG;
+    offset &= (BITS_PER_LONG-1);
    if (offset) {
        tmp = *(p++);
        tmp &= (~0UL << offset);

util/bitops.c unsigned long find_next_bit(const unsigned long · line 48

Quoted 5 lines
util/bitops.c +1 -0
@@ -43,6 +44,18 @@ unsigned long find_next_bit(const unsigned long
 *addr, unsigned long size,
        result += BITS_PER_LONG;
    }
    while (size & ~(BITS_PER_LONG-1)) {
+        while (!(size & (4*BITS_PER_LONG-1))) {

This really means

Quoted 8 lines
      if (!(size & (4*BITS_PER_LONG-1))) {
          while (1) {
              ...
          }
      }

because the subtraction will not change the result of the "while" loop condition.

Are you sure? The above is working nicely for me (wondering why ;-)) I think !(size & (4*BITS_PER_LONG-1)) is the same as what you propose. If size & (4*BITS_PER_LONG-1) is not zero its not dividable by 4*BITS_PER_LONG. But it see it might be a problem for size == 0.

Quoted 5 lines

What you want is probably "while (size & ~(4*BITS_PER_LONG-1))", which in turn means "while (size >= 4*BITS_PER_LONG).

Please change both while loops to use a ">=" condition, it's easier to read.

Good idea, its easier to understand.

Has anyone evidence if unrolling 4 longs is optimal on today processors? I just chooses 4 longs because it was the same in buffer_is_zero.

Peter

Quoted 18 lines

Paolo

Quoted 14 lines
util/bitops.c +11 -0
+            d0 = *p;
+            d1 = *(p+1);
+            d2 = *(p+2);
+            d3 = *(p+3);
+            if (d0 || d1 || d2 || d3) {
+                break;
+            }
+            p+=4;
+            result += 4*BITS_PER_LONG;
+            size -= 4*BITS_PER_LONG;
+        }
        if ((tmp = *(p++))) {
            goto found_middle;
        }
#4 lore raw

Am 11.03.2013 um 15:22 schrieb Peter Lieven <[email protected]>:

Quoted 50 lines

Am 11.03.2013 um 15:14 schrieb Paolo Bonzini <[email protected]>:

Quoted 47 lines

Il 11/03/2013 14:44, Peter Lieven ha scritto:

Quoted 32 lines

Hi,

I ever since had a few VMs which are very hard to migrate because of a lot of memory I/O. I found that finding the next dirty bit seemed to be one of the culprits (apart from removing locking which Paolo is working on).

I have to following proposal which seems to help a lot in my case. Just wanted to have some feedback.
I applied the same unrolling idea like in buffer_is_zero().

Peter

util/bitops.c +2 -1
@@ -24,12 +24,13 @@ unsigned long find_next_bit(const unsigned long
 *addr, unsigned long size,
   const unsigned long *p = addr + BITOP_WORD(offset);
   unsigned long result = offset & ~(BITS_PER_LONG-1);
   unsigned long tmp;
+    unsigned long d0,d1,d2,d3;
 
   if (offset >= size) {
       return size;
   }
   size -= result;
-    offset %= BITS_PER_LONG;
+    offset &= (BITS_PER_LONG-1);
   if (offset) {
       tmp = *(p++);
       tmp &= (~0UL << offset);

util/bitops.c unsigned long find_next_bit(const unsigned long · line 48

Quoted 5 lines
util/bitops.c +1 -0
@@ -43,6 +44,18 @@ unsigned long find_next_bit(const unsigned long
 *addr, unsigned long size,
       result += BITS_PER_LONG;
   }
   while (size & ~(BITS_PER_LONG-1)) {
+        while (!(size & (4*BITS_PER_LONG-1))) {

This really means

     if (!(size & (4*BITS_PER_LONG-1))) {
         while (1) {
             ...
         }
     }
Quoted 13 lines
Quoted 2 lines

because the subtraction will not change the result of the "while" loop condition.

Are you sure? The above is working nicely for me (wondering why ;-)) I think !(size & (4*BITS_PER_LONG-1)) is the same as what you propose. If size & (4*BITS_PER_LONG-1) is not zero its not dividable by 4*BITS_PER_LONG. But it see it might be a problem for size == 0.

Quoted 5 lines

What you want is probably "while (size & ~(4*BITS_PER_LONG-1))", which in turn means "while (size >= 4*BITS_PER_LONG).

Please change both while loops to use a ">=" condition, it's easier to read.

Thinking again, in case a bit is found, this might lead to unnecessary iterations in the while loop if the bit is in d1, d2 or d3.

Quoted 27 lines

Good idea, its easier to understand.

Has anyone evidence if unrolling 4 longs is optimal on today processors? I just chooses 4 longs because it was the same in buffer_is_zero.

Peter

Quoted 18 lines

Paolo

Quoted 14 lines
util/bitops.c +11 -0
+            d0 = *p;
+            d1 = *(p+1);
+            d2 = *(p+2);
+            d3 = *(p+3);
+            if (d0 || d1 || d2 || d3) {
+                break;
+            }
+            p+=4;
+            result += 4*BITS_PER_LONG;
+            size -= 4*BITS_PER_LONG;
+        }
       if ((tmp = *(p++))) {
           goto found_middle;
       }
#5 lore raw
In reply to Peter Lieven

Il 11/03/2013 15:22, Peter Lieven ha scritto:

Quoted 50 lines

Am 11.03.2013 um 15:14 schrieb Paolo Bonzini <[email protected]>:

Quoted 47 lines

Il 11/03/2013 14:44, Peter Lieven ha scritto:

Quoted 32 lines

Hi,

I ever since had a few VMs which are very hard to migrate because of a lot of memory I/O. I found that finding the next dirty bit seemed to be one of the culprits (apart from removing locking which Paolo is working on).

I have to following proposal which seems to help a lot in my case. Just wanted to have some feedback.
I applied the same unrolling idea like in buffer_is_zero().

Peter

util/bitops.c +2 -1
@@ -24,12 +24,13 @@ unsigned long find_next_bit(const unsigned long
 *addr, unsigned long size,
    const unsigned long *p = addr + BITOP_WORD(offset);
    unsigned long result = offset & ~(BITS_PER_LONG-1);
    unsigned long tmp;
+    unsigned long d0,d1,d2,d3;
 
    if (offset >= size) {
        return size;
    }
    size -= result;
-    offset %= BITS_PER_LONG;
+    offset &= (BITS_PER_LONG-1);
    if (offset) {
        tmp = *(p++);
        tmp &= (~0UL << offset);

util/bitops.c unsigned long find_next_bit(const unsigned long · line 48

Quoted 5 lines
util/bitops.c +1 -0
@@ -43,6 +44,18 @@ unsigned long find_next_bit(const unsigned long
 *addr, unsigned long size,
        result += BITS_PER_LONG;
    }
    while (size & ~(BITS_PER_LONG-1)) {
+        while (!(size & (4*BITS_PER_LONG-1))) {

This really means

      if (!(size & (4*BITS_PER_LONG-1))) {
          while (1) {
              ...
          }
      }
Quoted 4 lines
Quoted 2 lines

because the subtraction will not change the result of the "while" loop condition.

Are you sure? The above is working nicely for me (wondering why ;-))

while (!(size & (4*BITS_PER_LONG-1))) =>
while (!(size % (4*BITS_PER_LONG)) =>
while ((size % (4*BITS_PER_LONG)) == 0)

Subtracting 4*BITS_PER_LONG doesn't change the modulus.

Quoted 3 lines

I think !(size & (4*BITS_PER_LONG-1)) is the same as what you propose. If size & (4*BITS_PER_LONG-1) is not zero its not dividable by 4*BITS_PER_LONG. But it see it might be a problem for size == 0.

In fact I'm not really sure why it works for you. :)

Quoted 11 lines
Quoted 4 lines

What you want is probably "while (size & ~(4*BITS_PER_LONG-1))", which in turn means "while (size >= 4*BITS_PER_LONG).

Please change both while loops to use a ">=" condition, it's easier to read.

Good idea, its easier to understand.

Quoted 1 line
Quoted 1 line

Please change both while loops to use a ">=" condition, it's easier to read.

Thinking again, in case a bit is found, this might lead to unnecessary iterations in the while loop if the bit is in d1, d2 or d3.

How would that be different in your patch? But you can solve it by making two >= loops, one checking for 4*BITS_PER_LONG and one checking BITS_PER_LONG.

Paolo

Quoted 22 lines

Peter

Quoted 18 lines

Paolo

Quoted 14 lines
util/bitops.c +11 -0
+            d0 = *p;
+            d1 = *(p+1);
+            d2 = *(p+2);
+            d3 = *(p+3);
+            if (d0 || d1 || d2 || d3) {
+                break;
+            }
+            p+=4;
+            result += 4*BITS_PER_LONG;
+            size -= 4*BITS_PER_LONG;
+        }
        if ((tmp = *(p++))) {
            goto found_middle;
        }
#6 lore raw
Quoted 4 lines

How would that be different in your patch? But you can solve it by making two >= loops, one checking for 4*BITS_PER_LONG and one checking BITS_PER_LONG.

This is what I have now:

util/bitops.c +15 -2
index e72237a..b0dc93f 100644
@@ -24,12 +24,13 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
     const unsigned long *p = addr + BITOP_WORD(offset);
     unsigned long result = offset & ~(BITS_PER_LONG-1);
     unsigned long tmp;
+    unsigned long d0,d1,d2,d3;
 
     if (offset >= size) {
         return size;
     }
     size -= result;
-    offset %= BITS_PER_LONG;
+    offset &= (BITS_PER_LONG-1);
     if (offset) {
         tmp = *(p++);
         tmp &= (~0UL << offset);
@@ -42,7 +43,19 @@ 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)) {
+    while (size >= 4*BITS_PER_LONG) {
+        d0 = *p;
+        d1 = *(p+1);
+        d2 = *(p+2);
+        d3 = *(p+3);
+        if (d0 || d1 || d2 || d3) {
+            break;
+        }
+        p+=4;
+        result += 4*BITS_PER_LONG;
+        size -= 4*BITS_PER_LONG;
+    }
+    while (size >= BITS_PER_LONG) {
         if ((tmp = *(p++))) {
             goto found_middle;
         }
Reviewed-by
#7 lore raw

Il 11/03/2013 16:24, Peter Lieven ha scritto:

Quoted 38 lines
Quoted 4 lines

How would that be different in your patch? But you can solve it by making two >= loops, one checking for 4*BITS_PER_LONG and one checking BITS_PER_LONG.

This is what I have now:

util/bitops.c +8 -2
index e72237a..b0dc93f 100644
@@ -24,12 +24,13 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
     const unsigned long *p = addr + BITOP_WORD(offset);
     unsigned long result = offset & ~(BITS_PER_LONG-1);
     unsigned long tmp;
+    unsigned long d0,d1,d2,d3;
 
     if (offset >= size) {
         return size;
     }
     size -= result;
-    offset %= BITS_PER_LONG;
+    offset &= (BITS_PER_LONG-1);
     if (offset) {
         tmp = *(p++);
         tmp &= (~0UL << offset);
@@ -42,7 +43,19 @@ 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)) {
+    while (size >= 4*BITS_PER_LONG) {
+        d0 = *p;
+        d1 = *(p+1);
+        d2 = *(p+2);
+        d3 = *(p+3);
+        if (d0 || d1 || d2 || d3) {

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

Quoted 10 lines
util/bitops.c +7 -0
+            break;
+        }
+        p+=4;
+        result += 4*BITS_PER_LONG;
+        size -= 4*BITS_PER_LONG;
+    }
+    while (size >= BITS_PER_LONG) {
         if ((tmp = *(p++))) {
             goto found_middle;
         }

Minus the %= vs. &=,

Perhaps:

        tmp = *p;
        d1 = *(p+1);
        d2 = *(p+2);
        d3 = *(p+3);
        if (tmp) {
            goto found_middle;
        }
        if (d1 || d2 || d3) {
            break;
        }

Paolo

#8 lore raw

Am 11.03.2013 um 16:29 schrieb Paolo Bonzini <[email protected]>:

Quoted 56 lines

Il 11/03/2013 16:24, Peter Lieven ha scritto:

Quoted 38 lines
Quoted 4 lines

How would that be different in your patch? But you can solve it by making two >= loops, one checking for 4*BITS_PER_LONG and one checking BITS_PER_LONG.

This is what I have now:

util/bitops.c +8 -2
index e72237a..b0dc93f 100644
@@ -24,12 +24,13 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
    const unsigned long *p = addr + BITOP_WORD(offset);
    unsigned long result = offset & ~(BITS_PER_LONG-1);
    unsigned long tmp;
+    unsigned long d0,d1,d2,d3;
 
    if (offset >= size) {
        return size;
    }
    size -= result;
-    offset %= BITS_PER_LONG;
+    offset &= (BITS_PER_LONG-1);
    if (offset) {
        tmp = *(p++);
        tmp &= (~0UL << offset);
@@ -42,7 +43,19 @@ 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)) {
+    while (size >= 4*BITS_PER_LONG) {
+        d0 = *p;
+        d1 = *(p+1);
+        d2 = *(p+2);
+        d3 = *(p+3);
+        if (d0 || d1 || d2 || d3) {

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

Quoted 10 lines
util/bitops.c +7 -0
+            break;
+        }
+        p+=4;
+        result += 4*BITS_PER_LONG;
+        size -= 4*BITS_PER_LONG;
+    }
+    while (size >= BITS_PER_LONG) {
        if ((tmp = *(p++))) {
            goto found_middle;
        }

Minus the %= vs. &=,

Perhaps:

Quoted 10 lines
       tmp = *p;
       d1 = *(p+1);
       d2 = *(p+2);
       d3 = *(p+3);
       if (tmp) {
           goto found_middle;
       }
       if (d1 || d2 || d3) {
           break;
       }

i do not know what gcc interally makes of the d0 || d1 || d2 || d3 ? i would guess its sth like one addition w/ carry and 1 test?

your proposed change would introduce 2 tests (maybe)?

what about this to be sure?

       tmp = *p;
       d1 = *(p+1);
       d2 = *(p+2);
       d3 = *(p+3);
       if (tmp || d1 || d2 || d3) {
           if (tmp) {
               goto found_middle;
           }
           break;
       }

Peter

#9 lore raw

Il 11/03/2013 16:37, Peter Lieven ha scritto:

Quoted 70 lines

Am 11.03.2013 um 16:29 schrieb Paolo Bonzini <[email protected]>:

Quoted 56 lines

Il 11/03/2013 16:24, Peter Lieven ha scritto:

Quoted 38 lines
Quoted 4 lines

How would that be different in your patch? But you can solve it by making two >= loops, one checking for 4*BITS_PER_LONG and one checking BITS_PER_LONG.

This is what I have now:

util/bitops.c +8 -2
index e72237a..b0dc93f 100644
@@ -24,12 +24,13 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
    const unsigned long *p = addr + BITOP_WORD(offset);
    unsigned long result = offset & ~(BITS_PER_LONG-1);
    unsigned long tmp;
+    unsigned long d0,d1,d2,d3;
 
    if (offset >= size) {
        return size;
    }
    size -= result;
-    offset %= BITS_PER_LONG;
+    offset &= (BITS_PER_LONG-1);
    if (offset) {
        tmp = *(p++);
        tmp &= (~0UL << offset);
@@ -42,7 +43,19 @@ 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)) {
+    while (size >= 4*BITS_PER_LONG) {
+        d0 = *p;
+        d1 = *(p+1);
+        d2 = *(p+2);
+        d3 = *(p+3);
+        if (d0 || d1 || d2 || d3) {

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

Quoted 10 lines
util/bitops.c +7 -0
+            break;
+        }
+        p+=4;
+        result += 4*BITS_PER_LONG;
+        size -= 4*BITS_PER_LONG;
+    }
+    while (size >= BITS_PER_LONG) {
        if ((tmp = *(p++))) {
            goto found_middle;
        }

Minus the %= vs. &=,

Perhaps:

Quoted 10 lines
       tmp = *p;
       d1 = *(p+1);
       d2 = *(p+2);
       d3 = *(p+3);
       if (tmp) {
           goto found_middle;
       }
       if (d1 || d2 || d3) {
           break;
       }
Quoted 1 line

i do not know what gcc interally makes of the d0 || d1 || d2 || d3 ?

It depends on the target and how expensive branches are.

Quoted 1 line

i would guess its sth like one addition w/ carry and 1 test?

It could be either 4 compare-and-jump sequences, or 3 bitwise ORs followed by a compare-and-jump.

That is, either:

     test %r8, %r8
     jz   second_loop
     test %r9, %r9
     jz   second_loop
     test %r10, %r10
     jz   second_loop
     test %r11, %r11
     jz   second_loop

or

     or %r9, %r8
     or %r11, %r10
     or %r8, %r10
     jz   second_loop

Don't let the length of the code fool you. The processor knows how to optimize all of these, and GCC knows too.

Quoted 1 line

your proposed change would introduce 2 tests (maybe)?

Yes, but I expect they to be fairly well predicted.

Quoted 9 lines

what about this to be sure?

       tmp = *p;
       d1 = *(p+1);
       d2 = *(p+2);
       d3 = *(p+3);
       if (tmp || d1 || d2 || d3) {
           if (tmp) {
               goto found_middle;

I suspect that GCC would rewrite it my version (definitely if it produces 4 compare-and-jumps; but possibly it does it even if it goes for bitwise ORs, I haven't checked.

Regarding your other question ("one last thought. would it make sense to update only sizein the while loops and compute the result at the end as orgsize - size?"), again the compiler knows better and might even do this for you. It will likely drop the p increases and use p[result], so if you do that change you may even get the same code, only this time p is increased and you get an extra subtraction at the end. :)

Bottom line: don't try to outsmart an optimizing C compiler on micro-optimization, unless you have benchmarked it and it shows there is a problem.

Paolo

Quoted 6 lines
           }
           break;
       }

Peter

#10 lore raw

Even more efficient might be to do bitwise instead of logical or

Quoted 1 line
       if (tmp | d1 | d2 | d3) {

that should remove 3 of the 4 conditional jumps and should become 3 bitwise ors and one conditional jump

Quoted 140 lines · Paolo Bonzini

Il 11/03/2013 16:37, Peter Lieven ha scritto:

Quoted 70 lines

Am 11.03.2013 um 16:29 schrieb Paolo Bonzini <[email protected]>:

Quoted 56 lines

Il 11/03/2013 16:24, Peter Lieven ha scritto:

Quoted 38 lines
Quoted 4 lines

How would that be different in your patch? But you can solve it by making two >= loops, one checking for 4*BITS_PER_LONG and one checking BITS_PER_LONG.

This is what I have now:

util/bitops.c +8 -2
index e72237a..b0dc93f 100644
@@ -24,12 +24,13 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
    const unsigned long *p = addr + BITOP_WORD(offset);
    unsigned long result = offset & ~(BITS_PER_LONG-1);
    unsigned long tmp;
+    unsigned long d0,d1,d2,d3;
 
    if (offset >= size) {
        return size;
    }
    size -= result;
-    offset %= BITS_PER_LONG;
+    offset &= (BITS_PER_LONG-1);
    if (offset) {
        tmp = *(p++);
        tmp &= (~0UL << offset);
@@ -42,7 +43,19 @@ 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)) {
+    while (size >= 4*BITS_PER_LONG) {
+        d0 = *p;
+        d1 = *(p+1);
+        d2 = *(p+2);
+        d3 = *(p+3);
+        if (d0 || d1 || d2 || d3) {

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

Quoted 10 lines
util/bitops.c +7 -0
+            break;
+        }
+        p+=4;
+        result += 4*BITS_PER_LONG;
+        size -= 4*BITS_PER_LONG;
+    }
+    while (size >= BITS_PER_LONG) {
        if ((tmp = *(p++))) {
            goto found_middle;
        }

Minus the %= vs. &=,

Perhaps:

Quoted 10 lines
       tmp = *p;
       d1 = *(p+1);
       d2 = *(p+2);
       d3 = *(p+3);
       if (tmp) {
           goto found_middle;
       }
       if (d1 || d2 || d3) {
           break;
       }
Quoted 1 line

i do not know what gcc interally makes of the d0 || d1 || d2 || d3 ?

It depends on the target and how expensive branches are.

Quoted 1 line

i would guess its sth like one addition w/ carry and 1 test?

It could be either 4 compare-and-jump sequences, or 3 bitwise ORs followed by a compare-and-jump.

That is, either:

     test %r8, %r8
     jz   second_loop
     test %r9, %r9
     jz   second_loop
     test %r10, %r10
     jz   second_loop
     test %r11, %r11
     jz   second_loop

or

     or %r9, %r8
     or %r11, %r10
     or %r8, %r10
     jz   second_loop

Don't let the length of the code fool you. The processor knows how to optimize all of these, and GCC knows too.

Quoted 1 line

your proposed change would introduce 2 tests (maybe)?

Yes, but I expect they to be fairly well predicted.

Quoted 9 lines

what about this to be sure?

       tmp = *p;
       d1 = *(p+1);
       d2 = *(p+2);
       d3 = *(p+3);
       if (tmp || d1 || d2 || d3) {
           if (tmp) {
               goto found_middle;

I suspect that GCC would rewrite it my version (definitely if it produces 4 compare-and-jumps; but possibly it does it even if it goes for bitwise ORs, I haven't checked.

Regarding your other question ("one last thought. would it make sense to update only sizein the while loops and compute the result at the end as orgsize - size?"), again the compiler knows better and might even do this for you. It will likely drop the p increases and use p[result], so if you do that change you may even get the same code, only this time p is increased and you get an extra subtraction at the end. :)

Bottom line: don't try to outsmart an optimizing C compiler on micro-optimization, unless you have benchmarked it and it shows there is a problem.

Paolo

Quoted 6 lines
           }
           break;
       }

Peter

#11 lore raw

Il 11/03/2013 18:06, ronnie sahlberg ha scritto:

Quoted 5 lines

Even more efficient might be to do bitwise instead of logical or

Quoted 1 line
Quoted 1 line
       if (tmp | d1 | d2 | d3) {

that should remove 3 of the 4 conditional jumps and should become 3 bitwise ors and one conditional jump

Without any serious profiling, please let the compiler do that.

Paolo

#12 lore raw

Am 11.03.2013 18:07, schrieb Paolo Bonzini:

Quoted 8 lines

Il 11/03/2013 18:06, ronnie sahlberg ha scritto:

Quoted 5 lines

Even more efficient might be to do bitwise instead of logical or

Quoted 1 line
Quoted 1 line
       if (tmp | d1 | d2 | d3) {

that should remove 3 of the 4 conditional jumps and should become 3 bitwise ors and one conditional jump

Without any serious profiling, please let the compiler do that.

Paolo is right, i ran some tests with gcc 4.6.3 on x86_64 (with -O3) and tried the various ideas. They all made no significant difference. Even unrolling to 8 unsigned longs didn't change anything.

What I tried is running 1^20 interations of find_next_bit(bitfield,4194304,0); I choosed the bitfield to be 4MByte which equals a 16GB VM. The bitfield was complete zeroed so find_next_bit had to run completely through the bitfield.

The original version took 1 minute and 10 seconds whereas all other took approx. 37-38 seconds which is almost a 100% boost ;-)

So I think this here is the final version:

    while (size >= 4*BITS_PER_LONG) {
        unsigned long d1, d2, d3;
        tmp = *p;
        d1 = *(p+1);
        d2 = *(p+2);
        d3 = *(p+3);
        if (tmp) {
            goto found_middle;
        }        
        if (d1 || d2 || d3) {
            break;
        }
        p += 4;
        result += 4*BITS_PER_LONG;
        size -= 4*BITS_PER_LONG;
    }

Peter

#13 lore raw

PATCH 1/1 bitops: unroll while loop in find_next_bit().

In reply to Paolo Bonzini

this patch adopts the loop unrolling idea of bitmap_is_zero() to speed up the skipping of large areas with zeros in find_next_bit().

this routine is extensively used to find dirty pages in live migration.

testing only the find_next_bit performance on a zeroed bitfield the loop onrolling decreased executing time by approx. 50% on x86_64.

---
 util/bitops.c |   18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)
util/bitops.c +17 -1
index e72237a..227c38b 100644
@@ -42,7 +42,23 @@ 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)) {
+    while (size >= 4*BITS_PER_LONG) {
+        unsigned long d1, d2, d3;
+        tmp = *p;
+        d1 = *(p+1);
+        d2 = *(p+2);
+        d3 = *(p+3);
+        if (tmp) {
+            goto found_middle;
+        }
+        if (d1 | d2 | d3) {
+            break;
+        }
+        p += 4;
+        result += 4*BITS_PER_LONG;
+        size -= 4*BITS_PER_LONG;
+    }
+    while (size >= BITS_PER_LONG) {
         if ((tmp = *(p++))) {
             goto found_middle;
         }
Signature · 1 line
1.7.9.5
#14 lore raw
In reply to Peter Lieven

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

Quoted 2 lines · Peter Lieven
util/bitops.c +1 -1
-    offset %= BITS_PER_LONG;
+    offset &= (BITS_PER_LONG-1);

Still pointless.

-- PMM

#15 lore raw
In reply to Peter Lieven
Quoted 1 line · Peter Lieven

+ unsigned long d0,d1,d2,d3;

These commas should have spaces after them. Also, since the variables are only used inside the scope of your newly added while loop:

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

Quoted 2 lines
util/bitops.c +1 -1
-    while (size & ~(BITS_PER_LONG-1)) {
+    while (size >= 4*BITS_PER_LONG) {

it would be better to declare them here.

Quoted 5 lines
util/bitops.c +5 -0
+        d0 = *p;
+        d1 = *(p+1);
+        d2 = *(p+2);
+        d3 = *(p+3);
+        if (d0 || d1 || d2 || d3) {

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

Quoted 10 lines
util/bitops.c +7 -0
+            break;
+        }
+        p+=4;
+        result += 4*BITS_PER_LONG;
+        size -= 4*BITS_PER_LONG;
+    }
+    while (size >= BITS_PER_LONG) {
         if ((tmp = *(p++))) {
             goto found_middle;
         }

thanks
-- PMM

#16 lore raw

Am 11.03.2013 um 16:37 schrieb Peter Maydell <[email protected]>:

Quoted 11 lines · Peter Lieven
Quoted 1 line

+ unsigned long d0,d1,d2,d3;

These commas should have spaces after them. Also, since the variables are only used inside the scope of your newly added while loop:

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

Quoted 2 lines
util/bitops.c +1 -1
-    while (size & ~(BITS_PER_LONG-1)) {
+    while (size >= 4*BITS_PER_LONG) {

it would be better to declare them here.

can you verify if this does not make difference in the generated object code? in buffer_is_zero() its outside the loop.

thanks
peter

#17 lore raw

Il 11/03/2013 16:41, Peter Lieven ha scritto:

Quoted 2 lines

can you verify if this does not make difference in the generated object code? in buffer_is_zero() its outside the loop.

No, it doesn't.

Paolo

#18 lore raw

Am 11.03.2013 um 16:42 schrieb Paolo Bonzini <[email protected]>:

Quoted 5 lines

Il 11/03/2013 16:41, Peter Lieven ha scritto:

Quoted 2 lines

can you verify if this does not make difference in the generated object code? in buffer_is_zero() its outside the loop.

No, it doesn't.

ok, i will sent the final patch tomorrow.

one last thought. would it make sense to update only sizein the while loops and compute the result at the end as orgsize - size?

Peter

#19 lore raw
In reply to Peter Lieven
Quoted 4 lines · Peter Lieven

I ever since had a few VMs which are very hard to migrate because of a lot of memory I/O. I found that finding the next dirty bit seemed to be one of the culprits (apart from removing locking which Paolo is working on).

I have to following proposal which seems to help a lot in my case. Just wanted to have some feedback.

Hi Peter,
Do you have any performance numbers for this patch? I'm just curious how big the win is.

Stefan

#20 lore raw

Am 12.03.2013 um 09:35 schrieb Stefan Hajnoczi <[email protected]>:

Quoted 9 lines · Peter Lieven
Quoted 4 lines

I ever since had a few VMs which are very hard to migrate because of a lot of memory I/O. I found that finding the next dirty bit seemed to be one of the culprits (apart from removing locking which Paolo is working on).

I have to following proposal which seems to help a lot in my case. Just wanted to have some feedback.

Hi Peter,
Do you have any performance numbers for this patch? I'm just curious how big the win is.

Hi Stefan,

please see my recent email to the list with the final patch. The win is up to 100%. Worst case execution time (whole array is zero) is halved on x86_64.

Peter

Quoted 2 lines

Stefan

#21 lore raw
Quoted 13 lines · Peter Lieven

Am 12.03.2013 um 09:35 schrieb Stefan Hajnoczi <[email protected]>:

Quoted 9 lines · Peter Lieven
Quoted 4 lines

I ever since had a few VMs which are very hard to migrate because of a lot of memory I/O. I found that finding the next dirty bit seemed to be one of the culprits (apart from removing locking which Paolo is working on).

I have to following proposal which seems to help a lot in my case. Just wanted to have some feedback.

Hi Peter,
Do you have any performance numbers for this patch? I'm just curious how big the win is.

Quoted 5 lines

Hi Stefan,

please see my recent email to the list with the final patch. The win is up to 100%. Worst case execution time (whole array is zero) is halved on x86_64.

Thanks!

Stefan