On 01/03/2013 02:57:33 PM, Alexander Graf wrote:
On 03.01.2013, at 21:32, Scott Wood wrote:
> On 01/03/2013 02:31:30 PM, Alexander Graf wrote:
>> Am 03.01.2013 um 21:07 schrieb Scott Wood
<scottw...@freescale.com>:
>> > On 01/03/2013 12:53:13 PM, Alexander Graf wrote:
>> >> On 22.12.2012, at 03:15, Scott Wood wrote:
>> >> > Search the queue more efficiently by first looking for a
non-zero word,
>> >> > and then using the common bit-searching function to find the
bit within
>> >> > the word. It would be even nicer if bitops_ffsl() could be
hooked up
>> >> > to the compiler intrinsic so that bit-searching instructions
could be
>> >> > used, but that's another matter.
>> >> >
>> >> > Signed-off-by: Scott Wood <scottw...@freescale.com>
>> >> What we really want is a bitmap wide ffs() bipops helper
function that returns the first set bit in a bitmap and can optimize
the hell out of that operation inside of itself. I don't think this
belongs to the OpenPIC code.
>> >
>> > Well, we do have find_next_bit() in bitops.c, but it looks
comparitively complicated in order to be generic and simply return a
value rather than perform an action on each bit set. I suspect that
the code in this patch would be faster, and avoids the need for me to
follow all the twists and turns of find_next_bit() to figure out
whether the undocumented interface is actually exactly what I guess
it to be (e.g. what does it return when no bit is found?).
>> I would just call it bit_ffs and follow the same semantics.
>
> I'm not sure how that's an answer to what I wrote...
The answer is "man ffs" and it will tell you what semantics the
function would have.
Not completely, because ffs() doesn't operate on multiple words.
However given that find_next_bit() is defined in Linux, why not use
its semantics? Can't we just copy Linux code here?
As I said, the function *has* been copied. Its semantics differ from
ffs() (which is good, since ffs() has annoying semantics such as adding
one to the result). It took a fair bit of staring at the function to
be convinced that the not-found case returns "size" under all
circumstances and that there isn't a bug when size is not a multiple of
BITS_PER_LONG.
Whether it's faster or not is another question, but I'd like to keep
bitops internals as internal to bitops as we can.
I think you get diminishing (and eventually negative) returns if you
push it too far, but fine, I'll send a v2 using find_next_bit().
We could even completely hide the bitops implementation details
behind a private struct definition. But that would mean that we'd
have to create an indirect memory access for the bitmap itself :(.
One advantage of keeping these bits internal would be that we could
even add more accelerations. We could for example add another bitmap
layer on top of the bitmap internally, similar to how the MSIs get
another bitmap across all combined MSI registers in the MPIC. And
find_next_bit could use that to speed up the lookup for really big
bitmaps.
Perhaps, if it's shown to be a performance problem still.
-Scott
