Re: [Qemu-devel] [PATCH 12/15] openpic: IRQ_check: search the queue a word at a time

[Scott Wood]

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  
> <address@hidden>:
> >> > 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 <address@hidden>
> >> >> 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