wifi: carl9170: micro-optimize carl9170_tx_shift_bm()

[PATCH] wifi: carl9170: micro-optimize carl9170_tx_shift_bm()

Posted by Yury Norov 8 months, 3 weeks ago

The function calls bitmap_empty() just before find_first_bit(). Both
functions are O(N). Because find_first_bit() returns >= nbits in case of
empty bitmap, the bitmap_empty() test may be avoided.

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 drivers/net/wireless/ath/carl9170/tx.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/drivers/net/wireless/ath/carl9170/tx.c b/drivers/net/wireless/ath/carl9170/tx.c
index 0226c31a6cae..b7717f9e1e9b 100644
--- a/drivers/net/wireless/ath/carl9170/tx.c
+++ b/drivers/net/wireless/ath/carl9170/tx.c
@@ -366,8 +366,7 @@ static void carl9170_tx_shift_bm(struct ar9170 *ar,
 	if (WARN_ON_ONCE(off >= CARL9170_BAW_BITS))
 		return;
 
-	if (!bitmap_empty(tid_info->bitmap, off))
-		off = find_first_bit(tid_info->bitmap, off);
+	off = min(off, find_first_bit(tid_info->bitmap, off));
 
 	tid_info->bsn += off;
 	tid_info->bsn &= 0x0fff;
-- 
2.43.0

Re: [PATCH] wifi: carl9170: micro-optimize carl9170_tx_shift_bm()

Posted by Jeff Johnson 7 months ago

On Wed, 26 Mar 2025 11:51:58 -0400, Yury Norov wrote:
> The function calls bitmap_empty() just before find_first_bit(). Both
> functions are O(N). Because find_first_bit() returns >= nbits in case of
> empty bitmap, the bitmap_empty() test may be avoided.
> 
> 

Applied, thanks!

[1/1] wifi: carl9170: micro-optimize carl9170_tx_shift_bm()
      commit: 08e3cc13b0d050860f41b4eaaa21c789af968b98

Best regards,
-- 
Jeff Johnson <jeff.johnson@oss.qualcomm.com>

Re: [PATCH] wifi: carl9170: micro-optimize carl9170_tx_shift_bm()

Posted by Christian Lamparter 8 months, 3 weeks ago

Hi,

On Wed, Mar 26, 2025 at 4:52 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> The function calls bitmap_empty() just before find_first_bit(). Both
> functions are O(N). Because find_first_bit() returns >= nbits in case of
> empty bitmap, the bitmap_empty() test may be avoided.
>

I looked up bitmap_empty():
<https://web.git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/bitmap.h#n423>

apart from the small_const_nbits stuff (which carl9170 likely does not qualify
for since from what I remember it's a 128bits bitmap) the function just does:

|   return find_first_bit(src, nbits) == nbits;

so yes, find_first_bit runs twice with same parameters... Unless the
compiler is smart
enough to detect this and (re-)use the intermediate result later. But
I haven't check
if this is the case with any current, old or future compilers. Has anyone?

Anyway, Sure.

> Signed-off-by: Yury Norov <yury.norov@gmail.com>

Acked-by: Christian Lamparter <chunkeey@gmail.com>

> ---
>  drivers/net/wireless/ath/carl9170/tx.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
>
> diff --git a/drivers/net/wireless/ath/carl9170/tx.c b/drivers/net/wireless/ath/carl9170/tx.c
> index 0226c31a6cae..b7717f9e1e9b 100644
> --- a/drivers/net/wireless/ath/carl9170/tx.c
> +++ b/drivers/net/wireless/ath/carl9170/tx.c
> @@ -366,8 +366,7 @@ static void carl9170_tx_shift_bm(struct ar9170 *ar,
>         if (WARN_ON_ONCE(off >= CARL9170_BAW_BITS))
>                 return;
>
> -       if (!bitmap_empty(tid_info->bitmap, off))
> -               off = find_first_bit(tid_info->bitmap, off);
> +       off = min(off, find_first_bit(tid_info->bitmap, off));
>
>         tid_info->bsn += off;
>         tid_info->bsn &= 0x0fff;
> --
> 2.43.0
>

Re: [PATCH] wifi: carl9170: micro-optimize carl9170_tx_shift_bm()

Posted by Yury Norov 7 months, 3 weeks ago

On Wed, Mar 26, 2025 at 09:00:33PM +0100, Christian Lamparter wrote:
> Hi,
> 
> On Wed, Mar 26, 2025 at 4:52 PM Yury Norov <yury.norov@gmail.com> wrote:
> >
> > The function calls bitmap_empty() just before find_first_bit(). Both
> > functions are O(N). Because find_first_bit() returns >= nbits in case of
> > empty bitmap, the bitmap_empty() test may be avoided.
> >
> 
> I looked up bitmap_empty():
> <https://web.git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/bitmap.h#n423>
> 
> apart from the small_const_nbits stuff (which carl9170 likely does not qualify
> for since from what I remember it's a 128bits bitmap) the function just does:
> 
> |   return find_first_bit(src, nbits) == nbits;
> 
> so yes, find_first_bit runs twice with same parameters... Unless the
> compiler is smart
> enough to detect this and (re-)use the intermediate result later. But
> I haven't check
> if this is the case with any current, old or future compilers. Has anyone?
> 
> Anyway, Sure.
> 
> > Signed-off-by: Yury Norov <yury.norov@gmail.com>
> 
> Acked-by: Christian Lamparter <chunkeey@gmail.com>

Thanks, Chrustian. So, how is that supposed to be merged?
I can move it with bitmap-for-next, unless there's no better
branch.

Thanks,
Yury

Re: [PATCH] wifi: carl9170: micro-optimize carl9170_tx_shift_bm()

Posted by Jeff Johnson 7 months ago

On 4/27/2025 8:25 AM, Yury Norov wrote:
> On Wed, Mar 26, 2025 at 09:00:33PM +0100, Christian Lamparter wrote:
>> Hi,
>>
>> On Wed, Mar 26, 2025 at 4:52 PM Yury Norov <yury.norov@gmail.com> wrote:
>>>
>>> The function calls bitmap_empty() just before find_first_bit(). Both
>>> functions are O(N). Because find_first_bit() returns >= nbits in case of
>>> empty bitmap, the bitmap_empty() test may be avoided.
>>>
>>
>> I looked up bitmap_empty():
>> <https://web.git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/bitmap.h#n423>
>>
>> apart from the small_const_nbits stuff (which carl9170 likely does not qualify
>> for since from what I remember it's a 128bits bitmap) the function just does:
>>
>> |   return find_first_bit(src, nbits) == nbits;
>>
>> so yes, find_first_bit runs twice with same parameters... Unless the
>> compiler is smart
>> enough to detect this and (re-)use the intermediate result later. But
>> I haven't check
>> if this is the case with any current, old or future compilers. Has anyone?
>>
>> Anyway, Sure.
>>
>>> Signed-off-by: Yury Norov <yury.norov@gmail.com>
>>
>> Acked-by: Christian Lamparter <chunkeey@gmail.com>
> 
> Thanks, Chrustian. So, how is that supposed to be merged?
> I can move it with bitmap-for-next, unless there's no better
> branch.
> 
> Thanks,
> Yury
> 

Yury, did you take this?
If not, I'll take it through the ath tree.

Re: [PATCH] wifi: carl9170: micro-optimize carl9170_tx_shift_bm()

Posted by Yury Norov 7 months ago

On Tue, May 20, 2025 at 09:24:14AM -0700, Jeff Johnson wrote:
> On 4/27/2025 8:25 AM, Yury Norov wrote:
> > On Wed, Mar 26, 2025 at 09:00:33PM +0100, Christian Lamparter wrote:
> >> Hi,
> >>
> >> On Wed, Mar 26, 2025 at 4:52 PM Yury Norov <yury.norov@gmail.com> wrote:
> >>>
> >>> The function calls bitmap_empty() just before find_first_bit(). Both
> >>> functions are O(N). Because find_first_bit() returns >= nbits in case of
> >>> empty bitmap, the bitmap_empty() test may be avoided.
> >>>
> >>
> >> I looked up bitmap_empty():
> >> <https://web.git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/bitmap.h#n423>
> >>
> >> apart from the small_const_nbits stuff (which carl9170 likely does not qualify
> >> for since from what I remember it's a 128bits bitmap) the function just does:
> >>
> >> |   return find_first_bit(src, nbits) == nbits;
> >>
> >> so yes, find_first_bit runs twice with same parameters... Unless the
> >> compiler is smart
> >> enough to detect this and (re-)use the intermediate result later. But
> >> I haven't check
> >> if this is the case with any current, old or future compilers. Has anyone?
> >>
> >> Anyway, Sure.
> >>
> >>> Signed-off-by: Yury Norov <yury.norov@gmail.com>
> >>
> >> Acked-by: Christian Lamparter <chunkeey@gmail.com>
> > 
> > Thanks, Chrustian. So, how is that supposed to be merged?
> > I can move it with bitmap-for-next, unless there's no better
> > branch.
> > 
> > Thanks,
> > Yury
> > 
> 
> Yury, did you take this?
> If not, I'll take it through the ath tree.

No. Please take with ath.