a_ctz_32: Instead of a subtraction by 31, use an xor

Submitted by Rosen Penev on Nov. 8, 2019, 2:39 a.m.

Details

Message ID 20191108023955.4402-1-rosenp@gmail.com
State New
Series "a_ctz_32: Instead of a subtraction by 31, use an xor"
Headers show

Commit Message

Rosen Penev Nov. 8, 2019, 2:39 a.m.
This reduces produced assembly from a mov and sub to a single xor.

Tested with godbolt: https://godbolt.org/z/Qz-Qr5

Signed-off-by: Rosen Penev <rosenp@gmail.com>
---
 src/internal/atomic.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Patch hide | download patch | download mbox

diff --git a/src/internal/atomic.h b/src/internal/atomic.h
index f938879b..196b3fb1 100644
--- a/src/internal/atomic.h
+++ b/src/internal/atomic.h
@@ -256,7 +256,7 @@  static inline void a_crash()
 static inline int a_ctz_32(uint32_t x)
 {
 #ifdef a_clz_32
-	return 31-a_clz_32(x&-x);
+	return a_clz_32(x&-x)^31;
 #else
 	static const char debruijn32[32] = {
 		0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13,

Comments

Alexander Monakov Dec. 12, 2019, 3:10 p.m.
On Thu, 7 Nov 2019, Rosen Penev wrote:

> This reduces produced assembly from a mov and sub to a single xor.
> 
> Tested with godbolt: https://godbolt.org/z/Qz-Qr5
> 
> Signed-off-by: Rosen Penev <rosenp@gmail.com>
> ---
>  src/internal/atomic.h | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/src/internal/atomic.h b/src/internal/atomic.h
> index f938879b..196b3fb1 100644
> --- a/src/internal/atomic.h
> +++ b/src/internal/atomic.h
> @@ -256,7 +256,7 @@ static inline void a_crash()
>  static inline int a_ctz_32(uint32_t x)
>  {
>  #ifdef a_clz_32
> -	return 31-a_clz_32(x&-x);
> +	return a_clz_32(x&-x)^31;

(since there was no other response...)

While certainly this is a nice improvement when considered in isolation,
looking at how this is used in the rest of the library (in ffs, ffsl, qsort)
reveals that returned value is used in further arithmetics.

So e.g. ffs/ffsl do a_ctz_l(i)+1, and +1 may be folded together with 31-...,
but not with the xor.  Thus the original is preferable.

Alexander
Rich Felker Dec. 12, 2019, 3:17 p.m.
On Thu, Dec 12, 2019 at 06:10:31PM +0300, Alexander Monakov wrote:
> On Thu, 7 Nov 2019, Rosen Penev wrote:
> 
> > This reduces produced assembly from a mov and sub to a single xor.
> > 
> > Tested with godbolt: https://godbolt.org/z/Qz-Qr5
> > 
> > Signed-off-by: Rosen Penev <rosenp@gmail.com>
> > ---
> >  src/internal/atomic.h | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> > 
> > diff --git a/src/internal/atomic.h b/src/internal/atomic.h
> > index f938879b..196b3fb1 100644
> > --- a/src/internal/atomic.h
> > +++ b/src/internal/atomic.h
> > @@ -256,7 +256,7 @@ static inline void a_crash()
> >  static inline int a_ctz_32(uint32_t x)
> >  {
> >  #ifdef a_clz_32
> > -	return 31-a_clz_32(x&-x);
> > +	return a_clz_32(x&-x)^31;
> 
> (since there was no other response...)
> 
> While certainly this is a nice improvement when considered in isolation,
> looking at how this is used in the rest of the library (in ffs, ffsl, qsort)
> reveals that returned value is used in further arithmetics.
> 
> So e.g. ffs/ffsl do a_ctz_l(i)+1, and +1 may be folded together with 31-...,
> but not with the xor.  Thus the original is preferable.

Thanks for commenting on this. I hadn't thought about that, and indeed
the current version is probably better.

It would be even nicer if there were some way to make the compiler
aware that the range is limited (so that it could make such a
transformation itself in either direction if it wanted), but it
probably doesn't matter.

Rich