Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Message-ID: <423c4368-0a1c-792c-2637-768532fc7782@rasmusvillemoes.dk>
Date:   Thu, 7 Jul 2022 09:25:07 +0200
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101
 Thunderbird/91.9.1
Subject: Re: [PATCH 1/5] lib: add find_nth(,and,andnot)_bit()
Content-Language: en-US
To:     Yury Norov <yury.norov@gmail.com>, linux-kernel@vger.kernel.org,
        Alexander Lobakin <alexandr.lobakin@intel.com>,
        Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
        Arnd Bergmann <arnd@arndb.de>, David Gow <davidgow@google.com>,
        Eric Dumazet <edumazet@google.com>,
        Isabella Basso <isabbasso@riseup.net>,
        Kees Cook <keescook@chromium.org>,
        Keith Busch <kbusch@kernel.org>,
        Kumar Kartikeya Dwivedi <memxor@gmail.com>,
        Marco Elver <elver@google.com>,
        Mark Rutland <mark.rutland@arm.com>,
        Steven Rostedt <rostedt@goodmis.org>,
        =?UTF-8?Q?Toke_H=c3=b8iland-J=c3=b8rgensen?= <toke@redhat.com>
References: <20220706182300.70862-1-yury.norov@gmail.com>
 <20220706182300.70862-2-yury.norov@gmail.com>
From:   Rasmus Villemoes <linux@rasmusvillemoes.dk>
In-Reply-To: <20220706182300.70862-2-yury.norov@gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Precedence: bulk

On 06/07/2022 20.22, Yury Norov wrote:
> Kernel lacks for a function that searches for Nth bit in a bitmap.
> Usually people do it like this:
> 	for_each_set_bit(bit, mask, size)
> 		if (--n == 0)
> 			return bit;
> 
> We can do it more efficiently, if we:
> 1. find a word containing Nth bit, using hweight(); and
> 2. find the bit, using a helper fns(), that works similarly to
>    __ffs() and ffz().
> 
> fns() is implemented as a simple loop. For x86_64, there's PDEP instruction
> to do that: ret = clz(pdep(1 << idx, num)). However, for large bitmaps the
> most of improvement comes from using hweight(), so I kept fns() simple.
> 
> New find_nth_bit() is ~70 times faster on x86_64/kvm:
> for_each_bit:                  7154190 ns,  16411 iterations
> find_nth_bit:                505493126 ns,  16315 iterations

Eh, have you interchanged these somehow, otherwise this reads as
find_nth_bit being ~70 times _slower_?

> With all that, a family of 3 new functions is added, and used where
> appropriate in the following patches.
> 
> Signed-off-by: Yury Norov <yury.norov@gmail.com>
> ---
>  include/linux/bitops.h | 19 ++++++++++
>  include/linux/find.h   | 79 ++++++++++++++++++++++++++++++++++++++++++
>  lib/find_bit.c         | 20 +++++++++++
>  3 files changed, 118 insertions(+)
> 
> diff --git a/include/linux/bitops.h b/include/linux/bitops.h
> index 7aaed501f768..86072cfcbe17 100644
> --- a/include/linux/bitops.h
> +++ b/include/linux/bitops.h
> @@ -196,6 +196,25 @@ static inline unsigned long __ffs64(u64 word)
>  	return __ffs((unsigned long)word);
>  }
>  
> +/**
> + * fns - find N'th set bit in a 64 bit word
> + * @word: The 64 bit word
> + * @n: Bit to find
> + */
> +static inline unsigned long fns(unsigned long word, unsigned int n)
> +{
> +	unsigned int bit;
> +
> +	while (word) {
> +		bit = __ffs(word);
> +		if (--n == 0)
> +			return bit;
> +		__clear_bit(bit, &word);
> +	}
> +
> +	return BITS_PER_LONG;
> +}

Urgh.  "unsigned long" is not necessarily a 64 bit word. And I don't
like that the index is apparently 1-based (and that surprising API isn't
spelled out anywhere). This is also way too big to be inline IMO.

>  #ifndef find_first_and_bit
>  /**
>   * find_first_and_bit - find the first set bit in both memory regions
> diff --git a/lib/find_bit.c b/lib/find_bit.c
> index 1b8e4b2a9cba..7b8ad12c8cc7 100644
> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
> @@ -89,6 +89,26 @@ unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
>  EXPORT_SYMBOL(_find_first_bit);
>  #endif
>  
> +unsigned long _find_nth_bit(const unsigned long *addr1, const unsigned long *addr2,
> +				unsigned long size, unsigned long n, bool not)
> +{
> +	unsigned long val, idx, w;
> +
> +	for (idx = 0; idx * BITS_PER_LONG < size; idx++, n -= w) {
> +		val = addr1[idx];
> +		if (addr2)
> +			val &= not ? ~addr2[idx] : addr2[idx];

Maybe this could be microoptimized by doing

unsigned long addr2mask = not ? ~0UL : 0UL;
...

  val &= (addr2[idx] ^ addr2mask);

but I don't think it'll make a difference.

Rasmus