[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [RFC][PATCH 7/9] bitops: use vector algorithm to optimize f
From: |
Peter Lieven |
Subject: |
[Qemu-devel] [RFC][PATCH 7/9] bitops: use vector algorithm to optimize find_next_bit() |
Date: |
Tue, 12 Mar 2013 16:52:46 +0100 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130221 Thunderbird/17.0.3 |
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 <address@hidden>
---
util/bitops.c | 23 ++++++++++++++++++++---
1 file changed, 20 insertions(+), 3 deletions(-)
diff --git a/util/bitops.c b/util/bitops.c
index e72237a..0a056ff 100644
--- a/util/bitops.c
+++ b/util/bitops.c
@@ -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;
}
--
1.7.9.5
- [Qemu-devel] [RFC][PATCH 7/9] bitops: use vector algorithm to optimize find_next_bit(),
Peter Lieven <=