summaryrefslogtreecommitdiffstats
path: root/contrib/timer-wheel/find_last_bit.c
diff options
context:
space:
mode:
authorKaleb S. KEITHLEY <kkeithle@redhat.com>2017-04-30 18:59:17 -0400
committerJeff Darcy <jeff@pl.atyp.us>2017-05-01 16:05:56 +0000
commitc92b8347aea8ce78ca3fbc49b88f5adadc98509b (patch)
tree369257973535e6252e1378852f6aca7b31a6ce69 /contrib/timer-wheel/find_last_bit.c
parent73fcf3a874b2049da31d01b8363d1ac85c9488c2 (diff)
contrib/timerwheel: probable bug on 32-bit, use __builtin_ffs()
Simply always defining BITS_PER_LONG as 64 seems like it's almost certainly wrong on 32-bit platforms and could potentially result in incorrect results. fls and, e.g., __builtin_ffs() return the same answer for any given input, making it seem like the name fls (find last set) is a misnomer and ffs (find first set, starting from the lsb) is the more accurate name. Using __builtin_ffs() causes the compiler (in intel) to emit code with the bsf (bit scan forward) insn, which is approx 3x faster than the code in ffs(), at least on the machine I tried it on. (Even so, it takes 10M+ iterations for the speed difference to be measurable. Choosing the "faster" implementation seems like a no-brainer, even if there may not be any significant gain by doing so.) Change-Id: I1616dda1a5b76f208ba737a713877c1673131e33 Signed-off-by: Kaleb S. KEITHLEY <kkeithle@redhat.com> Reviewed-on: https://review.gluster.org/17142 Smoke: Gluster Build System <jenkins@build.gluster.org> NetBSD-regression: NetBSD Build System <jenkins@build.gluster.org> CentOS-regression: Gluster Build System <jenkins@build.gluster.org> Reviewed-by: Niels de Vos <ndevos@redhat.com> Reviewed-by: Jeff Darcy <jeff@pl.atyp.us>
Diffstat (limited to 'contrib/timer-wheel/find_last_bit.c')
-rw-r--r--contrib/timer-wheel/find_last_bit.c17
1 files changed, 12 insertions, 5 deletions
diff --git a/contrib/timer-wheel/find_last_bit.c b/contrib/timer-wheel/find_last_bit.c
index 054e90a076f..0479c52f904 100644
--- a/contrib/timer-wheel/find_last_bit.c
+++ b/contrib/timer-wheel/find_last_bit.c
@@ -15,15 +15,22 @@
*/
/**
- * @find_last_bit
- * optimized implementation of find last bit in
+ * @find_first_bit
+ * optimized implementation of find first bit in
*/
#ifndef BITS_PER_LONG
+#ifdef __LP64__
#define BITS_PER_LONG 64
+#else
+#define BITS_PER_LONG 32
+#endif
#endif
-static inline int fls(int x)
+#if defined(__GNUC__) || defined(__clang__)
+#define ffs(p) __builtin_ffs(p)
+#else
+static inline int ffs(int x)
{
int r = 32;
@@ -51,7 +58,7 @@ static inline int fls(int x)
}
return r;
}
-
+#endif
unsigned long gf_tw_find_last_bit(const unsigned long *addr, unsigned long size)
{
@@ -73,7 +80,7 @@ unsigned long gf_tw_find_last_bit(const unsigned long *addr, unsigned long size)
tmp = addr[--words];
if (tmp) {
found:
- return words * BITS_PER_LONG + fls(tmp);
+ return words * BITS_PER_LONG + ffs(tmp);
}
}