From c92b8347aea8ce78ca3fbc49b88f5adadc98509b Mon Sep 17 00:00:00 2001 From: "Kaleb S. KEITHLEY" Date: Sun, 30 Apr 2017 18:59:17 -0400 Subject: 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 Reviewed-on: https://review.gluster.org/17142 Smoke: Gluster Build System NetBSD-regression: NetBSD Build System CentOS-regression: Gluster Build System Reviewed-by: Niels de Vos Reviewed-by: Jeff Darcy --- contrib/timer-wheel/find_last_bit.c | 17 ++++++++++++----- 1 file 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); } } -- cgit