bitops: use vector algorithm to optimize find_next_bit()
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.
Signed-off-by Peter Lieven <[email protected]>
--- util/bitops.c | 23 ++++++++++++++++++++--- 1 file changed, 20 insertions(+), 3 deletions(-)
util/bitops.c +20 -3
@@ -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
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.
Signed-off-by Peter Lieven <[email protected]>--- 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