[KJ] anyone interested in the "power of 2" stuff?

[KJ] anyone interested in the "power of 2" stuff?

[Robert P. J. Day]

  the latest "git pull" now has the definition of the inline function
"is_power_of_2()," if anyone wants to adopt that as a cleanup project.
the wiki page describing that is here:

http://fsdev.net/wiki/index.php?title=Power_of_2_stuff

  read that page carefully before you start, to make sure you're doing
things properly.

  any takers?

rday

-- 
====================================
Robert P. J. Day
Linux Consulting, Training and Annoying Kernel Pedantry
Waterloo, Ontario, CANADA

http://fsdev.net/wiki/index.php?title=Main_Page
====================================
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] anyone interested in the "power of 2" stuff?

[Vignesh Babu BM]

On Thu, 2007-02-08 at 17:17 -0500, Robert P. J. Day wrote:

> http://fsdev.net/wiki/index.php?title=Power_of_2_stuff
> 
>   any takers?
> 
> rday
> 

I would take that up rday.

-- 
Regards,  
Vignesh Babu BM  
_____________________________________________________________  
"Why is it that every time I'm with you, makes me believe in magic?"

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] anyone interested in the "power of 2" stuff?

[Robert P. J. Day]

On Fri, 9 Feb 2007, Vignesh Babu BM wrote:

>
> On Thu, 2007-02-08 at 17:17 -0500, Robert P. J. Day wrote:
>
> > http://fsdev.net/wiki/index.php?title=Power_of_2_stuff
> >
> >   any takers?
> >
> > rday
> >
>
> I would take that up rday.

ok, have at it, and keep us up to date on the wiki page.

rday

p.s.  note that we still haven't formalized the rounding stuff so, as
i mention in the wiki page, the only changes should involve *just*
strict power of 2 testing, and not as part of a larger bit of code
that's trying to round, or anything like that.

-- 
====================================
Robert P. J. Day
Linux Consulting, Training and Annoying Kernel Pedantry
Waterloo, Ontario, CANADA

http://fsdev.net/wiki/index.php?title=Main_Page
====================================
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] anyone interested in the "power of 2" stuff?

[Vignesh Babu BM]

I have a doubt:
There are instances as follows:

/* ASIC location registers should be 0 or have only a single bit set. */
    if (   (iobase_reg  & (iobase_reg - 1))

here and in other similar situations the variables values vary from 0
and above
In such checks the above might be more optimized...as the is_power_of_2
will
1. check for 0 and fail that
2. check for even and pass it
3. or if it is odd...fail it

op 1 would be done followed by op 2/3

The code would be like
if(!iobase_reg && !is_power_of_2(iobase_reg))
---where we are checking for 0 at 2 places-both inside and outside of
is_power_of_2

But the n & (n-1) is just one step.
Is this not more optimised?

What would you suggest here?

On Fri, 2007-02-09 at 07:39 -0500, Robert P. J. Day wrote:
> On Fri, 9 Feb 2007, Vignesh Babu BM wrote:
> 
> >
> > On Thu, 2007-02-08 at 17:17 -0500, Robert P. J. Day wrote:
> >
> > > http://fsdev.net/wiki/index.php?title=Power_of_2_stuff
> > >
> > >   any takers?
> > >
> > > rday
> > >
> >
> > I would take that up rday.
> 
> ok, have at it, and keep us up to date on the wiki page.
> 
> rday
> 
> p.s.  note that we still haven't formalized the rounding stuff so, as
> i mention in the wiki page, the only changes should involve *just*
> strict power of 2 testing, and not as part of a larger bit of code
> that's trying to round, or anything like that.
> 
-- 
Regards,  
Vignesh Babu BM  
_____________________________________________________________  
"Why is it that every time I'm with you, makes me believe in magic?"
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] anyone interested in the "power of 2" stuff?

[Robert P. J. Day]

On Tue, 13 Feb 2007, Vignesh Babu BM wrote:

>
> I have a doubt:
> There are instances as follows:
>
> /* ASIC location registers should be 0 or have only a single bit set. */
>     if (   (iobase_reg  & (iobase_reg - 1))
>
> here and in other similar situations the variables values vary from 0
> and above
> In such checks the above might be more optimized...as the is_power_of_2
> will
> 1. check for 0 and fail that
> 2. check for even and pass it
> 3. or if it is odd...fail it
>
> op 1 would be done followed by op 2/3
>
> The code would be like
> if(!iobase_reg && !is_power_of_2(iobase_reg))
> ---where we are checking for 0 at 2 places-both inside and outside of
> is_power_of_2
>
> But the n & (n-1) is just one step.
> Is this not more optimised?
>
> What would you suggest here?

i was fairly sure this issue was going to raise its ugly head
eventually -- where a test was checking if something was a power of
two *or* zero.  first off, let's agree that we are *not* going to
redefine what it means to be a power of two.  zero *isn't*.  period.
so changing that macro is out of the question.

here's an option.  that test above isn't *really* asking if something
is a power of two, *is* it?  it's asking if at most one bit is set.
and while that might seem *superficially* almost the same thing,
semantically it's quite different.

it might be worth defining a macro:

  #define at_most_one_bit_set(n)      ((n) & ((n) - 1))

then we get the optimization, we get the proper behaviour, and we get
more meaningful semantics that actually reflect the test that is being
done.  in a nutshell, don't test for "power of twoness" if that's not
what's being asked.  if one is testing for at most one bit set, phrase
it that way.  obviously, this means you might have to look at one of
those tests closely to deduce what the programmer was trying to do
but, for the most part, that shouldn't be impossible.

thoughts?

rday

-- 
====================================
Robert P. J. Day
Linux Consulting, Training and Annoying Kernel Pedantry
Waterloo, Ontario, CANADA

http://fsdev.net/wiki/index.php?title=Main_Page
====================================
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] anyone interested in the "power of 2" stuff?

[Vignesh Babu BM]

On Tue, 2007-02-13 at 04:46 -0500, Robert P. J. Day wrote:
> On Tue, 13 Feb 2007, Vignesh Babu BM wrote:
> 
> >
> > I have a doubt:
> > There are instances as follows:
> >
> > if(!iobase_reg && !is_power_of_2(iobase_reg))
> > ---where we are checking for 0 at 2 places-both inside and outside of
> > is_power_of_2
> >
> > But the n & (n-1) is just one step.
> > Is this not more optimised?
> >
> > What would you suggest here?
> 

> and while that might seem *superficially* almost the same thing,
> semantically it's quite different.
Agreed.

> 
> it might be worth defining a macro:
> 
>   #define at_most_one_bit_set(n)      ((n) & ((n) - 1))
> 
> thoughts?
> 
> rday
> 

There are around 80 instances of code similar to the above. So instead
of a macro why not do an inline function?
And btw where would it go?

-- 
Regards,  
Vignesh Babu BM  
_____________________________________________________________  
"Why is it that every time I'm with you, makes me believe in magic?"
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] anyone interested in the "power of 2" stuff?

[Robert P. J. Day]

On Tue, 13 Feb 2007, Vignesh Babu BM wrote:

>
> On Tue, 2007-02-13 at 04:46 -0500, Robert P. J. Day wrote:
> > On Tue, 13 Feb 2007, Vignesh Babu BM wrote:
> >
> > >
> > > I have a doubt:
> > > There are instances as follows:
> > >
> > > if(!iobase_reg && !is_power_of_2(iobase_reg))
> > > ---where we are checking for 0 at 2 places-both inside and outside of
> > > is_power_of_2
> > >
> > > But the n & (n-1) is just one step.
> > > Is this not more optimised?
> > >
> > > What would you suggest here?
> >
>
> > and while that might seem *superficially* almost the same thing,
> > semantically it's quite different.
> Agreed.
>
> >
> > it might be worth defining a macro:
> >
> >   #define at_most_one_bit_set(n)      ((n) & ((n) - 1))
> >
> > thoughts?
> >
> > rday
> >
>
> There are around 80 instances of code similar to the above. So
> instead of a macro why not do an inline function? And btw where
> would it go?

sorry, i meant an inline function -- force of habit.  but let's not
rush into anything.  for now, just work on those tests that *clearly*
represent power-of-two tests, and nothing else.

so even if you find a test of the form "n & (n - 1)", depending on the
context, the coder might really have meant it to not include zero.
conversely, if you find a test of the form "n != 0 && (n & (n - 1))",
even though that's *exactly* our power-of-two test, it's possible the
coder might have been testing for exactly one bit being set.  (those
tests are, obviously, identical, but semantically, they have different
meanings.)

so, for now, just submit patches for what are *clearly* power-of-two
tests and leave the rest alone.  those can be handled later by a more
appropriate inline function that better represents their semantic
meaning.

rday

-- 
====================================
Robert P. J. Day
Linux Consulting, Training and Annoying Kernel Pedantry
Waterloo, Ontario, CANADA

http://fsdev.net/wiki/index.php?title=Main_Page
====================================
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors